娱乐 每 周 概 率 挑 战 【第一期】 解答

[yhz012]

原题链接：

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/

 

已有的优质答案：

引用

 

第一问答案：

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13270708 @applebird

 

第二问答案：

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13270768 @Mr.K 018

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13270777 @Felix_

 

第三问答案：

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13270786 @Mr.K 018

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13270759 @久帝

 

第四问第五问关键信息：

https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/?do=findComment&comment=13276795 @可洛

 

 

第一问实际上等价于求参拜客踩到各个台阶上的概率，然后选取概率最大的台阶挖坑即可。

为了方便，我们不妨假设还有-1、-2、-3、-4、-5层台阶。现在已知参拜客最开始必然出现在0号台阶。因此我们可以初始化概率

P[0] = 1
P[-5: 0] = 0

考虑参拜客在台阶i上，下一步会有各P / 6出现在i+1到i+6上。把这个想法重复6次，我们即可得到参拜客出现在台阶j上的概率是由j-6到j-1这6个台阶的概率的1/6组成的，即：

P[j] = sum(P[j - 6 : j]) / 6

现在我们有了初始状态和递推公式，即可把全部100层台阶的概率全写出来

def forward(startIndex, initP)
  for index in range(startIndex, 101):
    initP[index] = sum(initP[index - 6 : index]) / 6

P[0] = 1
P[-5: 0] = 0
P = forward(1, P)

接下来只要找到这里面的最大值在哪即可

return argmax(P[1 : 101])

 

第二问因为早苗可以挖2个坑，而参拜客只有1条命，那么实际上坑到参拜客只有2种情况：1. 参拜客被第一个陷阱坑了， 2. 参拜客躲过了第一个陷阱但是被第二个坑了。这两个事件是互斥事件，因此被坑的概率可以直接求和

所以最暴力的方案就是我们搜索所有可能的2个坑的情况，即：

for index1 in range(1, 101):
  for index2 in range(index1 + 1, 101):
    p1 = #TODO
    p2 = #TODO
    prob = p1 + p2

情况1可以直接参考第一问，列出参拜客走到各台阶的概率。

p1 = P[index1]

情况2会麻烦一些，因为我们需要先保证参拜客没有走到前一个陷阱，因此我们新开一个数列计算。显然在index1之前的概率不会有影响，但是index1的概率我们需要强制置为0来保证参拜客没有走到这个台阶上，随后我们可以继续进行递推公式

def evade(index, P):
  newP = copy(P)
  newP[index] = 0
  newP = forward(index1 + 1, newP)
  return newP

newP = evade(index1, P)
p2 = newP[index2]

接下来就是找到使得prob最大的index1和index2即可

if prob > tempMaxProb:
  tempMaxProb = prob
  tempMaxIndex = (index1, index2)

 

第三问实际上就是第二问的推广，最坏情况下我们可以用index1到index5建立5重循环，暴搜就好了

 

第四问我们有5个坑，但是参拜客有2条命。我们把情况分解来看，参拜客可能踩到12,13,14,15,23,24,25,34,35,45。总计10种情况，且每种情况都是互斥的，所以还是直接都加起来就好了（笑）

实际上我们可以把这些情况稍微整理下。考虑第一个坑踩到的是1，那么为了坑到参拜客，参拜客必须要在2345里面踩到1个。同理，如果第一个坑是2（即参拜客躲开了1），那么必须在345里踩一个。如果第一个是3（即躲开了12），那么必须踩45里的一个。如果是第一个是4,（躲开了123），那么必须要踩5。

作为举例，我们考虑情况第一个是3,（躲开了12），接着在45里踩一个。

首先我们要求参拜客确实第一个踩的是3的概率p3：

for index1 in range(1 : 101):
  for index2 in range(index1 + 1 : 101):
    for index3 in range(index2 + 1 : 101):
      for index4 in range(index3 + 1 : 101):
        for index5 in range(index4 + 1 : 101):
          prob1 = #TODO: case 1 + 2345
          prob2 = #TODO: case 2 + 345

          newP1 = evade(index1, P)
          newP2 = evade(index2, newP1)
          p3 = newP2[index3]
          p34 = #TODO
          p35 = #TODO
          prob3 = p3 * (p34 + p35)

          prob4 = #TODO: case 4 + 5
          prob = prob1 + prob2 + prob3 + prob4

接下来变成了假定参拜客确实踩在了3上，给定这个条件，实际上我们并不需要再去考虑之前参拜客踩过哪里了，因为这些信息不再影响下一步参拜客踩在哪的概率。形象一点的说法，就像我们知道参拜客最开始在0号台阶上，我们不会关心他是坐着幻想乡里不存在的公交车，还是从紫maslkdjflw的隙间里过来来到0号台阶的，因为之后无论如何，他都是1/6概率走到123456号台阶上。同样的道理也在index3上有效，之后无论如何，他都是1/6的概率走到了index3 + 123456上。我们在某种意义上可以把index3视作新的“0号台阶”。

def trap(index):
  newP[index] = 1
  newP[index - 5 : index] = 0
  newP = forward(index + 1, newP)
  return newP

newP3 = trap(index3)

那么之后的问题就变成了在newP3的分布上，参拜客要么踩到4，要么躲开了4踩到5的概率：

p34 = newP3[index4]
newP4 = evade(index4, newP3)
p35 = newP4[index5]

同样的道理用在其他的情况上，最后再找到使得prob最大的index就完成了。

 

第五题其实就是第四题的推广。我们的情况变成了1 + 2 + 345， 1 + 3 + 45， 1 + 4 + 5， 2 + 3 + 45， 2 + 4 + 5， 3 + 4 + 5 这6大种情况了

五月 11, 2020，由yhz012修改

[久帝]

3问第一反应就是23456

后来继续验证的时候发现绊34567好像和23456一样 一个26活一个16活

但是仔细一想多了一个116那就不用继续验证了233

[yhz012]

1 小时前, 久帝 说道:

3问第一反应就是23456

后来继续验证的时候发现绊34567好像和23456一样 一个26活一个16活

但是仔细一想多了一个116那就不用继续验证了233

我以为会卡住一部分人的问题居然反倒直接被猜出来了，而且逻辑是如此清晰流畅，岂可修233