http://www.iteye.com/topic/569275
A simple google on "100 prisoners riddle" yields the following two insights:
http://www.algonet.se/~ug/projects/lightbulb/
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
The second one is a pdf, which I appended here.
In the above links, I believe they assume the initial state of the light bulb is off, not unknown. They mentioned two ways to do this. The first way has expected value 28... years and the second one has 12.. years. (We can only talk about expected value since the process is a random process.)
If the initial state is not known, the strategy for the known case won't work.
Assume C is deonted for the counter, and P for other prisoners. Denote X for off and V for on
We can just consider 2 prisoner case, where one of them is counter
Initial state progress
X CP(V)C(X+1) ----> counter is now 1, we can get out
P(V)C(X+1) -----> counter is now 1, we can get out
V C(X+1) -----> counter is 1, but P is not out yet <--------- This is where it breaks down.
PC(x+1) -----> counter is 1, we can get out
The '+1' means that the counter increment its counter. (V) means turn on switch, (X) means turn off switch
In order to overcome the above problem, we have to let every P switch twice.
X CP(V1)P..PC(X+1)C...CP(V2)P...PC(X+1) ------> The counter is now 2, we can get out now
P(V1)P..PC(X+1)C...CP(V2)P...PC(X+1) ------> The counter is now 2, we can get out now
V C(X+1)C...CP(V1)P...PC(X+1) -----> The counter is now 2, we can get out now
PC(X+1)C...CP(V1)P...PC(X+1) -----> The counter is now 2, we can get out now
For 100 prisoners, the counter needs to reach 198.
Not sure the expected value of this method, and not sure we could make it faster using a similar method in the first link.
分享到:
相关推荐
趣味算法:国王和100个囚犯.doc
该存储库包含用于模拟100名囚犯和一个灯泡问题的代码。 问题 有一个监狱,院子里有可以由囚犯打开或关闭的灯。 有100个囚犯被单独监禁,这意味着他们不能彼此互动,也不能从外界获得任何感官信息。 入狱时,灯泡将...
n个死囚犯围成一圈,编号1至n,从1开始报数,报到数m时,执行枪决,接着重新报数,继续上述操作,直至剩下最后一个囚犯,给出最后一个囚犯的编号
有8个犯人,为防止他们串供,必须把有牵连的犯人互相隔离,问至少需要几个关押室,给出计算方法与程序。已知有牵连的情况如下表: 犯人 有牵连的犯人 A B C D E F G H B C E G A C H A B D C E H A D F H F G A F H...
在2015年收集的样本中,有两个成人教育班级相当于一个中学水平(A级为23名犯人,B级为12名犯人,全部为男性),位于一个教养所。 使用问卷。 网络分析软件(Visone)和常规统计信息(SPSS)用于计算网络变量(in...
每天,监狱长随机挑选一个囚犯,然后那个囚犯访问房间。 囚犯可以切换灯泡。 囚犯可以选择断言所有 N 个囚犯现在都到过房间。 如果此断言为假,则所有 N 个囚犯都被枪杀。 否则,所有囚犯都将被释放。 这个问题有...
但是,样本量只有170多个受访者,并且使用了便利抽样技术,因为这是一种研究,本质上是特殊的,因此,目前仅添加了那些受访者来做这项工作。 研究人员发现每个自变量(MA,SSQ,SE和SR)与因变量(巴基斯坦的社会...
古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决…… 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把...
囚犯逃跑问题的java解决方法,事先可以设定囚犯人数与测试次数。
解决问题
用单向循环链表实现了对点杀罪犯问题(约瑟夫问题)的处理。
小学数学数学神探哪个是犯人
元首与囚犯_人生故事.pdf
信息时代的“囚犯”.pdf
博弈论模拟这是一个模拟和可视化囚犯困境的项目。 它实现了Nowak&May(1992)提出的空间囚徒困境游戏[1]。细节在此模型中,座席被放置在网格中,在每一轮中: 每个人都通过与其所有近邻及其本人进行囚徒困境游戏来...
在正常运行中,这些索引中的一个将处于“活动”状态,而另一个则处于Hibernate状态且未使用。 当我们准备重建索引时,“其他”非活动索引将转换为进行in-progress状态true 。 PUT /prisoner-index/build-index检索...
监狱犯人自动考勤系统解决方案.doc
电信设备-一种犯人信息采集装置.zip
* 现在有八个人需要划船到河的对面去。...* 船上一次最多只能坐两个人。 * 求出过河方案 */ 依赖包: <groupId>com.github.dpaukov</groupId> <artifactId>combinatoricslib3 <version>3.3.0 </dependencies>