64匹马，8个赛道，最少多少次比赛找出最快的 4 匹马，以及对所有马进行排序

大家好，我是讯享网，很高兴认识大家。

问题：64匹马，8个赛道，最少几场比赛找出最快的 4 匹马，最少几场对所有马进行排序

问题一：64 匹马，8 个赛道，最少几场比赛找出最快的 4 匹马

问题中隐含的意思：
1、就是每次比赛马的时间不计，只对比赛的马进行快慢排名，在一次比赛中 A 马比 B 马快，那就认为它就是比 B 马快。
2、只需要找出最快的 4 匹马，不需要知道顺序。

从中可以得出淘汰原理：
1、一匹马 A 在一次比赛中获得名次 n，那他在 64 匹马中最好可能的排名就是 n（因为已知就有 n - 1 匹马比它快）
2、任意一次比赛，只要排名在第五及以后的马，可以直接淘汰
3、如果一匹马 A 在一次比赛中获得第四名，那么已知比 A 慢的马可就都可以淘汰了（很有用）

算法步骤分为以下 4 步：

第一步：淘汰一半，64 进 32（共 8 场比赛）

第一步就是最正常的八场比赛，每场比赛淘汰后四名，也就是 64 进 32，如下图（灰色就是淘汰了的）。
在这里插入图片描述
讯享网
值得注意的是，上图中的每一列，从上到下有序排列，列与列之间没有关系，也就是 A8 可能比 B1 还快。

第二步：每组第一名进行比赛，32 进 10（共 1 场比赛）

第一步之后淘汰了一半，我们对上边八场比赛的 8 个第一名进行一次比赛，根据上边的淘汰原理3，后四组都可以直接淘汰了，而且，可以淘汰不止后 16 匹。我们将前四组按照第一名在这一轮比赛中的排名进行排序，得到下图（其中 A1 > B1 > C1 > D1，’>’ 就是快的意思）：
在这里插入图片描述可以发现，既然同样根据淘汰原理3，既然 D1 已经比 A1、B1、C1 都慢了，它最好排名就是 64 匹中的第四了，那么 D2、D3、D4 都可以直接淘汰了。同理淘汰 B4、C3、C4。剩下 10 匹。

第三步：可能可以结束（共 1 场比赛）

第四步：一定结束（共 1 场比赛）

同理，36 个赛车，6 个跑道，最少 8 次找出前三（情况比这道题还简单，不用分类讨论）。

问题二：64 匹马，8 个赛道，最少多少次比赛对所有马进行排序

第一步：8 场比赛

在这里插入图片描述
首先还是排成 8 * 8 的方阵，每一列进行一场比赛，并从上到下排序，如上图，每一列从上到下，从快到慢；列与列之间没有关系。这样我们就得到了 8 个第一名（A1、B2、C1 … H1）和 8 个最后一名（A8、B8、C8 … H8），但是我们还是不知道任意一匹马的确定名次。

第二步：循环，每 4 场决出 8 个名次（4 个前边的，4 个倒数的）（共 4 * 7 = 28 场）

我们让 8 个第一名进行一场比赛，8 个最后一名进行一场比赛，就决出了第 1 名和第 64 名，并且把第一行和最后行按照它们的第一名在这一轮中的名次从左到右排序，如下图（每一列的第二行到第七行，依然是从上到下，从快到慢；第一行和最后一行，从左到右，从快到慢），也就是 A1 是总体第一名，H8 是总体倒数第一名：
在这里插入图片描述那么可以看出，现在第二名的候选马就只有 B1 和 A2 了，倒数第二的候选马也只有 G8 和 H7 了。那么我们选 A2、B1、B2、C1 这四匹马以及 H7、G7、G8、F8 这四匹马组成八匹马进行一场比赛，这样我们一定能确定第 2 名和第 63 名。
因为这一场比赛第一名只可能是 A2 或者 B1（因为其他所有马，已知比它们快的就至少有两匹了，A2 或者 B1 已知只有 A1 比它们俩快），所以分类讨论一下可以得出：第三名、第四名的候选马不超过 4 匹

如果 A2 获胜，第三名的候选马是 A3、B1，第四名的候选马是 A4 以及 B2、C1两个中较快的一个（这两匹在上边的比赛中已经比过了）；
如果 B1 获胜，第三名的候选马就已经知道了，是 A2、B2、C1 三匹马中最快的（也就是为什么要选上边橙色框的四匹马进行比赛）：
如果是 A2 最快，第四名的候选马是 A3 以及 B2、C1 中较快的；
如果是 B2 最快，第四名的候选马是 B3 以及 A2、C1 中较快的；
如果是 C1 最快，第四名的候选马是 A2、B2 中较快的以及 C2、D1。

同理可得，倒数第三倒数第四的候选马，也不超过4匹，那么我们就可以让这些马放在一起，再赛一场，这样就知道第三、第四、倒数第三、倒数第四的是哪些马了，至此，我们就确定了前四名的马和最后四名的马。
上边一共进行了 4 场比赛，每组第一一场，每组最后一名一场，确定第二、倒数第二一场，确定第三、第四、倒数第三、第四一场，接下来就是重复这个循环，每组（每一列）剩余马中，最快的 8 匹一场，最慢的 8 匹一场，确定没有确定的该排名的马中，最快的和最慢的，接下来两场确定没有确定排名的马中第二、第三、第四、倒数第二、倒数第三、倒数第四（一共 8 个名次）；这样一共循环 7 次，也就是 7 * 4 = 28 场之后，就确定了 7 * 8 = 56 个名次。
1 场比赛，最后 8 匹马

进行上述过程之后，最后还剩 64 - 56 = 8 个名次没有确定，那最后剩下的没有名次的 8 匹马赛一次，就全部都确定了。也就是说，一共进行了 8 + 4 * 7 + 1 = 37 场比赛，确定了所有 64 匹马的名次。