田忌賽馬演算法

A. 關於c語言的田忌賽馬問題。

應該是貪心的思路有點問題：
解題思路：
貪心演算法。
如果當前最好的馬可以勝齊王最好的馬，那麼讓這兩匹馬比一場。
如果當前最差的馬能勝齊王最差的馬，那麼讓這兩匹馬比一場。
如果上面兩個條件都不滿足，那麼讓當前最差的馬和齊王最好的馬比一場。

B. 田忌賽馬"的故事表現了運籌學的哪一特點

「田忌賽馬"的故事表現了運籌學的系統整體性這一特點。田忌賽馬這個故事表明，在有雙方參加的競賽或斗爭中，策略是很重要的，採用策略適當，就有可能在似乎一定會失敗的情況下取得勝利。研究這種競賽策略的數學分支，叫作博弈論，它是運籌學的重要內容。

運籌學中最初用數學方法研究博弈論是在國際象棋中開始的，旨在用來如何確定取勝的演算法。由於是研究雙方沖突、制勝對策的問題，所以這門學科在軍事方面有著十分重要的應用。

數學家還對水雷和艦艇、殲擊機和轟炸機之間的作戰、追蹤等問題進行了研究，提出了追逃雙方都能自主決策的數學理論。隨著人工智慧研究的進一步發展，對博弈論提出了更多新的要求。決策問題是由決策者和決策域構成的，而決策域又由決策空間、狀態空間和結果函數構成。

(2)田忌賽馬演算法擴展閱讀

運籌學理論：

1、排隊論，排隊論又叫隨機服務系統理論。最初是在二十世紀初由丹麥工程師艾爾郎關於電話交換機的效率研究開始的，在第二次世界大戰中為了對飛機場跑道的容納量進行估算，它得到了進一步的發展，其相應的學科更新論、可靠性理論等也都發展起來。

2、可靠性理論，可靠性理論是研究系統故障、以提高系統可靠性問題的理論。可靠性理論研究的系統一般分為兩類：不可修系統：如導彈等，這種系統的參數是壽命、可靠度等，可修復系統：如一般的機電設備等，這種系統的重要參數是有效度。

3、對策論，對策論也叫博弈論，前面講的田忌賽馬就是典型的博弈論問題。作為運籌學的一個分支，博弈論的發展也只有幾十年的歷史。系統地創建這門學科的數學家，馮·諾依曼。

C. usaco題目「田忌賽馬」

這樣是對的
設一個方案P中.共有W場，贏了N場，平了K場，則輸了(W-N-K)場
那麼該方案贏得的錢數為200N-200(W-N-K)=400N+200K-200W
因-200W一定..該題就是求最大的400N+200K
現在證明對於N最大，且在N最大的情況下K最大的方案P1,其贏得的錢設為T1,對任意方案Pi,T1>=Ti
1)對於方案Pi,如果Ni=N1,則Ki<=K1（由K1最大）,所以Ti<=T1
2)對於方案Pi,Ni<N1
找到一個在P1中贏了而在Pi中沒贏的馬(由Ni<N1,這樣的馬一定找得到)，
設該馬為H1,和它比賽的馬(P1中)為H'1,和H1比賽的馬(Pi)中，為H'2，H'1比賽的馬(Pi)中，為H2
我們可以讓H1在Pi中和H'1比賽，H2和H'2比賽，這樣使Pi多一匹勝馬，即H1,而H2和H'2的比賽或勝，或輸，或平，明顯地，無論哪種情況，這種變換多贏的錢都大於等於零。通過不斷地這種變換，我們一定能讓方案Pi變成1)中的方案，且變換中多贏的錢大於等於零，因此，可以證明
對於任意Pi,T1>=Ti
即...你的演算法是正確的
Q.E.D

...順手提一句，這題有一個動態規劃解，貌似編程復雜度和速度都會比二分圖最大匹配好一點...
畢竟...匈牙利演算法寫起來頭疼

D. 田忌賽馬 de 演算法

