国王与囚犯(腾迅笔试题)
国王招来100个囚犯，对他们说：你们犯的是死罪，但我给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见看不到，连时间都没法计算，无法获得外界的任何信息。
这所监狱有一个院子，每天随机（注意是完全随机）打开一间牢房的门，让一个囚犯到院子里来放风。院子里有一盏灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，灯泡和电路不会出故障。
除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风到院子里的人才能看到。
好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放：
给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流，被关若干天后，你们中间如果任何一个人能够向我证明你们每个人都至少放风了一次，我就把你们放了，不然永远别想再出来。
好吧！这样吧，如果你们有谁现在可以告诉我这个方法，也就是能够证明你们每人至少放风一次的方法，我马上放掉你们！
其中一个囚犯想了几分钟，回答了这个问题，国王听后，如自己所说的把他们全部给放了。请问那个囚犯是用什么方法证明的？
这是lookthesea10月16日在过软做腾讯笔试的时候遇到的。可以在这里看看原文。
容易想到的答案是用一个人只允许关灯并计数（如果灯本来就关着保持灯的状态），其他人只许且必须开灯一次（如果灯本来就开着保持灯的状态），这样的话，当这个人关99次灯的时候，就可以确定都已经出来过了。
javascript实现：
-
<script language="javascript">
-
var prisoners=[];
-
var light=false;
-
var counter=0;//计数器
-
for(var i=0;i<100;i++){
-
prisoners[i]=0;
-
}
-
var i;
-
var days=0;
-
while(1){
-
i=Math.floor(Math.random()*100);
-
if(i==0){
-
if(light){
-
light=false;
-
counter++;
-
if(counter>=99)break;
-
}
-
prisoners[0]++;
-
}
-
else{
-
-
if(!light&&prisoners[i]<1){
-
light=true;
-
prisoners[i]=1-prisoners[i];
-
}else{
-
prisoners[i]>0?prisoners[i]++:prisoners[i]--;
-
}
-
-
}
-
days++;
-
}
-
alert("在"+days+"天后他们都至少出来一次了");
-
var str="<strong>100名囚犯出来的次数分别为：</strong><br/>";
-
for(var i=0,len=prisoners.length;i<len;i++){
-
str+="第"+(i+1)+"名囚犯出来过"+prisoners[i]+"次；<br/>";
-
}
-
document.write(str);
-
</script>
这个办法虽然符合题意，但效率实在低下了点。
依赖1个人计数，而这个人又100次才能出来1次，所以最后大家得出来大约 100*100=10000次才能确定。
想了一下午也没有想到更好的办法。大家有什么好的办法不妨说说。
实际上，保证所有人都出来过只需几百次（哪位同学可以算算）
假设他们买通的监狱长，让他来计数，效果就不一样了:)
-
<script language="javascript">
-
//检查是否全部完成
-
function isFinish(obj){
-
return eval(obj.join("&&"));
-
}
-
var prisoners=[];
-
var light=false;
-
var counter=0;//计数器
-
for(var i=0;i<100;i++){
-
prisoners[i]=0;
-
}
-
var i;
-
var days=0;
-
do{
-
i=Math.floor(Math.random()*100);
-
prisoners[i]++;
-
days++;
-
}while(!isFinish(prisoners))
-
-
alert("在"+days+"天后他们都至少出来一次了");
-
var str="<strong>100名囚犯出来的次数分别为：</strong><br/>";
-
for(var i=0,len=prisoners.length;i<len;i++){
-
str+="第"+(i+1)+"名囚犯出来过"+prisoners[i]+"次；<br/>";
-
}
-
document.write(str);
-
</script>
当然，这只是玩笑。大家有什么好的想法欢迎提出来。最后附上一些搞笑的答案：
1.每个犯人放风出来第一次就在自己身上固定的地方划上一刀,第二次就不用了,等到每个人身上都有了伤疤就证明全部放过风,而且任何人都可以证明. 电灯之类的,我个人认为没有多大作用,障眼法而已。
2.那个囚犯想了几分钟然后大喊我们暴动吧100名囚犯一拥而上绑住了国王,于是国王被挟持犯人逃跑后,国王觉得面子过不去,然后对外界说,有一名囚犯想到了答案.。
3.拍得利数码清析摄像机，让你记录一切美好时光！
4.那个犯人这样对国王说:\"如果你能做到,我们就愿意去死\" 这样国王就不得不放了他们了.原因是;完全随机事件的概率是0<P<1的。
5.在牢房里用手机联络......
6.让国王证明每个囚犯不是每天都放过一次风，行吗？
7.我要是这100个人里的就利用15分钟商量一次暴动！
8.一起冲上去干掉那个国王......
9.押送途中起义......
10.就要看这个灯是多少瓦的拉。。还有他们吃的是西餐还是中餐？
11.不如马上来个痛快的算了~把囚犯全杀了吧！
12.每个囚犯第一次出去就将灯泡砸坏，等坏灯泡达到100个的时候，就证明了。
13.被关在没有时间，概念的房子里多久会崩溃掉呢？估计是自杀的多数吧...正常点的人都是这样子...
14. 可能留到最后的也许还有一个。那么怎么开灯关灯做记号就是他的事了。如果某人在若干天后发现自己已经连续（为什么连续？因为其它人都自杀死了啊。随机到最后只有一人没自杀的时候）一百天都出去放风了，那他可以试着出来说所有人都出来过了！（如果有某人一辈子被关着放不出来呢？那这100人就跟跳出来指证的人一起处死好了。）还不如自杀了算了。所以活到最后的估计也只有一个老得走不动的人了。。。。
15.先不说答案，人被关在一个与世隔绝的，连着蟑螂都看不到，估计也撑不下多久就自行崩溃了，能呆的下也都是神经病。
16.啧啧...把死刑当成无期徒刑...一直耗在那里...那才是最安全的方法啊～
17.要是我，我把其他９９个人全给杀了，就我一个人出去......
哈哈,最后这些答案太搞笑了!
缺哥哥是一个喜欢有趣的人。这是一项难得的品质
难道九哥不喜欢？
出来放风又没说要进去
等外面有100人放风了，不就都出来过一次了！
呵呵，腾讯是招程序员，不是招编辑。而且，出来就不进去了，那叫放风吗？