Open meishaoming opened 4 years ago
有64匹马，一共有8个赛道，想要找出最快的4匹马，要比赛最少多少轮才可以?
面腾讯的时候遇到这个问题，面试的时候紧张，答傻了。我回答每次去排除一半，总共要赛：8+4+2+1=15 次。
网上看了下别人的分析，才知道怎么得最优解。把我理解的画在下面：
第一步：每 8 组各赛一场，每场可以排除后面 4 名，剩下 32 匹马。
第二步：第一名赛一场，后四名的组可以直接排除掉了。剩下 16 匹。
分析一下剩下的 16 匹：
剩下还有 9 匹马要比。
观察一下，B 是它左下方格子里最大的。
B 先不比，先拿剩下黄色部分（A1, A2, A3, B1, B2, C, C1, D）比一场：
取这场的前 3 名，其中第一第二肯定是前 4。就看第三名跟 B 的关系了。有两种情况：
在网上搜了一下，酷壳上有这篇：面试题：赛马问题
一共有25匹马，有一个赛场，赛场有5个赛道。最少得比多少场才能知道跑得最快的5匹马？
在评论里看到一个解答，是比第二名的，感觉很猛。不知道照这种方法，上题会不会有更少的解。
64 匹马
面腾讯的时候遇到这个问题，面试的时候紧张，答傻了。我回答每次去排除一半，总共要赛：8+4+2+1=15 次。
网上看了下别人的分析，才知道怎么得最优解。把我理解的画在下面：
第一步：每 8 组各赛一场，每场可以排除后面 4 名，剩下 32 匹马。
第二步：第一名赛一场，后四名的组可以直接排除掉了。剩下 16 匹。
分析一下剩下的 16 匹：
剩下还有 9 匹马要比。
观察一下，B 是它左下方格子里最大的。
B 先不比，先拿剩下黄色部分（A1, A2, A3, B1, B2, C, C1, D）比一场：
取这场的前 3 名，其中第一第二肯定是前 4。就看第三名跟 B 的关系了。有两种情况：
25 匹马
在网上搜了一下，酷壳上有这篇：面试题：赛马问题
在评论里看到一个解答，是比第二名的，感觉很猛。不知道照这种方法，上题会不会有更少的解。