有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？不考虑什么犯人突然死亡的意外因素。是纯粹的理论题。
思路
1、前100天利用灯来互相确认自己的身份（灯初始状态为关闭）：
- 计数人
- 首次放风的人不进行任何操作，设第一个二次放风的人为计数人，计数人把灯打开（比如第20天该囚犯第二次去放风，且前面没有人去动过灯，则说明连同他共有19个人是首次放风），则此时生成一个该天数的计数(N-1)
- 已知囚徒
- 设剩下的99人中，见到过灯灭状态的人为已知囚徒，因为计数人能通过开灯的日期准确推算出之前的人数
- 未知囚徒
- 设从未见过灯灭状态的人为未知囚徒，因为灯打开后，计数人无法获取放风的准确人数
这里有可能出现最好情况：第100天，某首次放风囚徒发现灯为关闭状态，说明前100天均无人2次放风，即每人都是首次放风，可以宣布获救。
2、100天过后，未知囚徒和计数人之间通过灯来传递信息（灯初始状态为打开）：
已知囚徒放风
- 不进行任何操作
未知囚徒放风
- 若灯为打开状态，说明通信可用，关灯向计数人传递信息，至此该未知囚徒以后都不再对灯进行操作。
- 若灯为关闭状态，说明此次通信未结束，不进行任何操作
计数人放风
- 若灯为关闭状态，计数N+1，并将灯打开，以便下一个未知囚徒传递信息
- 若灯为打开状态，说明暂时没有未知囚徒发起通信，不进行任何操作
当计数人放风时恰好N=100，则他可以宣布确定所有囚徒都放过风了。
代码
import random
days = 1 # 天数
light = 0 # 灯
times = [0 for i in range(0,100)] # 每个囚徒放风次数的统计数组
counter = -1 # 计数人
remainer = 100 # 剩余未知人
while 1==1:
print("第%d天: "%days)
print(" 剩余未知人: %d"%remainer)
# 随机抽选一人放风
P = random.randint(0, 99)
# 前100天确认身份
if days <= 100:
if light == 0:
times[P] += 1 # 灯灭放风有效
if times == 1:
pass
if times[P] == 2: # 灯灭且第二次放风
counter = P
print(" 确定计数人: %d" %counter)
light = 1
remainer -= (days-1) # 开灯计数
else:
pass # 在灯亮放风无效
if days == 100 and light == 0: # 100天灯仍灭，获救
print("获救")
break
else: # 100天后通过灯通信
if light == 1:
times[P] += 1 # 灯亮放风有效
if times[P] == 1: #(未知者)关灯发出信息
light = 0
else:
if P == counter: # 灯灭计数人开灯计数
light = 1
remainer -= 1
if remainer == 0:
print(" 计数人%d宣布获救" %counter)
break
days += 1
日志
第1天:
剩余未知人: 100
第2天:
剩余未知人: 100
第3天:
剩余未知人: 100
第4天:
剩余未知人: 100
第5天:
剩余未知人: 100
第6天:
剩余未知人: 100
第7天:
剩余未知人: 100
确定计数人: 53
第8天:
剩余未知人: 94
第9天:
剩余未知人: 94
······
第9538天:
剩余未知人: 1
第9539天:
剩余未知人: 1
第9540天:
剩余未知人: 1
第9541天:
剩余未知人: 1
计数人53宣布获救