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