原文：
齊使者如梁，孫臏以刑徒陰見，說齊使。齊使以為奇，竊載與之齊。齊將田忌善而客待之。忌數與齊諸公子馳逐重射。孫子見其馬足不甚相遠，馬有上、中、下輩。於是孫子謂田忌曰：「君弟重射，臣能令君勝。」田忌信然之，與王及諸公子逐射千金。及臨質，孫子曰：「今以君之下駟彼上駟，取君上駟與彼中駟，取君中駟與彼下駟。」既馳三輩畢，而田忌一不勝而再勝，卒得王千金。於是忌進孫子於威王。威王問兵法，遂以為師。
譯文：
齊國使者到大梁來，孫臏以刑徒的身份秘密拜見，用言辭打動齊國使者。齊國使者覺得此人不同凡響，就偷偷地用車把他載回齊國。齊國將軍田忌賞識他並像對待客人一樣禮待他。田忌經常與齊國諸公子賽馬，設重金賭注。孫臏發現他們的馬腳力都差不多，可分為上、中、下三等。於是孫臏對田忌說：「您只管下大賭注，我能讓您取勝。」田忌相信並答應了他，與齊王和諸公子用千金來賭勝。比賽即將開始，孫臏說：「現在用您的下等馬對付他們的上等馬，拿您的上等馬對付他們的中等馬，拿您的中等馬對付他們的下等馬。」三場比賽完後，田忌一場不勝而兩場勝，最終贏得齊王的千金賭注。於是田忌把孫臏推薦給齊威王。威王向他請教兵法後，就把他當作老師。

E. acm田忌賽馬問題在線等急求！！

好暈。。田忌賽馬問題可用貪心演算法進行匹配。
我在這里借花敬佛：
http://blog.sina.com.cn/s/blog_5f0d09840100n7yx.html

F. c語言田忌賽馬問題

把雙方的馬從大到小排序 然後從前往後比較 老田贏了呢 就繼續往下比 老田比不過呢 就拉老田最慢的馬跟這個比 這里好理解

還有比平的情況 比平了還是從後面找一匹馬

找的時候 要是老田後面的馬可以贏對應位置的馬 就接著往前比 然後找到的那匹就跟前面這匹馬比

核心代碼：
for(i=0;i<n;i++)
{
if(t[head]>k[i])
{
head++;
ans+=200;
}
else if(t[head]<k[i])
{
tailt--;
ans-=200;
}
else if(t[head]==k[i])
{
for(j=tailt,m=tailk;j>=head;j--,m--)
{
if(t[j]>k[m])
{
ans+=200;
tailt--;
tailk--;
}
else
{
if(t[j]<k[i]) ans-=200;
tailt=--j;
tailk=m;
break;
}
}
}

if(head>tailt) break;
}

G. 田忌賽馬是運用了什麼數學方法

