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个囚犯" 这个题目是一个经典的算法问题,属于计算机科学和信息论的领域。问题的核心是,如何设计一个策略,使得100个囚犯至少每人都能至少放风一次,并且在监狱中不允许交流的情况下,如何证明...
该存储库包含用于模拟100名囚犯和一个灯泡问题的代码。 问题 有一个监狱,院子里有可以由囚犯打开或关闭的灯。 有100个囚犯被单独监禁,这意味着他们不能彼此互动,也不能从外界获得任何感官信息。 入狱时,灯泡将...
在这个特定的版本中,n个死囚犯围成一圈,每个人都被赋予了一个从1到n的编号,他们从1开始依次报数,每当报到m的人就会被处决,然后从下一个人继续报数,这个过程一直持续,直到只剩下最后一个囚犯。 解决这个问题...
在这个变体中,100名囚犯被排列成一排,国王的命令是按照某种规则淘汰他们,直到只剩下一个为止。具体规则是:每次消除所有奇数位置上的囚犯,然后在剩下的偶数位置上重复这个过程,直到只剩下一名囚犯。 首先,...
"囚犯逃跑问题"是一个有趣的逻辑问题,它通常被转化为编程任务,以Java这样的编程语言来解决。这个问题的核心在于模拟和优化策略,以求得最优解。 首先,让我们深入理解"囚犯逃跑问题"。假设我们有N个囚犯,他们被...
“一百个囚犯的故事”是一个经典的算法问题,通常被用来展示逻辑和概率思维。问题大致是这样的:有一百名囚犯,监狱长给他们每人一个不透明的盒子,盒子里有不同颜色的球,囚犯们不能看到其他人的球。他们需要通过...
在这个场景中,目标是确保每个有牵连的犯人都不能被关在同一间关押室,以防止他们串供。这个问题可以通过关系矩阵和特定的计算步骤来解决。 1. **关系矩阵构建**:首先,建立一个8x8的关系矩阵,表示犯人之间的关系...
在这个例子中,法官要判处4个犯人死刑,他制定了一个规则,从第s个人开始,每数到第D个人就会被处死,直至只剩下一个犯人可以获得赦免。 在PHP中,解决约瑟夫问题通常涉及到数组和指针的操作。提供的代码示例给出了...
在2015年收集的样本中,有两个成人教育班级相当于一个中学水平(A级为23名犯人,B级为12名犯人,全部为男性),位于一个教养所。 使用问卷。 网络分析软件(Visone)和常规统计信息(SPSS)用于计算网络变量(in...
监狱犯人自动考勤系统解决方案的计数管理软件界面提供了一个友好的用户界面,方便用户对犯人进行考勤和管理。 八、产品照片 监狱犯人自动考勤系统解决方案的产品照片展示了产品的外观和实际应用场景。
每天,监狱长随机挑选一个囚犯,然后那个囚犯访问房间。 囚犯可以切换灯泡。 囚犯可以选择断言所有 N 个囚犯现在都到过房间。 如果此断言为假,则所有 N 个囚犯都被枪杀。 否则,所有囚犯都将被释放。 这个问题有...
但是,样本量只有170多个受访者,并且使用了便利抽样技术,因为这是一种研究,本质上是特殊的,因此,目前仅添加了那些受访者来做这项工作。 研究人员发现每个自变量(MA,SSQ,SE和SR)与因变量(巴基斯坦的社会...
总结来说,该监控系统的设计基于现代化、智能化的视角,充分利用了Zigbee无线网络和GPRS无线网络的技术优势,构建了一个高效、可靠的犯人监控和管理平台。通过这种技术的应用,监狱管理的安全性和效率得到了显著提升...
4. 如果公鸡、母鸡和小鸡的总价等于100元,且小鸡数量是3的倍数,那么找到了一个解,输出这个解并累加计数器count。 5. 如果没有找到任何解,则输出“问题无解”。 实验代码: ```cpp #include #include using ...
这里我们关注的是一种特别的应用场景——犯人信息采集装置。这个装置是电信技术与司法管理相结合的产物,旨在提高监狱管理和犯人信息处理的效率。 犯人信息采集装置通常包含了多种技术集成,例如生物识别技术(如...
用单向循环链表实现了对点杀罪犯问题(约瑟夫问题)的处理。
该问题的基本设定是:一群囚犯围成一个圈,按照顺时针方向从某个人开始计数,每数到特定数值的人会被剔除出圈,然后从下一个人继续计数,直到只剩下最后一个人为止。这个最后剩下的人将获得自由。在编程领域,约瑟夫...
小学数学数学神探哪个是犯人
元首与囚犯_人生故事.pdf