智力问题：100个罪犯的命运

100个囚犯的智力测试题~

囚犯们按照顺序站成一排依次从左边或者右边开始观察其它囚犯是否有相同数字的帽子，如果观察到有至少一对相同数字的帽子，那么就直接出列，后面的人不用再观察他。如果没有观察到有相同数字的帽子则往前一步（表示他观察结束没有发现有相同数字的帽子轮到下一位观察者观察），但是后面的人还需要观察他，仍在观察范围之内。当所有囚犯都观察完成之后会出现两种情况：第一种是所有人都没有出列，都只是往前一步，说明没有相同数字的帽子，帽子数是从0到99刚好100位，100个囚犯不重复分配每人刚好分到0到99中的一个，这时候只需要观察其他人的数字就能推断出自己的数字来。第二种情况是只剩下两个人在队列里，其他人全部出列，因为最后一对相同数字帽子的人是看不到有数字相同帽子的人的，而其他人和排在前面的有相同数字帽子的人都会看到他们而出列，最后剩下的两个人互相写对方帽子上的数字就行了。

假设初始灯为关。把100个囚徒分成A和其他99人。
A如果看到灯关着，就打开。
其他人：（这个描述比较混乱）：如果其他人中任何一个，出来时看到灯开着，并且自己从来没有关过灯，那么，就把灯关了，如果看到灯关着，或者灯开着但是自己之前关过灯，则不动。
这样，当A开100次灯时，就可宣布所有人都放风了！（之所以是100而非99，是因为可能出现A是第一个放风的情况）。
解释：我的解的基础是：必须有一个人知道所有人都出来了！而知道的唯一办法，就是让其他所有人都拥有且仅拥有一次改变灯的状态的权利！并且这种改变是单向的，否则可能连出来两个人，灯的状态就变回去了，那个计数的人就迷茫了。于是，我让所有人都拥有且仅拥有一次关灯的权利，这样，A看到的灯被打开的次数表明了至少有多少人被放风过！（是至少，因为可能有人被放风了但是他出来的时候灯是关着的，他不能开，就不能留下记号）。当计数人数到99，他们就赢了。
这个解实际相当无效，再想优化解中......

稍微想想，想到一个你的方法的改进版，假设灯是关着的，每个人出去都不动那个灯，直到有个人第二次出去放风，那个人就负责做观察媛，这时根据天数可知已放风人数，后面的基本按你的办法，这样运气好的话节省不少时间啊。。。

　　呵呵，很有意思的一道面试题目。听说是今年百度公司前不久的某次面试题目！由于开关的开关两种状态，所以我猜应该是个编程的题目，我试着编程模拟了一下，应该没问题了吧！

　　突破口：开关（但是是废弃的，也就是说不能当控制灯用了，这是题目出的巧妙性与完整性，不愧是大公司出的题目）,可以是开或关的两种状态，由于100间牢房是完全隔绝的，而且相互间不能通信，即使路灯可以用，牢里的人也看不到外边，这样灯的亮与不亮直接就能用开关的开或关表示了，按我楼上的说法，废弃了多好，还能节能！
　　用VC编程语言部分代码简要说明如下：

　　BOOL Buf=FALSE; //标志开关的两种状态，1为开着，0为关着
　　int Science; /*0--99取值，100个数学家从0到99编号,Science=N表示第某天第N号数学家出去放风，设Science=0作为一个哨岗的数学家，负责保持开关的开状态(关状态也行，在此以开状态为例说明)*/
　　int ScienceBuf[100]; //ScienceBuf[N]=0表示第N位科学未关过开关
　　//ScienceBuf[N]=1表示第N位科学未开过开关
　　//所以ScienceBuf[N]只有0或1的取值
　　int Science_Num=1; /*由哨岗数学作记录，并记录相当确定出去放风过的人数*/
　　int Num; //记录天数（起辅助作用）
　　for(int i=0;i<100;i++)
　　ScienceBuf[i]=0; //初使化，因为开始时都没有关过开关

