田忌赛马故事

《田忌赛马故事》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、田忌赛马的故事中国国际广播电台      　公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 　　齐国使臣将他引见给齐国的大将军田忌，田忌向孙膑请教兵法，孙膑讲了三天三夜，田忌特别佩服，将孙膑待为贵宾，孙膑对田忌也很感激，经常为他献计献策。 　　赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。

2、孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 　　当又一次赛马时，孙膑随田忌来到赛马场，满朝文武官员和城里的平民也都来看热闹。孙膑了解到，大家的马按奔跑的速度分为上中下三等，等次不同装饰不同，各家的马依等次比赛，比赛为三赛二胜制。 　　孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。孙膑告诉田忌：“大将军，请放心，我有办法让你获胜。”田忌听后非常高兴，随即以千金作赌注约请国王与他赛马。国王在赛马中从没输过，所以欣然答应了田忌的邀请。 　　比赛前田忌按照

3、孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。比赛开始，只见齐王的好马飞快地冲在前面，而田忌的马远远落在后面，国王得意地开怀大笑。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 　　从未输过比赛的国王目瞪口呆，他不知道田忌从哪里得到了这么好的赛马。这时田忌告诉齐王，他的胜利并不是因为找到

4、了更好的马，而是用了计策。随后，他将孙膑的计策讲了出来，齐王恍然大悟，立刻把孙膑召入王宫。孙膑告诉齐王，在双方条件相当时，对策得当可以战胜对方，在双方条件相差很远时，对策得当也可将损失减低到最低程度。后来，国王任命孙膑为军师，挥指全国的军队。从此，孙膑协助田忌，改善齐军的作战方法，齐军在与别国军队的战争中因此屡屡取胜。田忌赛马的纯贪心算法2010-10-1111:57算法可以用DP，或者给每匹马连线赋权变为二分图最佳匹配，还有就是贪心了。1.当田忌最慢的马比齐王最慢的马快，赢一场先2.当田忌最慢的

5、马比齐王最慢的马慢，和齐王最快的马比，输一场3.当田忌最快的马比齐王最快的马快时，赢一场先。4.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场。5.当田忌最快的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比.田忌赛马贪心的正确性证明。先说简单状况下的证明：1.当田忌最慢的马比齐王最慢的马快，赢一场先。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。3

6、.当田忌最慢的和齐王最慢的马慢相等时，分4和5讨论。4.当田忌最快的马比齐王最快的马快时，赢一场先。因为最快的马的用途就是来赢别人快的马，别人慢的马什么马都能赢。5.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场，因为反正要输一场，不如拿最没用的马输。6.当田忌最快的马和齐王最快的马相等时，这就要展开讨论了,贪心方法是，拿最慢的马来和齐王最快的马比.前面的证明像公理样的，大家一看都能认同的，没有异议的，就不细说了。证明：田忌最快的马和齐王最快的马相等时拿最慢的马来和齐王最快的

7、马比有最优解。1）假设他们有n匹马，看n=2的时候.a1a2b1b2因为田忌最快的马和齐王最快的马相等所以a1=b1,a2=b2所以这种情况有2种比赛方式，易得这两种方式得分相等。2）当数列a和数列b全部相等等时(a1=b1,a2=b2...an=bn)，显然最慢的马来和齐王最快的马比有最优解,可以赢n-1长，输1场，找不到更好的方法了。3）当数列a和数列b元素全部相等时(a1=b1=a2=b2...=an=bn)，无法赢也不输。现在假设n匹马时拿最慢的马来和齐王最快的马比有最优解，证明有n+1匹

8、马时拿最慢的马来和齐王最快的马比也有最优解。数列a1a2a3a4...anan+1b1b2b3b4...bnbn+1其中ai>=ai-1,bi>=bi-1数列a和数列b不全部相等时，拿最慢的马来和齐王最快的马比数列得到数列(a1)a2a3a4...anan+1b1b2b3b4...bn(bn+1)分4种情况讨论1.b1=b2,an=an+1则有