Question

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

哪位高IQ的大侠能帮忙解决这个问题呀，100分奖励！

一百个数学家被判无期徒刑,每天可随机一人到一场地放风，但得向警察报到。场地与牢房完全隔绝，但有一个废弃的路灯开关仍能正确表示开关。进牢房前，警察对他们说：“你们会被分别关进一百个牢房，相互间不准通信。如果有一天有人向我报告你们已经每人出去放风过至少一次，经过我查证属实，我就放了你们；果报告错误，我会杀了报告的人！进去之前你们有一次商量的机会！”

问：这些数学家有何命运？
他们是随机出去,谁出去谁不出去没有任务规律.所以一个人可能出去过好几次的同时,有人甚至一次也没出去过!
出去的人只有两种选择,要么使开关开着,要么使它关着.
关键是进去了之后,在不能再互相通信的情况下,怎么样通过开关的两种状态,就能知道所有的人都出去过!
而且要相当确信所有人都出去过,不然报告的人就要死了!有人死了他们之间也不会有人知道!

这是一个很有名的电脑公司的面试题目,没有我们想象的那么简单,但我确定,其中一定有解!
由于是各位是书面解释,加上我的理解能力有限,希望大家尽量说得明白一点,最好用ABC给他们编号来说明!

Answer 1

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

　　突破口：开关（但是是废弃的，也就是说不能当控制灯用了，这是题目出的巧妙性与完整性，不愧是大公司出的题目）,可以是开或关的两种状态，由于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次开关有过关着的状态，所有人就至少放风过一次了！

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

Answer 2

他们不是可以商量么？那就约定，按人编号，从一到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次开关有过关着的状态，所有人就至少放风过一次了！

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

Answer 3

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个人每个人到底谁出去过。

Answer 4

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

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

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

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

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

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

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

Answer 5

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