田忌賽馬故事

《田忌賽馬故事》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、田忌賽馬的故事中國國際廣播電臺(tái)??????　公元前四世紀(jì)的中國，處在諸侯割據(jù)的狀態(tài)，歷史上稱為“戰(zhàn)國時(shí)期”。在魏國作官的孫臏，因?yàn)槭艿酵琵嬩傅钠群?，被齊國使臣救出后，到達(dá)齊國國都。?　　齊國使臣將他引見給齊國的大將軍田忌，田忌向?qū)O臏請(qǐng)教兵法，孫臏講了三天三夜，田忌特別佩服，將孫臏待為貴賓，孫臏對(duì)田忌也很感激，經(jīng)常為他獻(xiàn)計(jì)獻(xiàn)策。?　　賽馬是當(dāng)時(shí)最受齊國貴族歡迎的娛樂項(xiàng)目。上至國王，下到大臣，常常以賽馬取樂，并以重金賭輸贏。田忌多次與國王及其他大臣賭輸贏，屢賭屢輸。一天他賽馬又輸了，回家后悶悶不樂。

2、孫臏安慰他說：“下次有機(jī)會(huì)帶我到馬場看看，也許我能幫你?！?　　當(dāng)又一次賽馬時(shí)，孫臏隨田忌來到賽馬場，滿朝文武官員和城里的平民也都來看熱鬧。孫臏了解到，大家的馬按奔跑的速度分為上中下三等，等次不同裝飾不同，各家的馬依等次比賽，比賽為三賽二勝制。?　　孫臏仔細(xì)觀察后發(fā)現(xiàn)，田忌的馬和其他人的馬相差并不遠(yuǎn)，只是策略運(yùn)用不當(dāng)，以致失敗。孫臏告訴田忌：“大將軍，請(qǐng)放心，我有辦法讓你獲勝?！碧锛陕牶蠓浅８吲d，隨即以千金作賭注約請(qǐng)國王與他賽馬。國王在賽馬中從沒輸過，所以欣然答應(yīng)了田忌的邀請(qǐng)。?　　比賽前田忌按照

3、孫臏的主意，用上等馬鞍將下等馬裝飾起來，冒充上等馬，與齊王的上等馬比賽。比賽開始，只見齊王的好馬飛快地沖在前面，而田忌的馬遠(yuǎn)遠(yuǎn)落在后面，國王得意地開懷大笑。第二場比賽，還是按照孫臏的安排，田忌用自己的上等馬與國王的中等馬比賽，在一片喝彩中，只見田忌的馬竟然沖到齊王的馬前面，贏了第二場。關(guān)鍵的第三場，田忌的中等馬和國王的下等馬比賽，田忌的馬又一次沖到國王的馬前面，結(jié)果二比一，田忌贏了國王。?　　從未輸過比賽的國王目瞪口呆，他不知道田忌從哪里得到了這么好的賽馬。這時(shí)田忌告訴齊王，他的勝利并不是因?yàn)檎业?/p>

4、了更好的馬，而是用了計(jì)策。隨后，他將孫臏的計(jì)策講了出來，齊王恍然大悟，立刻把孫臏召入王宮。孫臏告訴齊王，在雙方條件相當(dāng)時(shí)，對(duì)策得當(dāng)可以戰(zhàn)勝對(duì)方，在雙方條件相差很遠(yuǎn)時(shí)，對(duì)策得當(dāng)也可將損失減低到最低程度。后來，國王任命孫臏為軍師，揮指全國的軍隊(duì)。從此，孫臏協(xié)助田忌，改善齊軍的作戰(zhàn)方法，齊軍在與別國軍隊(duì)的戰(zhàn)爭中因此屢屢取勝。田忌賽馬的純貪心算法2010-10-1111:57算法可以用DP，或者給每匹馬連線賦權(quán)變?yōu)槎謭D最佳匹配，還有就是貪心了。1.當(dāng)田忌最慢的馬比齊王最慢的馬快，贏一場先2.當(dāng)田忌最慢的

5、馬比齊王最慢的馬慢，和齊王最快的馬比，輸一場3.當(dāng)田忌最快的馬比齊王最快的馬快時(shí)，贏一場先。4.當(dāng)田忌最快的馬比齊王最快的馬慢時(shí)，拿最慢的馬和齊王最快的馬比，輸一場。5.當(dāng)田忌最快的馬和齊王最快的馬相等時(shí)，拿最慢的馬來和齊王最快的馬比.田忌賽馬貪心的正確性證明。先說簡單狀況下的證明：1.當(dāng)田忌最慢的馬比齊王最慢的馬快，贏一場先。因?yàn)槭冀K要贏齊王最慢的馬，不如用最沒用的馬來贏它。2.當(dāng)田忌最慢的馬比齊王最慢的馬慢，和齊王最快的馬比，輸一場。因?yàn)樘锛勺盥鸟R始終要輸?shù)模蝗缬盟鼇硐凝R王最有用的馬。3

6、.當(dāng)田忌最慢的和齊王最慢的馬慢相等時(shí)，分4和5討論。4.當(dāng)田忌最快的馬比齊王最快的馬快時(shí)，贏一場先。因?yàn)樽羁斓鸟R的用途就是來贏別人快的馬，別人慢的馬什么馬都能贏。5.當(dāng)田忌最快的馬比齊王最快的馬慢時(shí)，拿最慢的馬和齊王最快的馬比，輸一場，因?yàn)榉凑斠粓?，不如拿最沒用的馬輸。6.當(dāng)田忌最快的馬和齊王最快的馬相等時(shí)，這就要展開討論了,貪心方法是，拿最慢的馬來和齊王最快的馬比.前面的證明像公理樣的，大家一看都能認(rèn)同的，沒有異議的，就不細(xì)說了。證明：田忌最快的馬和齊王最快的馬相等時(shí)拿最慢的馬來和齊王最快的

7、馬比有最優(yōu)解。1）假設(shè)他們有n匹馬，看n=2的時(shí)候.a1a2b1b2因?yàn)樘锛勺羁斓鸟R和齊王最快的馬相等所以a1=b1,a2=b2所以這種情況有2種比賽方式，易得這兩種方式得分相等。2）當(dāng)數(shù)列a和數(shù)列b全部相等等時(shí)(a1=b1,a2=b2...an=bn)，顯然最慢的馬來和齊王最快的馬比有最優(yōu)解,可以贏n-1長，輸1場，找不到更好的方法了。3）當(dāng)數(shù)列a和數(shù)列b元素全部相等時(shí)(a1=b1=a2=b2...=an=bn)，無法贏也不輸?，F(xiàn)在假設(shè)n匹馬時(shí)拿最慢的馬來和齊王最快的馬比有最優(yōu)解，證明有n+1匹

8、馬時(shí)拿最慢的馬來和齊王最快的馬比也有最優(yōu)解。數(shù)列a1a2a3a4...anan+1b1b2b3b4...bnbn+1其中ai>=ai-1,bi>=bi-1數(shù)列a和數(shù)列b不全部相等時(shí)，拿最慢的馬來和齊王最快的馬比數(shù)列得到數(shù)列(a1)a2a3a4...anan+1b1b2b3b4...bn(bn+1)分4種情況討論1.b1=b2,an=an+1則有