　　for(Num=0;;Num++)
　　{ Science=rand%100; /*随着天数的增涨，每天出去的数学也是有rand%100随机产生*/
　　if( Science==0 && Buf==FALSE ) //哨岗外出放风,并看到有人第一次关过开关了
　　{ Science_Num++; /*有人第一次关开关，则记录，算他第一次放风*/
　　Buf=TRUE; //并且继续保持开关开着
　　}
　　if( Science!=0 && Buf==TRUE && ScienceBuf[Science]==0) //其它人放风且开关开着而且这人没有关过开关
　　{ Buf=FALSE; //关掉开关
　　ScienceBuf[Science]=1; //这人关过开关了
　　}
　　if(Science_Num==100)
　　{ cout<<"所有人已经出去过了，我可以去报告了，我们可以回家了"<<endl;
　　return;
　　}
　　}
　　（什么时候能全部出去就看这个算法的时间复杂度。在实际中，随机产生的时间无法估量，但可以想象得到，每天每人出去的概率是百分之一，所以某人出去的期望值是100天一次，也就是说100*100天全部数学家能出去是最理想的，看来27年的岁月得耗在里头了！）

　　看不懂编程的人看如下文字说明：
　　设第一个放风的人为Q，Q作为哨岗，只能他将开关保持开着的状态。也就是到他放风时候，见开关开着就继续让它开着，见开关关着就把它打开，记录一次；
　　其它出去的人一般对待。如果这些出去，见到开关开着，并且自己没有关过开关就将它关掉；如果见到开关着，就不管它保持它的原有状态。
　　这样，也就是关掉开关的人都是第一次关开关，也就当他第一次出去放风。这时候其他第一次放风的人看到自己前边有第一次放风的人关掉了开关，就算作自己没有出来放过，也就不动开关了。正是这样，哨岗Q所记录的都是第一次出去的人，除掉自己外，再记录99次开关有过关着的状态，所有人就至少放风过一次了！

　　楼上诸位中只有三楼的说得接近（也可能是正确思路，没说明白），其他的各位要么是没有正面回答，要么是没认清题目，考虑周全。

他们不是可以商量么？那就约定，按人编号，从一到100，第一天一号放风，第二天二号放风，，，，，，第一百天一百号放风，然后就可以集体报告：该放我们了。
回答者：琥珀玫瑰 - 探花 十一级 11-20 12:21
废弃的路灯开关不是能用嘛，专门指定一个人，当他放风的时候就把路灯显示“关”，然后当其余人放风的时候，在路灯显示为“关”的状态下，每人去“开”一次，然后，由专门指定的人去统计，路灯总共“开”了几次，这样，开了99次以后就说明每人出去放风过至少一次了。

这样行吗？
回答者：always_caicai - 魔法学徒 一级 11-20 12:30
每个人第一次到场地的时候都开关一次灯（进去时打开，出来时关上），第二次进去的人进去以后不开灯。这样找个人数着开灯的天数，够一百就可以了。
这么简单的问题，还用问？！
回答者：冰爱鑫 - 见习魔法师 三级 11-20 12:51
第一个去放风的人 把开关弄到"开"的位置 进去前跟其他人约定好:只有他再次放风的时候,才会把开关弄到"关"的位置.然后第一个看到关的人去报信.并且把开关再弄到"开"的位置,这样循环.当第99人去放风的时候 先不去报信,等到有两天没叫他去放风的时候,他和剩余的第100人就可以一起出去了!

楼主我这方法不行吗?错在哪呢?

很简单，他们都被放了```
要问他们怎么被放的，那就是另一个问题了。
受到惩罚
有点难度```结局是他们都被放````
可以按人编号啊，从第一天开始．第一个人为1，第二个人为二，以此类推 就可以了啊，到第一百个人时，也就是第一百天了啊
最后他们就得以都被放了
商量的时候给每个人编号，然后按场地的数量a一天出去a个人，到编号为100的人出去后，按下路灯开关即可。

要么回答错误被杀，
要么无期徒刑到老死。
什么数过100下开关灯什么的能不能专心看下题目啊!!!!什么叫完全隔绝!!!!!题目都没看清就瞎答!来搞笑的吧!!!!
2楼的更搞笑,什么叫随机,上小学没有啊!
我想应该是编程序的,写起来比较复杂,你找些编程的书看就O了!开关既0和1!
OK,我先来分析一下题目
要点有1、随记，也就是说这个不是由犯人决定，而是由监狱决定，完全无法避免不重复。
2、可以商量一次，在进去以前。
3、路灯显示，路灯的开关情况是可以被所有人看见的。都是数学家。

