题目描述

   监狱中关着100名囚犯，每人在一个独立的房间里，且无法用任何方式相互通信；每天会有随机一人被选出来放风，放风的地方有一盏灯，囚犯可以打开或关闭它，其他没有任何人会去动这个灯，其他囚犯不知道是谁被选中放风，也无法看到灯，假定最初灯就是关闭的。
   某一天国王召集所有囚犯开了一个会，向他们说：如果某一天有人说所有的囚犯都已经放过风了，且情况属实，则所有人都会被释放，如果说错了则所有人都要被处死，然后给了囚犯20分钟讨论时间。
   不考虑灯损坏或犯人意外死亡的理想情况下，他们能找出办法让所有人都被释放吗?

题目思路（低级版本）

很明显我们需要通过灯的状态变化次数来判断有多少人放过风。

从这100人中选出1个人，这个人只能关灯，并且他记下自己关灯的次数。其他99人出来放风的时候只能开灯，并且每人只能开一次灯（也就是说，如
果他以前已经开过灯了，就算他再次出来的时候灯是关着的也不能开）。当关灯的发现他已经关灯99次时，就可以宣称所有人都出来过了。
这个方法和穷举法相比差不多，这里就不做代码解释和思路分析了。

题目思路（进阶版本）

确认身份

前100天利用灯来互相确认自己的身份（灯初始状态为关闭，最好的情况是100天）。

  • 计数人
    首次放风的人不进行任何操作，设第一个二次放风的人为计数人，计数人把灯打开（比如第20天该囚犯第二次去放风，且前面没有人去动过灯，则说明连同他共有 19个人是首次放风，因为第20天的话，这个人去了两次，所以要减去一次），则此时生成一个该天数的计数(N-1)

  • 已知囚徒
    设剩下的99人中，见到过灯灭状态的人为已知囚徒，因为计数人能通过开灯的日期准确推算出之前的人数

  • 未知囚徒
    设从未见过灯灭状态的人为未知囚徒，因为灯打开后，计数人无法获取放风的准确人数

这里有个最理想状态：
第101天，某首次放风囚徒发现灯为关闭状态，说明前100天均无人2次放风，即每人都是首次放风，可以宣布获救。

添加后续人员

确认完身份后，开始将未知囚徒一个一个变成已知囚徒（计数人通过灯的变化）

  • 已知囚徒放风
    不进行任何操作
  • 未知囚徒放风
    若灯为打开状态，将灯关闭，该未知囚徒变为已知囚徒。
    若灯为关闭状态，不进行任何操作。
  • 计数人放风
    若灯为关闭状态，说明有一个未知囚徒变成了已经囚徒，计数N+1，并将灯打开，以便下一个未知囚徒传递信息
    若灯为打开状态，说明暂时没有未知囚徒变成了已经囚徒，不进行任何操作。
    当计数人放风时恰好N=100，则他可以宣布确定所有囚徒都放过风了。

代码实现

import random

days = 1  # 天数
light = False  # 灯
times = [0 for i in range(0, 100)]  # 每个囚徒放风次数的统计数组
counter = -1  # 计数人
know_list = []  # 已知囚徒
know_num = 0

while 1 == 1:

    # 随机抽选一人放风
    P = random.randint(0, 99)
    # 前100天确认身份并且确认计数人
    if days <= 101 and counter < 0:
        times[P] += 1  # 灯灭放风有效
        if times[P] == 1:  # 第一次放风 什么也不用做
            know_list.append(P)     # 已确认身份人列表
            know_num+=1     # 已确认身份人数
        if times[P] == 2:  # 灯灭且第二次放风，这个人为计数人，设置灯亮
            counter = P
            light = True
    elif len(know_list) == 100 and know_num == 100:   # 刚好100人确认身份
        print("        所有囚徒已确认身份")
        break
    else:
        if P == counter:        # 确认计数人
            if not light:       # 灯灭，至少有1个新人放风，灯设置为亮
                light = True
                know_num += 1  # 从计数人的角度来看，这里加1
                if len(know_list) == 100 and know_num == 100:  # 其实这里最好是判断 know_num ，因为最终是要计数人来宣布
                    print("        所有囚徒已确认身份")
                    break
            else:           # 灯亮，没有人放风
                pass
        elif P in know_list:       # 已经确认身份 什么都不用做
            pass
        else:
            if light:               # 未确认身份灯亮，放风有效，灯关闭，确认身份
                light = False
                know_list.append(P)
    days += 1