经典算法问题其一:百日囚徒问题
开始更新博客啦~ 计划每周研究一道算法问题,并给出解决方案和代码实现(python),欢迎大家提出看法和意见,有更优的解决方案更是强烈欢迎。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。这次的问题是几天前看到的一个算法问题,先是自己想了半天,找到一个解决方案,然后和朋友讨论并找到了一个更优解,网上没有搜到几条比较相关的解决方法,所以发出来和大家分享一下。
问题描述:
监狱中关着100名囚犯,每人在一个独立的房间里,且无法用任何方式相互通信;每天会有随机一人被选出来放风,放风的地方有一盏灯,囚犯可以打开或关闭它,其他没有任何人会去动这个灯,其他囚犯不知道是谁被选中放风,也无法看到灯。
某一天国王召集所有囚犯开了一个会,向他们说:如果某一天有人说所有的囚犯都已经放过风了,且情况属实,则所有人都会被释放,如果说错了则所有人都要被处死,然后给了囚犯20分钟讨论时间。
不考虑灯损坏或犯人意外死亡的理想情况下,他们能找出办法让所有人都被释放吗?
大家可以先尝试思考一下,题中很明确只能通过开关灯和灯的亮灭传递消息,所以不要走进死胡同想别的通信方式了,就是设计一个算法,能只通过灯就知道是否所有人都放过风了。
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这里是优化解
经过多次执行模拟的代码,可以看出来耗时在30年上下波动,也比较符合上述算法经过数学计算的10000天左右
更多精彩