【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《田忌赛马的故事》，欢迎阅读！
田忌赛马的故事 中国国际广播电台 公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 齐国使臣将他引见给齐国的大将军田忌，田忌向孙膑请教兵法，孙膑讲了三天三夜，田忌特别佩服，将孙膑待为贵宾，孙膑对田忌也很感激，经常为他献计献策。 赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 当又一次赛马时，孙膑随田忌来到赛马场，满朝文武官员和城里的平民也都来看热闹。孙膑了解到，大家的马按奔跑的速度分为上中下三等，等次不同装饰不同，各家的马依等次比赛，比赛为三赛二胜制。 孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。 孙膑告诉田忌：“大将军，请放心，我有办法让你获胜。”田忌听后非常高兴，随即以千金作赌注约请国王与他赛马。国王在赛马中从没输过，所以欣然答应了田忌的邀请。 比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马， 与齐王的上等马比赛。比赛开始，只见齐王的好马飞快地冲在前面，而田忌的马远远落在后面，国王得意地开怀大笑。 第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。 关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国 王的马前面，结果二比一，田忌赢了国王。 从未输过比赛的国王目瞪口呆，他不知道田忌从哪里得到了这么好的赛马。 这时田忌告诉齐王，他的胜利并不是因为找到了更好的马，而是用了计策。 随后，他将孙膑的计策讲了出来，齐王恍然大悟，立刻把孙膑召入王宫。孙膑告诉齐王，在双方条件相当时，对策得当可以战胜对方，在双方条件相差很远时， 对策得当也可将损失减低到最低程度。后来，国王任命孙膑为军师，挥指全国的军队。从此，孙膑协助田忌，改善齐军的作战方法，齐军在与别国军队的战争中因此屡屡取胜。 田忌赛马的纯贪心算法 2010-10-11 11:57 算法可以用DP，或者给每匹马连线赋权变为二分图最佳匹配，还有就是贪心了。 1.当田忌最慢的马比齐王最慢的马快，赢一场先 2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场 3.当田忌最快的马比齐王最快的马快时，赢一场先。 4.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场。 5.当田忌最快的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比. 田忌赛马贪心的正确性证明。 先说简单状况下的证明： 1.当田忌最慢的马比齐王最慢的马快，赢一场先。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。 2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。 3.当田忌最慢的和齐王最慢的马慢相等时，分4和5讨论。 4.当田忌最快的马比齐王最快的马快时，赢一场先。因为最快的马的用途就是来赢别人快的马，别人慢的马什么马都能赢。 5.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场，因为反正要输一场，不如拿最没用的马输。 6.当田忌最快的马和齐王最快的马相等时，这就要展开讨论了,贪心方法是，拿最慢的马来和齐王最快的马比. 前面的证明像公理样的，大家一看都能认同的，没有异议的，就不细说了。 本文来源：https://www.dywdw.cn/23a78416f18583d049645992.html
下载此文档
搜索文档
阅读：
文档下载
2023-02-03