由以上几点可以推断上面部分答案是错误的，还有一部分我没有看懂。

但是问题并不复杂。答案如下：
商量好，任何一个人如果被随机挑选到放风，那么他第一次就把灯打开，走的时候把等关上，如果他第二次，第三次以及更多次被选上去放风时，则不要开灯。
这样，就可以保证灯亮的每一次都有一个人是第一次去放风，也就是说当灯亮到100次时，100个人已经都去放过风。

为了安全起见，我们还可以来一个验算机制，首先，所有人都应该对于灯被打开的次数进行记录，当100次亮灯的第二天，防风者如果记录的次数是100，那么他可以通过当天反复亮灯以表示达到100，如果这样连续3天，就表示有3个人得到的答案都是100，应该可以保证，如果没有连续，那么继续验算，当然，这个时候还是取平均值，看得到答案是100的人有多少，如果比例达到一定程度就可以确定了啊。
验算是保险起见，不在答案范畴内。

方法2：商量时，自己编号，1到100，当天放风者通过开关灯来表示编号，即亮一次表示1号，两次表示2号，以次类推，所有人做记录，当所有编号满了的时候就表示所有人都去过了。

验算方法通上，不过改一下表示方法，不亮灯表示已经算满。

从节能的角度出发，采取方法1，如果灯一不小心坏了，算他们倒霉，但是等灯好了还是可以继续撒。如果灯关不了，就惨了，方法1不行，方法2仍然可以实行。
回答者：czc001002 - 试用期 一级 11-23 10:10
呵呵，很有意思的一道面试题目。听说是今年百度公司前不久的某次面试题目！由于开关的开关两种状态，所以我猜应该是个编程的题目，我试着编程模拟了一下，应该没问题了吧！

突破口：开关（但是是废弃的，也就是说不能当控制灯用了，这是题目出的巧妙性与完整性，不愧是大公司出的题目）,可以是开或关的两种状态，由于100间牢房是完全隔绝的，而且相互间不能通信，即使路灯可以用，牢里的人也看不到外边，这样灯的亮与不亮直接就能用开关的开或关表示了，按我楼上的说法，废弃了多好，还能节能！

（什么时候能全部出去就看这个算法的时间复杂度。在实际中，随机产生的时间无法估量，但可以想象得到，每天每人出去的概率是百分之一，所以某人出去的期望值是100天一次，也就是说100*100天全部数学家能出去是最理想的，看来27年的岁月得耗在里头了！）

看不懂编程的人看如下文字说明：
设第一个放风的人为Q，Q作为哨岗，只能他将开关保持开着的状态。也就是到他放风时候，见开关开着就继续让它开着，见开关关着就把它打开，记录一次；
其它出去的人一般对待。如果这些出去，见到开关开着，并且自己没有关过开关就将它关掉；如果见到开关着，就不管它保持它的原有状态。
这样，也就是关掉开关的人都是第一次关开关，也就当他第一次出去放风。这时候其他第一次放风的人看到自己前边有第一次放风的人关掉了开关，就算作自己没有出来放过，也就不动开关了。正是这样，哨岗Q所记录的都是第一次出去的人，除掉自己外，再记录99次开关有过关着的状态，所有人就至少放风过一次了！

楼上诸位中只有三楼的说得接近（也可能是正确思路，没说明白），其他的各位要么是没有正面回答，要么是没认清题目，考虑周全

1.如果数学家可以选择每天谁出去放风的话，那就按照编号每人出去一次，第100天就报告。

2.如果数学家不可以选择每天谁出去放风的话：
2.1 如果希望早点放大家出来，只能冒险牺牲掉一些数学家了。1年2年之后，大家就自愿打报告吧，大不了牺牲几个了。

2.2 如果不能接受任何数学家的死亡。那就需要只能用多年的时光来等待，策略如下：

