原帖可见:http://www.iteye.com/topic/570744,问题大致如下:
国王招来100个囚犯,对他们说:你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见、看不到,连时间都没法计算,更别说获得外界的任何信息。(送饭除外,但也是不规律的送)
这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。院子里有一盏路灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。
除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净(包括在灯上作的任何记号)。
牢房是完全封闭的,院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。
好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放: 若干天以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人无法自圆其说,你们就全部砍头。所以,要珍惜这次机会。如果你们永远做不到我的要求,你们就全部关到死。
现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。
这是我的解决方案:
package org.sunkui.demo;
import java.util.Random;
public class PrisonExample {
Random rand = new Random();
public static void main(String[] args) {
PrisonExample p = new PrisonExample();
p.method_1(true);
}
void method_1(boolean light) {
int[] prisoner = new int[100];
// counter prisoner, the first out
int counter = rand.nextInt(100);
// Light turn on or off from now on
int counterLightOnOrOff = 1;
// whether on or off the first time, and the counter turn on/off the
// light right now
boolean lightOnOrOff = !light;
// starts right now
int days = 0;
// the first prisoner out
prisoner[counter] = 1;
while (true) {
// include the counter
int others = rand.nextInt(100);
days++;
if (others == counter && !lightOnOrOff) {
// if light is in state initialize state, put it to opposite
// state
lightOnOrOff = !lightOnOrOff;
counterLightOnOrOff++;
} else {
// other prisoners turn the light on or off just once
if (prisoner[others] == 0 && lightOnOrOff) {
lightOnOrOff = !lightOnOrOff;
prisoner[others] = 1;
}
}
if (counterLightOnOrOff == 100)
break;
}
System.out.println("Total days: " + days);
}
}
分享到:
相关推荐
趣味算法:国王和100个囚犯.doc
该存储库包含用于模拟100名囚犯和一个灯泡问题的代码。 问题 有一个监狱,院子里有可以由囚犯打开或关闭的灯。 有100个囚犯被单独监禁,这意味着他们不能彼此互动,也不能从外界获得任何感官信息。 入狱时,灯泡将...
n个死囚犯围成一圈,编号1至n,从1开始报数,报到数m时,执行枪决,接着重新报数,继续上述操作,直至剩下最后一个囚犯,给出最后一个囚犯的编号
用单向循环链表实现了对点杀罪犯问题(约瑟夫问题)的处理。
某国王对囚犯进行大赦,让一狱吏n次通过一-排锁着的n间. 牢房,每通过一-次按所定规则转动n间牢房中的某些门锁,每转 动一次原来锁着的被打开,原来打开的被锁上通过n次后,门锁 开着的,牢房中的犯人被放出,否则,...
每天,监狱长随机挑选一个囚犯,然后那个囚犯访问房间。 囚犯可以切换灯泡。 囚犯可以选择断言所有 N 个囚犯现在都到过房间。 如果此断言为假,则所有 N 个囚犯都被枪杀。 否则,所有囚犯都将被释放。 这个问题有...
古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决…… 直到剩下最后一个可以赦免. function getNum($n,$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...
囚犯逃跑问题的java解决方法,事先可以设定囚犯人数与测试次数。
解决问题
但是,样本量只有170多个受访者,并且使用了便利抽样技术,因为这是一种研究,本质上是特殊的,因此,目前仅添加了那些受访者来做这项工作。 研究人员发现每个自变量(MA,SSQ,SE和SR)与因变量(巴基斯坦的社会...
遗传算法的有趣应用很多,诸如寻路问题,8数码问题,囚犯困境,动作控制,找圆心问题(这是一个国外网友的建议:在一个不规则的多边形 中,寻找一个包含在该多边形内的最大圆圈的圆心。),TSP问题(在以后的章节...
小学数学数学神探哪个是犯人
元首与囚犯_人生故事.pdf
信息时代的“囚犯”.pdf
深度优先搜索的过河问题应用,一个警察和一个犯人,一个爸爸一个妈妈,两个儿子两个女儿,他们要过河,有一艘船一次只能坐两个人,爸爸不在妈妈打儿子,妈妈不在爸爸打女儿。警察不在。犯人杀人。怎样才能过河?
在正常运行中,这些索引中的一个将处于“活动”状态,而另一个则处于Hibernate状态且未使用。 当我们准备重建索引时,“其他”非活动索引将转换为进行in-progress状态true 。 PUT /prisoner-index/build-index检索...
监狱犯人自动考勤系统解决方案.doc