① 關於c語言的田忌賽馬問題。
應該是貪心的思路有點問題：
解題思路：
貪心演算法。
如果當前最好的馬可以勝齊王最好的馬，那麼讓這兩匹馬比一場。
如果當前最差的馬能勝齊王最差的馬，那麼讓這兩匹馬比一場。
如果上面兩個條件都不滿足，那麼讓當前最差的馬和齊王最好的馬比一場。
② acm田忌賽馬問題在線等急求！！
好暈。。田忌賽馬問題可用貪心演算法進行匹配。
我在這里借花敬佛：
http://blog.sina.com.cn/s/blog_5f0d09840100n7yx.html
③ 田忌賽馬 de 演算法
貪心就可以了..
先排序,然後比較隊頭,隊尾,如果都不能贏就用小的碰大的
④ 關於用動態規劃法求最大公共子序列的問題
#include <iostream>
#include <string>
using namespace std;
#define N 100 // 宏定義N的初始值為100
char a[N], b[N], str[N]; //a用於保存第一個輸入的字元的，b用於保存第二個，str用於判斷兩個字元是不是都遍歷到了'\0'(到了的話說明字元串處理完畢)，先初始化為N
int c[N][N]; //int型數組，初始化為N，用於保存兩個字元串的內容
//下面你要跟著程序的調用規律走，先看主函數調用的是build_lcs(),然後是lcs_len()
int lcs_len(char* a, char* b,int c[][N]) //用於計算兩個字元串的每個元素的內容！
{
int m=strlen(a), n=strlen(b), i, j; //聲明m，n，i,j變數,其中的strlen()函數是用來獲取字元串長度的
for (i=0; i<=m; i++) //
c[i][0]=0; //遍歷第一個字元串的內容，分別保存到c的一維數組中
for (i=0; i<=n; i++) //
c[0][i]=0; //遍歷第二個字元串的內容，分別保存到c的二維數組中
for (i=1; i<=m; i++) //第一層FOR循環
{ //
for (j=1; j<=n; j++) //第二層FOR循環
{ //
//
if (a[i-1]==b[j-1]) //判斷第一個字元串的第i(-1是為了去掉'\0')個元素的值等於第二個字元串第j個元素
c[i][j]=c[i-1][j-1]+1; //
else if (c[i-1][j]>=c[i][j-1]) //如果不是，則判斷第一個字元數組的第i個元素與第二個字元數組所有元素相等(j循環j遍,i才循環1遍)
c[i][j]=c[i-1][j]; //
else //如果不是，則判斷第一個字元數組的第j個元素與第二個字元數組所有元素相等(i循環j遍,j才循環1遍)
c[i][j]=c[i][j-1]; //
} //
} //
return c[m][n]; //得到相同的元素並返回
}
char* build_lcs(char s[],char* a,char* b)
{
int i=strlen(a), j=strlen(b);
int k=lcs_len(a,b,c);
s[k]='\0';
while (k>0) //下面都很簡單了！
{
if (c[i][j]==c[i-1][j])
i--;
else if (c[i][j]==c[i][j-1])
j--;
else
{
s[--k]=a[i-1];
i--; j--;
}
}
cout<<s<<endl;
return s;
}
void main()
{
cout<<"輸入兩個長度小於"<<N<<"的字元串"<<endl;
cin>>a;
cin>>b;
cout<<"LCS="<<build_lcs(str,a,b)<<endl;
}
⑤ 田忌賽馬 de 演算法
原文：
齊使者如梁，孫臏以刑徒陰見，說齊使。齊使以為奇，竊載與之齊。齊將田忌善而客待之。忌數與齊諸公子馳逐重射。孫子見其馬足不甚相遠，馬有上、中、下輩。於是孫子謂田忌曰：「君弟重射，臣能令君勝。」田忌信然之，與王及諸公子逐射千金。及臨質，孫子曰：「今以君之下駟彼上駟，取君上駟與彼中駟，取君中駟與彼下駟。」既馳三輩畢，而田忌一不勝而再勝，卒得王千金。於是忌進孫子於威王。威王問兵法，遂以為師。
譯文：
齊國使者到大梁來，孫臏以刑徒的身份秘密拜見，用言辭打動齊國使者。齊國使者覺得此人不同凡響，就偷偷地用車把他載回齊國。齊國將軍田忌賞識他並像對待客人一樣禮待他。田忌經常與齊國諸公子賽馬，設重金賭注。孫臏發現他們的馬腳力都差不多，可分為上、中、下三等。於是孫臏對田忌說：「您只管下大賭注，我能讓您取勝。」田忌相信並答應了他，與齊王和諸公子用千金來賭勝。比賽即將開始，孫臏說：「現在用您的下等馬對付他們的上等馬，拿您的上等馬對付他們的中等馬，拿您的中等馬對付他們的下等馬。」三場比賽完後，田忌一場不勝而兩場勝，最終贏得齊王的千金賭注。於是田忌把孫臏推薦給齊威王。威王向他請教兵法後，就把他當作老師。