先考虑只有三个数学家被关押的情况，A,B,C三人。如果没有路灯的话，A每天只能知道要么是自己出去，要么是其他两个人中某个人出去。A列布尔表达式是，方程1：A=1,方程2：B+C=1。其中1表示出去过，0表示没出去过。每个人的方程都类似，对每个人来说，三元方程组却只有2个方程，不可解。所以引入路灯一元变量。我们这样来做：确定若A出去放风则开灯，那么当B或者C出去的时候就知道A出去过了，并且随手关灯，呵呵。对于B来说，如果自己出去过两次，一次灯亮，一次灯不亮，那么他就知道亮的那次是A出去，不亮的那次是C出去，可以打报告了。

对于100个数学家，情况略有不同。如果只是让A出去的时候点灯，每个人的方程组还是不可解，因为方程不够。如果让奇数编号的人出去的时候点灯，偶数的人出去不点灯，每个人得到的方程组还是无法解，因为100元方程组却没有几个方程。只能借助日期，编排一张轮流表，比如说第一天前50人中任何人出去的话就点灯；第二天后50人中任何人出去就点灯；第三天1-25，50-75号中任何人出去点灯，一次类推。这样子的话，对于每个数学家，他每次出去都会得到一个新的方程，比如说第一次出去知道是前50人中的一个人出去过，下一次知道后50人中出去过一个人，一次类推，等他积累了足够的方程了，放到一起就能知道100个人每个人到底谁出去过。

OK,我先来分析一下题目
要点有1、随记，也就是说这个不是由犯人决定，而是由监狱决定，完全无法避免不重复。
2、可以商量一次，在进去以前。
3、路灯显示，路灯的开关情况是可以被所有人看见的。都是数学家。

由以上几点可以推断上面部分答案是错误的，还有一部分我没有看懂。

但是问题并不复杂。答案如下：
商量好，任何一个人如果被随机挑选到放风，那么他第一次就把灯打开，走的时候把等关上，如果他第二次，第三次以及更多次被选上去放风时，则不要开灯。
这样，就可以保证灯亮的每一次都有一个人是第一次去放风，也就是说当灯亮到100次时，100个人已经都去放过风。

为了安全起见，我们还可以来一个验算机制，首先，所有人都应该对于灯被打开的次数进行记录，当100次亮灯的第二天，防风者如果记录的次数是100，那么他可以通过当天反复亮灯以表示达到100，如果这样连续3天，就表示有3个人得到的答案都是100，应该可以保证，如果没有连续，那么继续验算，当然，这个时候还是取平均值，看得到答案是100的人有多少，如果比例达到一定程度就可以确定了啊。
验算是保险起见，不在答案范畴内。

方法2：商量时，自己编号，1到100，当天放风者通过开关灯来表示编号，即亮一次表示1号，两次表示2号，以次类推，所有人做记录，当所有编号满了的时候就表示所有人都去过了。

验算方法通上，不过改一下表示方法，不亮灯表示已经算满。

从节能的角度出发，采取方法1，如果灯一不小心坏了，算他们倒霉，但是等灯好了还是可以继续撒。如果灯关不了，就惨了，方法1不行，方法2仍然可以实行。

楼上那些什么数过100下开关灯什么的能不能专心看下题目啊!!!!什么叫完全隔绝!!!!!题目都没看清就瞎答!来搞笑的吧!!!!
2楼的更搞笑,什么叫随机,上小学没有啊!
我想应该是编程序的,写起来比较复杂,你找些编程的书看就O了!开关既0和1!
但我不会编程,所以用其他方法!说好第一个出去的人负责统计(也只有他可以把灯打开!!!),他出去后把灯打开,然后后面出去的人把灯关了,如果重复出去的不能把灯关了,只有第一次出去的才能关灯!当第一个出去的人统计自己开了100次灯时就能去报告了!
如果还不清楚就在问题补充说一下!

---

细河区19367102521： 号称是美国高考的题:100个囚犯,国王准备赦免他们的机会,准备100顶红蓝帽子那啥的问题.求指教.有一个监狱,关押着100个死囚,这天国王心情好大... - ？
源杨氨酚：[答案] 若只能说“红”或者“蓝”两个字的话,想了半天,最好的办法就是你的方案一了(也许还有更好的,但实在想不出).用你的方案一的话,死的人会比最小比例小一些.因为若蓝色是最小比例,有30个,那最多有30组异色,就是死30人.而实际情况,...

