有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宣布获救