求知 文章 文库 Lib 视频 Code iProcess 课程 角色 咨询 工具 火云堂 讲座吧   成长之路  
会员   
要资料
 
追随技术信仰

随时听讲座
每天看新闻
 

利用python进行数据分析
搭建python环境
统计 1880-2010 年间 全美婴儿姓名的趋势
Ipython & Ipython Notebook
NumPy Basics: Arrays and Vectorized Computation
Pandas(Python Data Analysis Library)
数据加载、储存与文件格式
绘图和可视化(Matplotlib)
时间序列
经济,金融数据应用
补充例子
国王与囚徒
利用python进行科学计算
分形与混沌之-Mandelbrot集合
分形与混沌之-迭代函数系统(IFS)
分形与混沌之-蔡氏电路模拟
对于μ子实验数据进行快速处理与分析
37%法则 - "非诚勿扰" 中的博弈
关于时间/日期的转换
深入研究
一切从游戏开始:完整的一个 python to hack 实例!
习题:扑克牌发牌
 
 

国王与囚徒
50 次浏览
1 次
 捐助

国王与囚徒

某监狱里有100个囚犯,有一天国王对囚犯说:“明天我将和你们玩一个游戏,你们将轮流被带到一个房间里,房间里有100个按1到100编号的盒子,每个盒子里都有一张卡片,每张卡片上分别写着你们中一个人的名字,因为你们的名字都不一样,所以每张卡片的名字都不相同。你们每人可以打开50个盒子,但是不能移动任何一个盒子或者卡片,所有的盒子和卡片都会保持初始状态不变。假如某人在打开第50个盒子时或者之前找到自己的名字,那么他将被带到另一个隔离的地方,所有盒子都会重新合上,下一个犯人将被带到房间里继续进行游戏。如果你们所有人都找到自己的名字,游戏就算你们赢,你们所有人都将获释;但是假如有人找不到的话,那么游戏到此为止,你们将按照原来的刑期呆在监狱里。当然,在整个过程中你们不能做任何形式的暗号。但是你们有一个晚上商量对策。”假如所有囚犯都随机打开50个盒子的话,那么他们成功的机会就是1/2^100,机会约等于0。请问你能想出一个提高他们成功机会的策略吗?

当然囚徒不能挪动纸条盒子等,每次操作完都会将盒子移动到标准状态。

怎么算阶乘?

In [67]: def f(n):
....: return reduce(lambda x,y: x*y, range(1,n+1))
....:
In [68]: f(4)
Out[68]: 24

介绍scipy 中的阶乘和排列组合函数 http://docs.scipy.org/doc
/scipy/reference/misc.html#scipy.misc.comb

In [60]: import scipy.misc as sc
In [61]: f=sc.factorial
In [64]: f(4)
Out[64]: array(24.0)

In [65]: f(5)
Out[65]: array(120.0)

计算倒数和

def f2(n):
return reduce(lambda x,y: x + 1.0 / y, range(1,n+1))
或者
f2 = lambda n: sum(1/float(x) for x in range(1, n+1))

首先把1-100这100个数字随机分配给100个囚犯,编号为i的囚犯进房间后先打开第i个盒子,假如里面是第i1个犯人的名,那么接着去打开第i1个盒子;假如第i1个盒子里是第i2个犯人的名字,那么去开第i2个盒子,直到找到自己的名字或者打开50个盒子。这样可以保证无论人数多少,成功的机会总是大于1 - ln2

不失一般化,先设有n个囚犯(n是偶数)。1-n这n个整数的每一种排列相对于原有顺序都可以分解成若干个循环,比如设有1234四个整数,2314这个排列可以表示成(123)和(4)两个循环,,2143可以表示成(12)和(34)两个循环。假如把卡片上的名字对应的编号看成是1-n的一种排列,那么同样可以分解成若干个循环,于是上述的方法相当于第i个犯人遍历整数i所在的循环,策略成功相当于该排列不存在一个长度大于n/2的循环。

现在来分析一个随机排列存在一个长度为k(k>n/2)的循环的概率。从n个数字里选k个循环里的数字共有C(n,k)种方法,每一种方法循环里的数字共有(k-1)!种排列方法,循环外的数字有(n-k)!种排列方法,所有的情况共有n!种,于是概率是 C(n,k)*(k-1)!*(n-k)!/n!=1/k。于是排列存在一个长度大于n/2的循环的概率p是p = 1/(n/2+1) + 1/(n/2+2) + 1/(n/2+3) + … + 1/n

上述p的值小于1/x在[n/2,n]上的定积分,有 p < ln n - ln n/2 = ln 2。于是成功的概率是 1-p,大于 1-ln 2,即无论人数多少,总能保证成功的机会大于 1-ln2,约30%。


您可以捐助,支持我们的公益事业。

1元 10元 50元





认证码: 验证码,看不清楚?请点击刷新验证码 必填



50 次浏览
1 次
 捐助
 

每天2个文档/视频
扫描微信二维码订阅
订阅技术月刊
获得每月300个技术资源
 
 

关于我们 | 联系我们 | 京ICP备10020922号 京公海网安备110108001071号