细河区19367102521： 谁给我来几道超级考验智商的题目? - ？
源杨氨酚： 国王招来100个囚犯,对他们说:你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会.15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见、看不到,连时间...

细河区19367102521： 100个囚犯的智力测试题 - ？
源杨氨酚： 囚犯们按照顺序站成一排依次从左边或者右边开始观察其它囚犯是否有相同数字的帽子,如果观察到有至少一对相同数字的帽子,那么就直接出列,后面的人不用再观察他.如果没有观察到有相同数字的帽子则往前一步(表示他观察结束没有发...

细河区19367102521： 高智商的推理问题？
源杨氨酚： 他们要进去坐牢的时候选择一个人负责,比如叫A.对他讲好(最好选一个记性比较好的人,因为这样的时间是要很久的): “你每次出来只能关灯.其他所有人只能出来开灯一次,就算是你出来灯是关着的,但是你已经开过灯了,那么再也不能开灯了,如果出来灯是关着的,你还没有开过灯就开,是关着的就代表是别人开的,你就不要动.每个人不是第一次出来的话,就不要动灯的开关,就当没有这次出来.所以你每次出来就关灯,如果你出来灯是关着的,那么表示你在你上次出来之后,没有新人出来,所以你这次不要动,不要计数,知道你这样关了100次(如果他是第一次出去的人,而且原来灯就是开着的,那么99次就不够,所以要100次关灯),就代表全部人都出来过了.”

细河区19367102521： 推理~高智商进噢~国王招来100个囚犯,对他们说:你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会.15分钟以后,你们将被... - ？
源杨氨酚：[答案] 他们要进去坐牢的时候选择一个人负责,比如叫A.对他讲好(最好选一个记性比较好的人,因为这样的时间是要很久的): ... 没有新人出来,所以你这次不要动,不要计数,知道你这样关了100次(如果他是第一次出去的人,而且原来灯就是开着的...

细河区19367102521： 挑战智商 一个超难的囚徒问题! - ？
源杨氨酚： 没有百分百的方案.那个“模加法”的方案,只要假设除最后一个为1,其他全为0,他的方案就OVER了.这个应该不是超难,而是无解吧.

细河区19367102521： 智商难题,我就不信这里没高手 - ？
源杨氨酚： 等第一个人又被抽到第二次出去,他如果没有开过灯,打开,此时下一个出去的人看到灯是关的,他出去后首先在第一天,将灯关掉;开过:1 只有第一个出去的人有权力关灯2 每个人只有一次开灯机会这样等第一个人第99次关灯时,不要管………………………………以此类推,也就是遵循以下原则,让所有犯人按秒数数,后面出去的人看到灯是开的不要关, 第二个出去的人把灯打开,让灯处于关着的状态,以此方法第一天放风的囚犯可以知道自己是第一个.然后

细河区19367102521： 求正确答案囚犯活命问题简介:一道真正难倒亿人的智力题,这是微软的面试题. - ？
源杨氨酚： 按这种规则,囚犯就不去抓了,最后打破规则,因为大家都是死路一条.★★★证明如下:★★★ 假设第1个囚犯取了x颗,第2个囚犯取了y颗,则第3个囚犯知道第1、第2个总共拿了(x+y)颗,那么他为了保命,一定选择最接近(x+y)/2的整数颗,同理,...

细河区19367102521： 智力题9(五个囚犯)——一道真正难倒亿人的智力题,这是微软的面试题. - ？
源杨氨酚： 一.第一个人肯定不会取>20个的,否则后面的人肯定取比他小的数,最后他就是最大的那个必死.二.当第一个人取小于20个的时候,第二个人根据剩下的数目就知道只能取与第一个人的数目只差不超过1; (因为相差超过1的时候后面的...

细河区19367102521： 智力题100囚徒问题(经典谜题,有必要让大家知道) - ？
源杨氨酚： 假设初始灯为关.把100个囚徒分成A和其他99人. A如果看到灯关着,就打开. 其他人:(这个描述比较混乱):如果其他人中任何一个,出来时看到灯开着,并且自己从来没有关过灯,那么,就把灯关了,如果看到灯关着,或者灯开着但是...