百日囚徒问题

有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宣布获救
文章目录
  1. 1. 思路
  2. 2. 代码
  3. 3. 日志
|