英語全稱為：Operational Research(英國)或者是Operations Research(美國)
在中國戰國時期,曾經有過一次流傳後世的賽馬比賽,相信大家都知道,這就是田忌賽馬.田忌賽馬的故事說明在已有的條件下,經過籌劃、安排,選擇一個最好的方案,就會取得最好的效果.可見,籌劃安排是十分重要的.
現在普遍認為,運籌學是近代應用數學的一個分支,主要是將生產、管理等事件中出現的一些帶有普遍性的運籌問題加以提煉,然後利用數學方法進行解決.前者提供模型,後者提供理論和方法.
運籌學的思想在古代就已經產生了.敵我雙方交戰,要克敵制勝就要在了解雙方情況的基礎上,做出最優的對付敵人的方法,這就是「運籌帷幄之中,決勝千里之外」的說法.
但是作為一門數學學科,用純數學的方法來解決最優方法的選擇安排,卻是晚多了.也可以說,運籌學是在二十世紀四十年代才開始興起的一門分支.
運籌學主要研究經濟活動和軍事活動中能用數量來表達的有關策劃、管理方面的問題.當然,隨著客觀實際的發展,運籌學的許多內容不但研究經濟和軍事活動,有些已經深入到日常生活當中去了.運籌學可以根據問題的要求,通過數學上的分析、運算,得出各種各樣的結果,最後提出綜合性的合理安排,已達到最好的效果.
運籌學作為一門用來解決實際問題的學科,在處理千差萬別的各種問題時,一般有以下幾個步驟：確定目標、制定方案、建立模型、制定解法.
雖然不大可能存在能處理及其廣泛對象的運籌學,但是在運籌學的發展過程中還是形成了某些抽象模型,並能應用解決較廣泛的實際問題.
隨著科學技術和生產的發展,運籌學已滲入很多領域里,發揮了越來越重要的作用.運籌學本身也在不斷發展,現在已經是一個包括好幾個分支的數學部門了.比如：數學規劃（又包含線性規劃；非線性規劃；整數規劃；組合規劃等）、圖論、網路流、決策分析、排隊論、可靠性數學理論、庫存論、對策論、搜索論、模擬等等.
運籌學有廣闊的應用領域,它已滲透到諸如服務、庫存、搜索、人口、對抗、控制、時間表、資源分配、廠址定位、能源、設計、生產、可靠性、等各個方面.
運籌學是軟科學中「硬度」較大的一門學科,兼有邏輯的數學和數學的邏輯的性質,是系統工程學和現代管理科學中的一種基礎理論和不可缺少的方法、手段和工具.運籌學已被應用到各種管理工程中,在現代化建設中發揮著重要作用.
[編輯本段]運籌學的歷史
運籌學作為一門現代科學,是在第二次世界大戰期間首先在英美兩國發展起來的,有的學者把運籌學描述為就組織系統的各種經營作出決策的科學手段. P.M.Morse與G.E.Kimball在他們的奠基作中給運籌學下的定義是：「運籌學是在實行管理的領域,運用數學方法,對需要進行管理的問題統籌規劃,作出決策的一門應用科學.」運籌學的另一位創始人定義運籌學是：「管理系統的人為了獲得關於系統運行的最優解而必須使用的一種科學方法.」它使用許多數學工具（包括概率統計、數理分析、線性代數等）和邏輯判斷方法,來研究系統中人、財、物的組織管理、籌劃調度等問題,以期發揮最大效益.
現代運籌學的起源可以追溯到幾十年前,在某些組織的管理中最先試用科學手段的時候.可是,現在普遍認為,運籌學的活動是從二次世界大戰初期的軍事任務開始的.當時迫切需要把各項稀少的資源以有效的方式分配給各種不同的軍事經營及在每一經營內的各項活動,所以美國及隨後美國的軍事管理當局都號召大批科學家運用科學手段來處理戰略與戰術問題,實際上這便是要求他們對種種（軍事）經營進行研究,這些科學家小組正是最早的運籌小組.
第二次世界大戰期間,「OR」成功地解決了許多重要作戰問題,顯示了科學的巨大物質威力,為「OR」後來的發展鋪平了道路.
當戰後的工業恢復繁榮時,由於組織內與日俱增的復雜性和專門化所產生的問題,使人們認識到這些問題基本上與戰爭中所曾面臨的問題類似,只是具有不同的現實環境而已,運籌學就這樣潛入工商企業和其它部門,在50年代以後得到了廣泛的應用.對於系統配置、聚散、競爭的運用機理深入的研究和應用,形成了比較完備的一套理論,如規劃論、排隊論、存貯論、決策論等等,由於其理論上的成熟,電子計算機的問世,又大大促進了運籌學的發展,世界上不少國家已成立了致力於該領域及相關活動的專門學會,美國於1952年成立了運籌學會,並出版期刊《運籌學》,世界其它國家也先後創辦了運籌學會與期刊,1957年成立了國際運籌學協會.
[編輯本段]運籌學的特點
運籌學的特點是：1.運籌學已被廣泛應用於工商企業、軍事部門、民政事業等研究組織內的統籌協調問題,故其應用不受行業、部門之限制；2.運籌學既對各種經營進行創造性的科學研究,又涉及到組織的實際管理問題,它具有很強的實踐性,最終應能向決策者提供建設性意見,並應收到實效；3.它以整體最優為目標,從系統的觀點出發,力圖以整個系統最佳的方式來解決該系統各部門之間的利害沖突.對所研究的問題求出最優解,尋求最佳的行動方案,所以它也可看成是一門優化技術,提供的是解決各類問題的優化方法.
[編輯本段]運籌學的研究方法
運籌學的研究方法有：1.從現實生活場合抽出本質的要素來構造數學模型,因而可尋求一個跟決策者的目標有關的解；2.探索求解的結構並導出系統的求解過程；3.從可行方案中尋求系統的最優解法.
[編輯本段]運籌學的具體內容
運籌學的具體內容包括：規劃論（包括線性規劃、非線性規劃、整數規劃和動態規劃）、圖論、決策論、對策論、排隊論、存儲論、可靠性理論等.
規劃論
數學規劃即上面所說的規劃論,是運籌學的一個重要分支,早在1939年蘇聯的康托洛維奇（H.B.Kahtopob ）和美國的希奇柯克（F.L.Hitchcock）等人就在生產組織管理和制定交通運輸方案方面首先研究和應用一線性規劃方法.1947年旦茨格等人提出了求解線性規劃問題的單純形方法,為線性規劃的理論與計算奠定了基礎,特別是電子計算機的出現和日益完善,更使規劃論得到迅速的發展,可用電子計算機來處理成千上萬個約束條件和變數的大規模線性規劃問題,從解決技術問題的最優化,到工業、農業、商業、交通運輸業以及決策分析部門都可以發揮作用.從范圍來看,小到一個班組的計劃安排,大至整個部門,以至國民經濟計劃的最優化方案分析,它都有用武之地,具有適應性強,應用面廣,計算技術比較簡便的特點.非線性規劃的基礎性工作則是在1951年由庫恩（H.W.Kuhn）和達克（A.W.Tucker）等人完成的,到了70年代,數學規劃無論是在理論上和方法上,還是在應用的深度和廣度上都得到了進一步的發展.
數學規劃的研究對象是計劃管理工作中有關安排和估值的問題,解決的主要問題是在給定條件下,按某一衡量指標來尋找安排的最優方案.它可以表示成求函數在滿足約束條件下的極大極小值問題.
數學規劃和古典的求極值的問題有本質上的不同,古典方法只能處理具有簡單表達式,和簡單約束條件的情況.而現代的數學規劃中的問題目標函數和約束條件都很復雜,而且要求給出某種精確度的數字解答,因此演算法的研究特別受到重視.

