64匹马，8个赛道。找出前4名最少比赛多少场（概率分析+验证代码）
先上结论：
如果需要明确前四的顺序：有92/93（约为98.92%）的概率只需要十场比赛，1/93（约为1.08%）的概率需要进行第十一场。
如果不必明确前四的顺序：有16963/17091（约为99.67%）的概率只需要十场，56/17019（约为0.33%）的概率需要进行第十一场。
第一步：全部马分8组，各跑一次（共8次）
第二步：取每组第一名进行一次比赛（共1次）
分析：
1、按照第二步（每组第一名）比赛结果的名次，对各组进行排序，即：第一名所在组为A组，第二名所在组为B组，以此类推
2、每一组根据第一步比赛结果进行排序，如A组第一名为A1，第二名为A2，以此类推
3、E、F、G、H这四组不可能有前四（因为已经有A1、B1、C1、D1比它们快）
4、每一组的5号以后不可能是前四（因为同一组前四名比它们快）
5、D2不可能是前四，因为有A1、B1、C1、D1比它快，以此类推，D3、D4、C3、C4、B4不可能是前四
6、A1是最快的
综上，A1已经晋级，只需要从A2、A3、A4、B1、B2、B3、C1、C2、D1中取前三，就能得到前四
马有九匹，赛道只有八条，要怎样安排第十场？这是需要讲究的事情。安排好了，可以最大限度地避免进行第十一场。
第三步：取A2、A3、B1、B2、B3、C1、C2、D1进行一次比赛（共1次）
结果分两种：
A、如果前三名按从快到慢顺序为A2、A3、B1，那么还不知道A4和B1谁快，需要进行一次加赛，A2、A3、A4、B1取前三（附加1次）
B、其他情况，则A1+前三名为前4名
结论：按照以上安排，有92/93（约为98.92%）的概率只需要十场比赛，1/93（约为1.08%）的概率需要进行第十一场。
以下是 python 代码。运行结果印证了以上分析。
import random
class Horse:
def __init__(self):
self.reset()
def reset(self):
self.counter = 0
self.values = []
for x in range(64):
self.values.append(random.randint(1000,9999)*100+x)
def check_best(self, indexes):
best = self.best()
for x in range(4):
if indexes[x] != best[x]:
return False
return True
def count(self):
return self.counter
def best(self):
return sorted(range(64), key=lambda x: self.values[x], reverse=True)[0:4]
def sort(self, indexes):
self.counter = self.counter + 1
return sorted(indexes, key=lambda x: self.values[x], reverse=True)
def get(self, indexes):
return [(x, self.values[x]) for x in indexes]
def get_best(horse):
values = [horse.sort([k + x*8 for k in range(8)]) for x in range(8)]
index = [x // 8 for x in horse.sort([n[0] for n in values])]
serial = [values[x] for x in index]
second = [serial[y][x] for x in range(4) for y in range(4-x)]
best = [second[0]]
items = horse.sort(second[1:9])[0:3]
if serial[1][0] == items[2]:
items.append(serial[0][3])
items = horse.sort(items)[0:3]
best.extend(items)
return best
if __name__ == '__main__':
rept = 100000
horse = Horse()
count = 0
for x in range(rept):
horse.reset()
best = get_best(horse)
count = count + horse.count()
if not horse.check_best(best):
print(f'ERR :{horse.get(best)}')
print(f'best:{horse.get(horse.best())}')
print(f'average: {count/rept}')注：reset 里的 random.randint(1000,9999)*100+x 是为了让每个值都不相同。当然也可以用 range(64) 再进行洗牌。
--------------------------------------------------------------------------------
如果只要找出前四，不必整理出顺序，第三步也可以：
第三步：取A2、A3、A4、B2、B3、C1、C2、D1进行一次比赛（共1次）
结果分两种：
A、前三为A2、A3、A4。那么还不知道B1是不是更快，需要进行一次加赛，A2、A3、A4、B1取前三（附加1次）
B、其他情况，必然包含B2或C1，它们都比B1慢，所以，只要取A1、B1和第十轮的前两名，即为前四（这种情况无法确定二、三、四名的顺序）
这种情况的概率为：有16963/17091（约为99.67%）的概率只需要十场，56/17019（约为0.33%）的概率需要进行第十一场。
Python 代码如下。运行结果印证了以上分析。
import random
class Horse:
def __init__(self):
self.reset()
def reset(self):
self.counter = 0
self.values = []
for x in range(64):
self.values.append(random.randint(1000,9999)*100+x)
def check_best(self, indexes):
best = self.best()
for x in range(4):
if indexes[x] != best[x]:
return False
return True
def count(self):
return self.counter
def best(self):
return sorted(range(64), key=lambda x: self.values[x], reverse=True)[0:4]
def sort(self, indexes):
self.counter = self.counter + 1
return sorted(indexes, key=lambda x: self.values[x], reverse=True)
def get(self, indexes):
return [(x, self.values[x]) for x in indexes]
def get_best(horse):
values = [horse.sort([k + x*8 for k in range(8)]) for x in range(8)]
index = [x // 8 for x in horse.sort([n[0] for n in values])]
serial = [values[x] for x in index]
second = [serial[y][x] for x in range(4) for y in range(4-x)]
best = [second[0]]
second[1], second[9] = second[9], second[1]
items = horse.sort(second[1:9])[0:3]
if serial[0][3] == items[2]:
items.append(serial[1][0])
items = horse.sort(items)[0:3]
else:
items = [serial[1][0], items[0], items[1]]
best.extend(items)
return best
if __name__ == '__main__':
rept = 100000
horse = Horse()
count = 0
for x in range(rept):
horse.reset()
best = get_best(horse)
count = count + horse.count()
best = horse.sort(best)
if not horse.check_best(best):
print(f'ERR :{horse.get(best)}')
print(f'best:{horse.get(horse.best())}')
print(f'average: {count/rept}')注：以校验前多了一行 best = horse.sort(best)，是因为前四的顺序没有明确，所以在校验前要先对结果进行排序。
概率计算公式编辑太麻烦，直接上照。
第一种情况可以继续简化成：前三名在同一组。有兴趣可以自己列公式。
（可以鼓掌了）
本文地址：https://blog.csdn.net/amoyman/article/details/110421314