囚徒问题(100 prisoners problem)的python验证

　　密码学课上老师介绍了这样一个问题，囚徒问题(100 prisoners problem)：一百个囚徒被关在牢房里，典狱长给他们最后一次机会，100人依次进入一个有100个抽屉的牢房，每个抽屉置乱放入1~100的号码，每个人依次打开50个抽屉，如果每个人都能找到自己的号码(0~100)，则所有人被释放，反之所有人都会被杀死。

　　典型的算法给出的被释放概率几乎为零，但是有这样一种方法：第i号囚徒打开第i号抽屉，如果这个抽屉放的是自己的号码牌，ok pass，如果不是，则打开该抽屉中号码牌对应的抽屉，依次进行，直到找到自己的号码牌或者失败。

　　那么，这个方法的成功率有多少呢。使用python模拟的代码如下：

import random

flag = 0    # 单次实验是否成功flag

counter = 0     # 实验成功次数counter

fcounter = 0    # 单个囚徒打开抽屉次数fcounter

N = 10000   # 设置试验次数

A = list(range(100))

random.shuffle(A)   # 抽屉置乱

for i in range(N):

    flag = 1

    # experiment begins

    for j in range(100):

        k = j

        while(A[k] != j and fcounter < 50):

            k = A[k]

            fcounter += 1

        if(fcounter >= 50):

            flag = 0

            fcounter = 0

            break

        fcounter = 0

    if(flag == 1):

        counter += 1

    flag = 0

    random.shuffle(A)

print('Success Rate: ' + str(counter/N))

　　最终的成功率是惊人的

Success Rate: 0.3117

　　这种方法的原理是什么呢，用置换的方法看，一次1~100置乱可以分解为若干个不相交的小循环。若所有小循环的阶都小于50，则囚犯都可以找到自己的号牌。

　　 $\frac{1}{100!}\sum_{l=51}^{100}{\left(\frac{1}{l}\times100!\right)}=\sum_{l=51}^{100}{\frac{1}{l}}=0.6882$ 囚徒遇到大于五十阶循环的概率如左所示，则囚徒们成功的概率达到了惊人的0.3118

巴特西

囚徒问题(100 prisoners problem)的python验证

最新文章

热门文章