田忌赛马问题

来自计算思维百科
跳转至: 导航搜索
田忌赛马问题1.jpg

田忌赛马问题说的是战国时期,齐威王与大将田忌赛马,田忌智胜齐威王的历史典故。战国时期,齐威王与大将田忌赛马,齐威王和田忌各有三匹马:上马,中马与下马。比赛分三次进行,每次赛马以千金作赌。由于两者的马力相差无几,而齐威王的马分别比田忌相应等级的马要好,所以田忌最后是以怎样的方式赢了齐威王呢?

解决方案

步骤一:若剩下的最强的马都赢不了齐王剩下的最强的马,选择用最差的一匹马对阵齐王最强的马;

步骤二:若剩下的最强的马可以赢齐王剩下的最强的马,选择用这匹马去赢齐王剩下的最强的马;

步骤三:若剩下的马最强的马和齐王剩下的最强的马打平的话,可以选择打平或用最差的马输掉比赛。

根据以上策略,比赛中田忌与齐威王的马安排如下:

田忌赛马问题2.png

涉及的计算思维

我们知道田忌的三匹马没有一匹比齐威王的好,但庆幸的是,每匹马都只能用一次,所以我们要在每场比赛中选择最合适的马去与齐威王的马比赛才有可能取胜。这体现了计算思维中“优化”的特点。