国王与100个囚犯

我解释一下楼主关于这个题目的解题思路。

思路:
·选被关后第一天出去的囚犯作为特殊的计数员
·计数员被放出去,第一天将灯打开,今后每次放出去的时候,如果遇见灯是熄灭的,则将灯打开,并将记数加1
·而其他囚犯为普通囚犯,普通囚犯如果被放出去,在第一次遇见灯是打开的时候将其关闭
(其他情况,即遇见灯是熄灭或第2,3,4..次遇见灯是开着的时候什么也不做)


作为第一天出去的囚犯，每次随机等到他出去的时候（有可能绝大部分时间随机出去的都不是他），如果看到灯熄灭（如果灯亮着，则不算，因为他前一次出来和这次出来之间的时间内没有人关灯，说明没有是第一次出来的囚犯，只有第N次出来，或者这个期间没有人出来过，也就是两台你随机都是他），说明有一个关灯的人来过了（这个人不会是重复的，当然这个期间可能也有其他人来过，但是什么事情都没有做），当他第100次出来看到灯熄灭的时候，说明每个囚犯都至少出来过一次了，呵呵，当然如果真的是每次都随机的话，可能等到他们都死的时候，他们都没有全部出来过。

连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

> 如果时间没法判断，囚犯就无法判断自己是否是第一天放风的。
  顺着楼主的思路可如下计算:
  ·选一个囚犯作为特殊的计数员
  ·计数员被放出去的时候,如果遇见灯是熄灭的,则将灯打开,并将记数加1
  ·而其他囚犯为普通囚犯,普通囚犯如果被放出去,在第1，2次遇见灯是打开的时候将其关闭
   (其他情况,即遇见灯是熄灭或第3,4..次遇见灯是开着的时候什么也不做)
  ·计数累加到197时可保证所有囚犯都放过风了（哈哈，可能要关几辈子了）

当计数员的犯人好辛苦呀。。。。

跟每个囚犯事先要求：
1 约定一种操作表示这一轮自己来过了。比如“开灯”。限制：每人总共只需要操作一次。
2 从自己开灯起，每个囚犯以后出来时，从1开始计数，灯亮表示新人来过，+1.满100报告。
3 如果放风连续100次出来时，灯都是亮的，表示灯初始就亮的，在第一百次出来时将灯关掉，开始计数。

lz的思路是正确的，就算不用选第一天出来的人做计数员，指定某个具体的人做计数员同样可以实现..
想清楚就可以了..其实计数的只有计数员一个人而已..

发现很多人都不理解lz的思路,思路就是100人里指定某个人是计数员，比如说49号的XXX他是计数员，比如灯的初始状态是关着的，然后第一天某个人被放出来了，只要看见灯是关着的，就开开，第二天又有人被放出来了，如果看见灯是关着就开开，如果是开着灯就什么也不做..只有技术员49号被放出来的时候看见灯是开着的就关掉，证明一个人被放出来过，如果49号出来看见灯是关着的，证明他是第一个出来的..如果有人是第2次出来不管灯是开是关都不要去管就可以了..
把这个问题缩小化至5个人，你们试试就应该理解了..

不需要什么第一个人出来就是计数员，要不然又要被人讲死了．．．
还有，其实这个算法不是最优算法，因为按照概率他们都不可能在有生之年出来..

题目有问题，给个思路也有毛病！！




请问你怎么计数？老是贴代码干吗？先抛开代码行不？
什么？记数员囚犯？？这个人每次都出来放风啊？？一次只能放风一个，谁记录？
难道你的意思是说，这个特殊的记数员囚犯每天可以出来一次？？？

另外参数所谓代码的解说，计够 100次？？？我随机成这样 1,2,1,2,1,2,1,2....1，1第100次出来，发现灯熄了，OK了？？？这成吗？

！！！！破坏我脑细胞。

普通囚犯只有关灯的权利，且只能关一次灯！
计数囚犯只有开灯的权利，只有当灯关着的时候才能开灯。
那么当计数囚犯开满100次灯的时候，就说明一百个囚犯都曾出来过！

这个人适合解说题目，条理很好，我终于明白了。

不过，感觉LZ提供的思路解决方案不是很好，因为有大量的冗余或时间空白浪费了，继续寻找最佳答案。
因为有这么个情况:
计数员只出来过99次，就再也没被放风出来了，而外面已经放了好几次100个了，请问怎么办？？？

最后


你就那么担保国王问的就是计数员？