H. 求C++演算法。。。田忌賽馬擴展版。

有趣的問題，分析分析了半天，貌似不能用很簡單的數學公式計算出來。如果用C語言窮舉，還是比較簡單的，權當交流。

題目分析：
由於是求概率，可以假定齊王的馬永遠是按照順序出的，田忌的馬是任意順序。因此，總共是 N！種可能性。如果田忌需要贏，田忌需要贏 (N+1)/2場，如總共3場，需要贏2場，總共4場，需要贏3場（贏2場是平局）。

按照題目的要求，設定：
齊王的馬的次序：Q[N]
田忌的馬的次序：T[N]
齊王的馬的速度設定為 2n+1, 2(n-1)+1, ..., 1 (0<=n < N)
田忌的馬的速度設定為 2n, 2(n-1), ..., 0 (0<=n<N)

窮舉法：
1）齊王的馬永遠是固定的，Q[n] = 2n+1
2）窮舉田忌所有的排列方法（窮舉的演算法網上應該有現成的），對於每一種排列，比較T和Q的大小，統計輸贏的情況: T[n] > Q[n]的數目大於(N+1)/2
2）將贏的次數處以N!, 就是概率

數學的方式，分析了半天，沒有搞定，不獻丑了。

I. 25匹馬賽跑，共有5個賽道，最少賽多少次可以找出前三名

