找出最快的3匹马

来自计算思维百科
跳转至: 导航搜索
找出最快的3匹马.jpg

有25匹马,速度都不同,但每匹马的速度都是定值。现在只有5条赛道,无法计时,即每赛一场最多只能知道5匹马的相对快慢。问最少进行几场比赛可以找出25匹马中速度最快的前3名?

解决方案-分治法

为了公平起见,每匹马都至少有一次参赛机会。所以把25匹马分成五组,每组5匹马,首先每组的五匹马进行比赛,得到每组的冠军,然后每组冠军再进行比赛,那么冠军就是五组冠军中的最快的一匹马。到此,一共比了6场,我们已经得到冠军的马。

接下来需要找出第二名和第三名。现在将第六次比赛的五匹马所在的组按照第六次的比赛排名编号如下,组内也按照组排名编号:

A:1 2 3 4 5(第一名所在组)

B:1 2 3 4 5(第二名所在组)

C:1 2 3 4 5(第三名所在组)

D:1 2 3 4 5(第四名所在组)

E:1 2 3 4 5(第五名所在组)

那么可能成为第二名第三名的只有A组的2、3,B组的1、2,C组的第一名。因此取这五匹马进行第7场比赛,分出亚军和季军,所以一共需要进行7场比赛才能在25匹马中找出前三名。

运用的计算思维

对25匹马进行分组,再对分组结果进行排名是分而治之的思想,分治法对于规模很大的问题很有效果。六场比赛完毕后,利用贪心法的思想从中选择5匹最有潜力的马进行比赛,从而高效率地只进行7场比赛就找出了前三名。运用了“分解”和“优化”的计算思维。

参考文献

(百度2008面试题)