64匹马赛跑问题

这题是我之前一段时间在网上看到的一道面试的思维题，题目的描述大致如下：

现有64匹马，8条赛道，如何用最少的比较次数找出最快的4匹

刚看到这道题时，我在想如果有计时器的话，64匹马分8组跑，找出时间最短的4匹就可以了吧，这样的话就只需要进行1次对于时间长短的比较。而严格来说的话分8组跑可以算是8次比较，那么最少就算8次吧。可是题目的解答并没有那么简单，因为按照其他人的说法，这次赛跑并没有“计时器”，也就无法直接得知8组间最快4匹是哪4匹

那么这就需要思维拐下弯了

首先先让64匹马分8组进行赛跑。此时进行了8次比较

接着让8组中每组的第1名跑一次，按照跑出来的名次对刚刚分出的8组进行排序，组别的名次和该组第1名本次赛跑的名次一致。此时进行了9次比较

完成了以上的8组排序后，由于需要决出的是最快的4匹，那么最快的4匹不可能是在排名后4位的组别中产生（后4组的第1名都排不到前4，更不要说后4组中其他名次的马了），所以后4组所有马舍去

这时剩下了前4组的32匹马，而由于需要的是最最快的4匹马，那么前4组中每组的后4名也不会是最快的4匹（既然都不是本组的前4名，就更不可能是所有马中的前4名了），所以前4组中所有后4名的马舍去，这时剩下了16匹马

这时看到排名第4的组别中的前四名，由于该组的第1名仅在所有组第1名的马中排第4，那么第4组的2到4名就不可能是前4，所以可以将第4组中第2到4名的马舍去

对于第3组的前4名来说，由于该组的第1名可以排到所有组第1名的马中的第3，那么跟随其后的该组第2名就有可能是第4，但其后的3、4名就不可能是所有马中的前4了，所以可以将第3组中3、4名的马舍去

对于第2组的分析也是类似：既然第2组的第1名可以在所有组第1名排到第2，那么跟随其后的该组第2、3名就有可能是所有马中的第3、4名，而该组的第4名就不可能是所有马的前4，所以舍去第2组中4名的马

对于第1组的剩余4匹马，由于该组第1名是所有组第1最快的，所以其后3匹马可能是所有马前4中的马，不用舍去

此时剩余的马匹数量为10匹（1组4匹，2组3匹，3组2匹、4组1匹）

由于第1组的第1名是所有第1名中最快的，可以确定第1组的第1名就是所有64匹马中最快的了，也就是说第1名确定下来为第1组的第1名，那么就需要在剩余9匹马中决出前3

由于只有8条赛道，为了尽量减少比较次数，将剩余9匹中除去第1组第4名的8匹进行1次比较，根据第1组第3名的名次再决定是否将第1组第4名与其他马比较（此时是第10次比较）：

如果经过这次比较，第1组第3名名次在前2名，那么第1组第4名就有可能是剩余9匹马的前3名，这就需要将第1组第4名和第10次比较后非第1的7匹马比较，这8匹马决出的前2名就是剩余的所有马中的第3、第4名（此时是第11次比较）

如果经过第10次比较，第1组第3名没有在前2名，则不需要让第1组第4名参与比较，也就不需要第11次比较了，此时第10次比较的前3名就是所有马中的第2到4名

综上，需要至少10或11次的比较