7次。理由如下:

1、先分開賽5組（A-E）， 5次， 每組的最後兩名肯定會被淘汰，（-10)。

2、5組第一名賽一次，假設A1 > B1 > C1 > D1＞E1，那麼 A1肯定是總體第一名。則D，E全部被淘汰（-6） . 現在需要在剩下的裡面取2個，那麼C2，C3，B3也會被淘汰（-3) 。

3、那麼就剩下A2，A3，B1，B2，C1了，再賽一次，取前兩名（-3)。

最多7次比賽，前5次總共淘汰10匹，第6次淘汰9匹，第7次淘汰3匹。 總共淘汰22匹。

(9)田忌賽馬演算法擴展閱讀

有關賽馬的故事：

齊國的大將田忌，很喜歡賽馬，有一回，他和齊威王約定，要進行一場比賽。各自的馬都可以分為上，中，下三等。比賽的時候，齊威王總是用自己的上馬對田忌的上馬，中馬對中馬，下馬對下馬。由於齊王每個等級的馬都比田忌的馬強一些，所以比賽了幾次，田忌都失敗了。

有一次，田忌又失敗了，覺得很掃興，比賽還沒有結束，就垂頭喪氣地離開賽馬場，這時，田忌抬頭一看， 人群中有個人，原來是自己的好朋友孫臏。孫臏招呼田忌過來，拍著他的肩膀說： 「我剛才看了賽馬，威王的馬比你的馬快不了多少呀。」

孫臏還沒有說完，田忌瞪了他一眼： 「想不到你也來挖苦我！」 孫臏說：「我不是挖苦你，我是說你再同他賽一次，我有辦法准能讓你贏了他。」 田忌疑惑地看著孫臏： 「你是說另換一匹馬來？」 孫臏搖搖頭說： 「連一匹馬也不需要更換。」

田忌毫無信心地說： 「那還不是照樣得輸！」孫臏胸有成竹地說： 「你就按照我的安排辦事吧。」齊威王屢戰屢勝，正在得意洋洋地誇耀自己馬匹的時候，看見田忌陪著孫臏迎面走來， 便站起來譏諷地說： 「怎麼，莫非你還不服氣？」

田忌說：「當然不服氣，咱們再賽一次！」說著，「嘩啦」一聲，把一大堆銀錢倒在桌子上，作為他下的賭錢。 齊威王一看，心裡暗暗好笑，於是吩咐手下，把前幾次贏得的銀錢全部抬來，另外又加了一千兩黃金，也放在桌子上。

齊威王輕蔑地說：「那就開始吧！」 一聲鑼響，比賽開始了。 孫臏先以下等馬對齊威王的上等馬，第一局田忌輸了。齊威王站起來說： 「想不到赫赫有名的孫臏先生，竟然想出這樣拙劣的對策。」 孫臏不去理他。接著進行第二場比賽。

孫臏拿上等馬對齊威王的中等馬，獲勝了一局。 齊威王有點慌亂了。 第三局比賽，孫臏拿中等馬對齊威王的下等馬，又戰勝了一局。這下，齊威王目瞪口呆了。 比賽的結果是三局兩勝，田忌贏了齊威王。 還是同樣的馬匹，由於調換一下比賽的出場順序，就得到轉敗為勝的結果。

這個故事告訴我們:由於其結合變化了，事物的質也會發生變化。在事物發展變化過程中，構成事物的成分在排列次序上發生變化也會引|起事物的質變。這是量變引起質變的又一種形式。

J. C語言里關於田忌賽馬的問題

其實你的演算法很簡單，就是讓淵子的馬按照速度按照從小到大排序，取前1/3為從小到大的順序，然後剩下的2/3按照從大到小排序。
讓對手的馬按照從大到小排序。
這樣你就能保證淵子贏了。