囚犯问题

Question

如果大家是第一次出去放风就关掉灯，如果不是第一次就打开灯，而灯的状态是由他之后的人再来改变，也就是说后面一个人可以看到前面人的灯的效果！如果有一个人在看到了99次灯都是灭的，说明大家都是已经出去放过风了！我感觉这样是可以的。VERY EASY!  但如何给国王证明这个结果，呵呵！不知道证明是不是上面我所说的过程算不算是证明，不算的话，也要被砍头了！

Answer 1

月之影    说的确实在理，不过没有最极端的情况，因为就只有这一种极端情况，就是这个人连续两天都出来才不好判断，
如果不是连续两天的话，是可以的
call,这么说我也要被杀头了嘛？55...不会吧，该死的，老天啊，你怎么能让一个人连续出去两次啊，害得我永远也出不去了！

Answer 2

以下方法错误到了极点啊！
只有一个计数的方法可行，其它的都不可行。
=============================================================================
tavor(龙双公子) 
哈哈，我上面一激动把初始状态和下面的标准写反下，下面是更详细的解释大家的思路被封在两个地方：
1.只让一个人计数（可以，但奇慢，效果十分之不好，大伙都这么认为吧）
2.多人计数，但不知道如何控制状态。（都对状态的设置十分迷糊）
我再详细说一下：
1.假设灯的初始状态是开的。
如果囚犯是第一次放风，看见灯灭，就认为前面有一个人出来放过风，计数加1，并且保持灯灭的状态不变;如果看见灯开着，因为他是第一次出来，就把灯关掉。如果囚犯不是第一次放风，看见灯灭，就认为前面有一个人出来放过放，计数加1，并且把灯打开;如果看见灯开着，因为他也是第二次出来，就保持灯开的状态不变。当任一个人的计数达到99的时候，就可以报告给国王了。2.如果灯开的时候是灭的（理论上是这样才合理的）
如果囚犯是第一次出去，看见灯亮，就认为前面有一个人出来放过风，计数加1，因为他也是第一次出来，所以并且保持灯亮的状态不变;如果看见灯灭，因为他是第一次出来，就把灯打开。如果囚犯不是第一次放风，看见灯亮，就认为前面有一个人出来放过风，计数加1，并且把灯关掉;如果看见灯灭着，因为他也是第二次出来，就保持灯灭的状态不变。同样，当任一个人的放数达到99的时候，就可以报告给国王了
=====================================================================================以上方法错误到了极点啊！只有一个计数的方法可行，其它的都不可行。

Answer 3

不对   风之影    ，我的推理没有问题，只不过被你的假像所迷惑（其实也许本来就是我想的不够充分）
，其实就只有一个你所说的极端情况，那就是这个人被连续两天被放出来，再者，一个人如果是被连续两天放出来的话，老大，你连续待在外面两次你能分不出来吗？你刚被带进来，然后又马上被带出去，你分不清楚嘛！如果真的是这样的话，估计不要等着放出去了，还是自尽好一些。不过也许楼主又要说，每天在外面待的时间是随机，我CALL，那么说就是出题的漏洞了。
根本不需要人数到100，要不  月之影   你还是给我举个例子吧！
我不睡觉了，和你讨论讨论！

Answer 4

TO：herocome(隐身人) 朋友，请你给一个你自己的不错误到极点的方法！谢谢！

Answer 5

我觉得很简单，因为国王给他们都有一次机会，所以当100天过去之后，就有答案了，因为一点，人人都可以得一次饭吃。我觉得就像 while条件判断一样。          public 机会() 
          while (每人一次机会)
               { 
                if (其中一个人没有得到机会)
                   {
                      国王说的话=false;
                       break:;
                    }
                }

Answer 6

测试N次，最多157年，最少31年出来~一个最简单的方法是让一个囚犯负责关灯，其余的囚犯负责开灯，规则如下：
设第100号囚犯关灯，其他囚犯作如下动作：
当他头一次放风并且看到的灯是关着的时候，那么他将灯打开，其余的情况不作任何操作
而第100号囚犯（负责关灯的）则在他被放风的时候观察灯，若灯亮，记下次数，并且关灯，若灯暗，则不作操作，这样，当这一囚犯记录到99次关灯之时，他可以确认所有的人至少都被放风过一次了。
这个方法是最简单的但不是最优的，有兴趣的人可以用程序模拟一下，会发现天数太多，所有的囚犯十有八九注定是要老死在狱中的...by 月之影

Answer 7

月之影的答案确实是可行的，但是要30年，如果在这30年中有人，那99个人中有个人死掉的话，那么那个计数的the one就永远也无法去想国王证明了。
解法2：（转）为了信仰，我们甘愿付出生命。15分钟内我们选出一个智勇双全的人（b），用其他99人（a）的生命换来他的释放。再由b为a们报仇，组织一支军队干掉变态的国王。（当然，这都是后话，与题目无关）
具体方案：管他妈的鸟路灯！所有的a到放风时都在院子里撞死。b呢？当他发现连续很多天都轮到他放风时，就明白了：a已经死光光。也就是说：a已经全部放过风了。那么，他就可以得到释放。
该方案不要半年就可以完成，成功率也可以无限逼近100%。