有趣的算法-赛马问题

问题描述

64匹马，8个跑道，问最少比赛多少场，可以选出跑得最快的4匹马。每场比赛每个跑道只允许一匹马，且不存在并列情形

问题分析

第一步：先让马儿跑起来，首先将马儿分批次赛跑，一共需要进行8次赛跑。假设结果如下：

分组	第一名	第二名	第三名	第四名	第五名	第六名	第七名	第八名
A	A1	A2	A3	A4	A5	A6	A7	A8
B	B1	B2	B3	B4	B5	B6	B7	B8
C	C1	C2	C3	C4	C5	C6	C7	C8
D	D1	D2	D3	D4	D5	D6	D7	D8
E	E1	E2	E3	E4	E5	E6	E7	E8
F	F1	F2	F3	F4	F5	F6	F7	F8
G	G1	G2	G3	G4	G5	G6	G7	G8
H	H1	H2	H3	H4	H5	H6	H7	H8

可直接排除各组最后四名赛马，剩余64-4*8=32匹赛马待定

第二步：将每一组中的第一名进行赛跑(如果每一组选多个参加赛马，那样就存在重复比赛)，需要进行1次赛跑。假设结果如下：

分组	第一名	第二名	第三名	第四名	第五名	第六名	第七名	第八名
1	A1	B1	C1	D1	E1	F1	G1	H2

可直接排除各组最后四名赛马，也就是后四组全部淘汰，剩余 32 - 4 * 4 = 16，其中第一名已经知道就是A1

需要注意的是：这里还可以继续排除

1. 因为在头名争夺中 D1只能排第四，所以D1最快也是第四，D组剩余被淘汰
2. 同理C组最多只有2名在前4
3. 同理B组最多只有1名在前4

分组	第一名	第二名	第三名	第四名
A	A1	A2	A3	A4
B	B1	B2	B3	B4
C	C1	C2	C3	C4
D	D1	D2	D3	D4

所以剩余需要确认的数量为 16 - 1 - 3 - 2 - 1 = 9。

第三步：剩余的9匹赛马中需要选出8匹马再次进行一次赛马

这里是否有一匹特殊的马，不需要参与赛跑进行这一次赛马就能得出结果？

1. 排除A组中的3匹马中的一匹，那么除非B1都输或者都赢，否则B1以及后面的排名不确定。也就是排除前面的对后面影响较大
2. 排除D1/C2，那么可能无法确认D1与C2谁是第四
3. 排除C1与排除其他一样，可能无法确认自己和它身后的排名

所以，这里最好从D1与C2中排除一个进行赛跑，如果这一轮得出结果，那么就不用跑。如果没有得出结论就再跑一次

因为所有赛马的第一名已经确认是第一，所以剩下的比赛就是确认 2 - 4 名次，C1要是所有赛马的前四名，这次必须跑入前三。

第一种可能：C1第三名或者第三名之后，那么比赛结束，一共经过了 8 + 1 + 1 = 10 赛出前四名

第二种可能：C1排在第二名，也就是说 C2 和 D1 无法确认谁是第四个，那么就需要加赛一场。排除前三，剩余的马再比一场。一共经过了 8 + 1 + 1 + 1 = 11

参考文档

1. https://zhuanlan.zhihu.com/p/103572219