前言

昨天看到 TingRongGao 大佬发了关于一道算法题的一篇文章,觉得着实有趣,但不知为何我看到题后首先想到的是田忌赛马。今天我也试着解释下这题,当做是一个学习的过程。

解题过程

题目:64 匹马,8 个赛道,找出前 4 名最少比多少场?(马的速度恒定不变)

直接开始

第一轮

64 匹马分 8 次在全部比完一次,然后我们可以把目标缩小到 32 匹马。

第一轮解析

1、八次比完后,我们可以将每一匹马的速度按下表排好。

2、每组比赛的后 4 名直接淘汰(小组中都无法进前四,全部中必然无法进前四);


到现在为止,已经进行了 8 次比赛

第二轮

剩下的 8 组 32 匹马选每组的第一名进行一次比赛,然后我们可以把目标缩小到 10 匹马。

第二轮解析

1、8组中第一名比完后(假设 A1 表示最快的,依次为较慢者,H1最慢),这次比赛直接影响到它们这组是否可以参加下一场的比赛,因为每组的第一都进不了前四的话那这组肯定就没有前四的马啦。

2、所以这轮比赛的后四名直接全组淘汰,剩下 16 匹马。

3、先别急着进行下一场的比赛,因为这里面还可以淘汰 6 匹马。

D 组第一名 D1 都最多只是第四名,所以 D2、D3、D4 就不需要再比了;C 组第一名 C1 最好成绩是第三名,所以只有 C2 可以冲一下第四名,C3、C4 淘汰;B 组第一名 B1 最好成绩是第二名,所以 B2、B3 还是有机会进前 4 的,B4 淘汰;A 组就运气比较好,全组都可能进前 4 。
现在只有 10 匹马的范围啦。

即剩 A1、A2、A3、A4、B1、B2、B3、C1、C2、D1 十匹马可能进前四。

到现在为止,已经进行了 9 次比赛

第三轮

A1 必定是第一名无需再比。B1 这个暂定第二的基本不需要再比,所以剩下的 A2、A3、A4、B2、B3、C1、C2、D1 这八匹马再比一次。

第三轮解析(情况有二)

1、这轮比赛如果 B2 或 C1 中二者有其一进入前三,那比赛结束,前四名已经区分出来。(这点想不明白的话你想想这个问题:跑步比赛中你跑过了第二名你是第几名)

我们知道 B1 在 BCD 三组中肯定是最快的,所以 B2 或 C1 进入前三,B1 就一定再前四。

若结果为: A2>B2>C1>C2>D1>A3>A4>B3
那么前四就是 A1、A2、B1、B2(A2、B1 的名次不知)

2、如果比赛的前三戏剧性的是 A2、A3、A4,那么我们是不清楚 A4 快还是 B1 快的,所以需要在比一场,就能找出前四。

情况一:8 + 1 + 1 = 10, 共 10 次
情况二:8 + 1 + 1 + 1 = 11,共 11 次

总结

64 匹马,8 个赛道,找出前 4 名最少需要比 10 场。