腾讯面试题答案：64匹马8个跑道最少需要多少轮才能选出最快的4匹马？

先说结论：

1. 计时的情况下需要比赛8轮；

2.不计时的情况下最少需要10轮，最多需要11轮。

分析：

情况一：计时。

共有64匹马，8个跑道，每个跑道一次只能跑一匹马，在计时的情况下，只需让64匹马全部跑完并记录每匹马跑完全程的时间即可，用时最少的4匹马就是跑的最快的四匹马，这样只需比赛8轮，64匹马就能全部跑完，选出最快的4名。

情况二：不计时。

第一步：把64匹马分8组，各跑一次，然后淘汰掉每组的后四名，这里淘汰后四名是因为只需要跑的最快的四匹马。（花费8轮）；

第二步：取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，因为后四名所在的组的第一名没有跑过前四名的马，所以可以直接淘汰。（+1轮）；

这时候还剩下16匹马，在这里其实可以继续淘汰，因为D1是第九轮的第四名，但D1又是它3所在组的第一名，那么对应的D2，D3，D4都可以继续淘汰掉。但是第四名也可能出现在C2中，C2是所在组的第二名，那么C3，C4也可以淘汰了，同理，可以得到B4也可以淘汰了。到此为止还剩10匹马，其中A1是64匹马中跑的最快的马，可以直接晋级。如下图，其中有红色斜线是已经被pass的：

第三步：A2、A3、A4、B2、B3、C1、C2、D1八匹马跑一次，即：在剩下需要排名的马中，除了B1外，其它8匹马跑一次（+1轮）

分类讨论：

1、如果这次排名，B2或C1能进前三名，则加上B1后，B1一定能进前三名，因为B1 排名比B2和C1都要靠前；

到此比赛可以结束了；这种情况8+1+1＝10次出结果；

2、如果这次排名，B2或C1不能进入前三名，则需要再进行一次比赛，B1、A2、A3、A4进行，取前三名：

这种情况8+1+1+1=11次出结果。

结论：

1. 计时的情况下需要比赛8轮；

2.不计时的情况下最少需要10轮，最多需要11轮。

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_44756792/article/details/103851500
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-02 18:06:46
阅读 ( 2325 )
分类：面试题