看到一个有趣的问题,有兴趣的可以做一做
国王招来100个囚犯,对他们说:你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,
给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人
一间牢房,都与外界隔绝,什么也听不见、看不到,连时间都没法计算,更别说获得外界的
任何信息。(送饭除外,但也是不规律的送)
这所监狱有一个院子,每天会随机打开一间牢房的门,让那个囚犯到院子里来放风。院子里
有一盏路灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,
其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马
上修好,当然修理人员不会改变灯的状态(开或关)。
除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净(包括在灯上作的
任何记号)。
牢房是完全封闭的,院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。
好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放:
若干天以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体
释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人无法自圆其说,你们
就全部砍头。所以,要珍惜这次机会。如果你们永远做不到我的要求,你们就全部关到死.
现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。
==================================
灯的初始状态是开还是关,犯人们不知道。
请帮助这100个囚犯出监狱。
编程输出:
灯的初始状态:?(随机的)
向国王证明100人都已放过风的囚犯编号:?(由编程者指定)
出监狱时已经过了多少天:?(随机的)
其中
囚犯1号放风:?次(随机的)
囚犯2号放风:?次(随机的)
囚犯3号放风:?次(随机的)
......
囚犯100号放风:?次(随机的)
----------------解决方案--------------------------------------------------------
输入呢?怎么没输入?
我到现在还整不明白,说清楚些啊?
----------------解决方案--------------------------------------------------------
偶也不清楚,可能自己想吧,偶看到好玩,发来让大家瞧瞧~~
----------------解决方案--------------------------------------------------------
编程输出:
灯的初始状态:?(随机的)
向国王证明100人都已放过风的囚犯编号:?(由编程者指定)
出监狱时已经过了多少天:?(随机的)
其中
囚犯1号放风:?次(随机的)
囚犯2号放风:?次(随机的)
囚犯3号放风:?次(随机的)
......
囚犯100号放风:?次(随机的)
是不是写个程序模拟一下啊?
----------------解决方案--------------------------------------------------------
100个人可以设置成:
1.一个开灯人员(就是在灯灭的时候负责开灯)
2.其余人员只有在灯亮着的时候才把灯给关了(如果灯关着就不去动它)。并且这些人只能关一次灯,关过之后无论以后再出去看见什么状态的灯都不能去碰它。
这道题目可能轮到开灯人员的时候有两种情况
A.如果开灯人员第一次出去看见灯是亮着的时候,可以明确一点就是他是第一个放出去的,所以这种情况下就比较好处理。开灯员只需记录自己开灯的次数,当他第99次开灯的时候就能明确的知道所有人都出来过了。
B.如果第一次出去的时候灯是关着的话,就可能又有2种小情况的出现了:第一,灯是被其他囚犯中的一个给关了,这种情况下解法和大情况A一样,只需第99次打开灯就可以明确的知道所有人都出来过了。第二种情况是他还是第一个被放出去,但是灯的状态是暗着的,这个就比较麻烦了需要等到第100次开灯才明确的知道所有人都出来过了。基于大情况B开灯人员自己也不知道到底会是那种情况所以比较难以判定(因为如果开灯人员碰到B的第二种情况那么他到第99次就和国王说了,那么还有一个囚犯没出去过,这样就全军覆没了;但是如果盲目等第100次的话,如果是B的第一种情况,那么他们又都会老死了,也不好)
因此中和以上所有情况重新设置100人的分工:
1.还是设置一个开灯员
2.其余人员只有在灯亮着的时候才把灯给关了(如果灯关着就不去动它)。并且这每人能关两次灯,关过之后无论以后再出去看见什么状态的灯都不能去碰它。
这样一来当开灯员第198次开灯的时候(无论出现以上哪种情况)就可以确定所有人都出去过了。虽然时间上较长,但是可以保证所有人都100%活下来。
呵呵,以上方法不一定是最好的解决方法,但是我想这个方法至少可以全部活下来。望大家也发表下自己的看法。
模拟程序:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
int fun(int n,int count[])//n表示开灯人的编号
//count[N]存放每个囚犯的放风次数
{
int flag[N],i,days=0,OF; //flag[N]存放每个囚犯关灯的次数(0~2)
//days表示总天数,OF表示灯的状态(0,1)
for(i=0;i<N;i++)
{
flag[i]=0;
}
srand(time(NULL));
OF=rand()%2; //随机产生灯的初始状态0,1
while(count[n]<2*(N-1)) //开灯次数小于198次
{
i=rand()%100; //随机抽取人放风
if(i==n&&OF==0) //若抽到的人是开灯人,且灯为关,则开灯
OF=1;
if(i!=n&&OF==1&&flag[i]<2)//若抽到的人不是开灯人,且灯为开,
//且关灯次数小于2次,则关灯,关灯次数加1
{
OF=0;
flag[i]++;
}
count[i]++; //被抽取人放风次数加1
days++; //天数加1
}
return days;
}
int main()
{
int count[N],i; //count[N]存放每个囚犯的放风次数
for(i=0;i<N;i++)
{
count[i]=0;
}
printf("days=%d\n",fun(0,count));
for(i=0;i<N;i++)
{
if(i%5==0)
printf("\n");
printf("count[%2d]=%d ",i,count[i]);
}
return 0;
}
模拟的结果大概需要20000天,大概60多年,老都老死了!
----------------解决方案--------------------------------------------------------
呃,我刚从网上看到答案,您都做出来啦
----------------解决方案--------------------------------------------------------