国王和100个囚犯

可是你无法确定谁是第一个出来的

不管灯是明暗，其他囚犯做什么都不影响，只从计数的第一次出来开始置1，接着计数的每次出来若发现灯是暗的需要开灯时就++……

假设你是计数者，你第一次出去的时候看到灯是灭的，你会做什么？
如果灯一开始是灭的，那么没问题，开灯计数即可。
如果灯一开始是亮的，那么一定是别人熄灭的，那么你开灯计数的话岂不是少了一个熄灯的人吗？因为一开始熄灯的人已经熄过一次了，而且他再也不会熄第二次了。所以永远只能数到98个人。

不知道说得对不对。

最后一句的省略号就是你的问题所在!!
“之后就和灯初始是关的一样” 就是这里不一样


C 计数囚犯
P 其他囚犯

规则：
1. P 熄灯， C 开灯
2. C 第一次出来看到灯亮 计数初始为 1 ，否则计数初始为 0
3. C 每次开灯计数加 1
4. 每 P 只可熄 1 次灯
5. 计数值到 100 ，判定所有 P 都出来过了


第一个出来的 P 熄灭了灯，但是 C 出来后却不知道灯是原来就灭的，还是被别人熄灭的
1. 如果是本来就灭的，没问题，他以后还可以开 99 次灯，也就是明确有 99 人出来过
2. 如果是被别人熄灭的，他就只能开 98 次灯了，因为那个第一个出来关灯的囚犯不会再熄灭灯了，他已经熄过 1 次了，那 C 只能确定有 98 人出来过

所以每 P 只能熄 1 次灯的方法在逻辑上无法严密


---

前面有人提到每 P 熄 2 次灯，应该是可行的
计数到 198 就可以肯定所有 P 都出来过了
只不过不能肯定是不是每 P 都出来过 2 次了，有可能有一 P 只出来过 1 次。


C 计数囚犯
P 其他囚犯

灯初始状态未知的情况下，可行的规则：
1. P 熄灯， C 开灯
2. C 第一次出来看到灯亮，计数初始为 1 ，否则计数初始为 0
3. C 每次开灯计数加 1
4. 每 P 可熄 2 次灯
5. 计数值到 198 ，判定所有 P 都出来过了


btw: 如果运气一般，出来也要四五十年了。。。

呵呵，题目蛮有意思...大概理解了楼主的设计思路...主要利用计数员的开灯...跟囚犯的关灯..计算count的值.
请楼主赐教...

Orz 没考虑到一个囚犯只能熄一次灯……
这样若灯一开始就亮着，如果囚犯是前多少次能熄灯，在计数囚犯之前的都会少 - 口-

这个方法可行啊，确实，计数198次就不会存在初始时灯的状态不确定带来的问题了。
不过，他们离自由的日子又延长了～～～～

第一天出来的人，担当“计数者”，它把灯开起来（原来开着就不必动了）

然后每天出来一个囚犯。

    如果他不是“计数者”，并且没有关过灯， 并且灯开着， 那么就把灯关了。

    如果他是“计数者”， 如果灯关了， 就把他开起来（计数+1）。 当然如果灯被关了99次， 那么就去和国王说吧。


不需要这么久， 只要 28~29年就行了。


http://bencode.iteye.com/admin/blogs/572294

day = 0
prison =  Hash.new
light_state = rand(2)
light_count = 0
puts "light initialize state #{light_state}"
while light_count < 99 do
	day += 1
	i = rand(100)   # 0 - 99
	if light_state == 0
		if i > 0 && prison[i].nil?
			light_state = 1
			prison[i] = 1
		end
	else
		if i == 0
			light_state = 0
			light_count += 1
		end
	end
end
puts day, day/365

题目描述里面很清楚地表达了，你无法知道你是不是第一天出来的！！