经典算法问题其一：百日囚徒问题

1、发出信息的方式就是开灯或关灯，获取信息的方式就是灯亮着或灭着；
2、囚犯除了处理灯以外，还可以计数，比如遇到过多少次亮灭；
3、必须要有人做统计，知道有多少人已经放过风了才能汇报。

#有个人我们假设是A，A说：“你们如果放风的时候看到灯亮着，就关掉它，但是每个人只关一次。然后我去打开它。”
#这样的话，A每次见到灯灭着，就说明有放过风的人数增加了1个，然后他打开灯。当他开了99次灯之后，说明所有人都已经放过风了。
#理论最短耗时为198天，即其他人不重复的依次放风，A隔一天放一次风计数一次。BACADAEA......

#那么实际需要多少天才能完成目标呢？我们用python模拟一下：


import random

#先创建一个99人的囚犯字典，值为False，代表还没放过风(没关过灯)
prisonerDict = dict.fromkeys(range(99), False)
#再添加计数君A进去，值为0，代表已知0个人放过风
prisonerDict['A'] = 0
#天数
day = 0
#初始灯是亮的
light = True

#然后开始我们漫长的循环之旅吧~
while True:
    #新的一天开始了，我们随机选了一位囚犯出来放风
    day += 1
    user = random.choice(prisonerDict.keys())
    #如果是A，看到灯灭了，则打开灯，并在人数上累加1
    if (user == 'A'):
        if not light:
            light = True
            prisonerDict[user] += 1
        #当A发现其他99个人都放过风了，则汇报上去，跳出循环
        if (prisonerDict[user] == 99):
            break
    else:
        #其他囚犯如果发现灯亮着而且这个囚犯没关过灯，就关掉它，囚犯状态改为True
        if (light and not prisonerDict[user]):
            light = False
            prisonerDict[user] = True

#简单计算一下天数(年数)
print day/365

#如果大家觉得A这个人不靠谱，每个人都想当最后汇报结果的人呢？那么我们就选拔出一个人吧：第一个重复放风的人成为计数君
#基本解里，即使是一群欧皇(人品帝)理想模式下仍需要198天才能出去，能不能缩短下呢？让所有人都出去过的第二天，计数君就能汇报结果
#优化后方案如下，分为2个阶段：

#1、计数君选拔阶段(前101天)：每个人第一次放风的时候不处理灯，当第二次出去的时候关掉灯；那么第一个关灯的人就是计数君A，最多需要101天
#2、计数阶段(102-)：所有人按照基本解里的操作来执行。

#优化后的方案好处是缩短了理想情况的时间，当所有人依次放一次风后，第101天放风的人发现灯还是亮的，知道前100天没有人重复，就可以汇报了，耗时101天；(其实第100个人判断这100天都没重复就可以汇报了)
#代码模拟如下：

#!/usr/bin/python
# -*- coding: <encoding name> -*-

import random

#创建一个100人的囚犯字典，值为[0, 0, None]，代表还没放过风(没关过灯)且未开始计数且没有身份，没有使用dict.fromkeys是由于它产生的字典，所有值指向了同一个内存，无法分别计算
prisonerDict = {}
for i in range(100):
    prisonerDict[i] = [0, 0, None]
#天数
day = 0
#初始灯是亮的
light = True

#仍然是开始我们漫长的循环之旅~
while True:
    #新的一天开始了，我们随机选了一位囚犯出来放风
    day += 1
    user = random.choice(prisonerDict.keys())
    #前101天我们先选一个计数君,每次自己放风次数+1，灯亮着并且自己第二次出来则关掉灯
    if (day < 102):
        prisonerDict[user][0] += 1
        if (light and prisonerDict[user][0] == 2):
            light = False 
            #此处为标识计数君，将放风次数始终为负数，为保证始终有效，将放风次数置为-102
            prisonerDict[user][2] = 'count'
    else:
        #101天之后，如果是计数君，看到灯亮了，则关掉灯，并在人数上累加1
        if (prisonerDict[user][2] == 'count'):
            if light:
                light = False
                prisonerDict[user][1] += 1
            #当A发现其他99个人都放过风了，则汇报上去，跳出循环
            if (prisonerDict[user][1] == 99):
                break
        else:
            #其他囚犯如果发现灯灭着而且这个囚犯没开过灯，就打开它，囚犯状态改为True
            if (not light and not prisonerDict[user][2]):
                light = True
                prisonerDict[user][2] = True

#简单计算一下天数(年数)
print day/365