| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1884 人关注过本帖
标题:[讨论]腾论题国王招来100个囚犯
只看楼主 加入收藏
zkkpkk
Rank: 2
等 级:论坛游民
威 望:5
帖 子:489
专家分:28
注 册:2006-6-17
收藏
 问题点数:0 回复次数:5 
[讨论]腾论题国王招来100个囚犯

国王招来100个囚犯,对他们说:你们犯的是死罪,但我给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见看不到,连时间都没法计算,无法获得外界的任何信息。
这所监狱有一个院子,每天只少随机(注意是完全随机)打开一间牢房的门,让一个囚犯到院子里来放风。院子里有一盏灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,灯泡和电路不会出故障。
除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净(包括在灯上作的任何记号)。牢房是完全封闭的,院子里的灯光在牢房里看不到。只有放风到院子里的人才能看到。
好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放
给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流,被关若干天后,你们中间如果任何一个人能够向我证明你们每个人都至少放风了一次,我就把你们放了,不然永远别想再出来。
好吧!这样吧,如果你们有谁现在可以告诉我这个方法,也就是能够证明你们每人至少放风一次的方法,我马上放掉你们!
其中一个囚犯想了几分钟,回答了这个问题,国王听后,如自己所说的把他们全部给放了。请问那个囚犯是用什么方法证明的?

目前比较可行的方法:
他们要进去坐牢的时候选择一个人负责A。对他们讲好: A每次出来只能关灯。
其他所有人只能出来开灯一次,就算你出来灯是关着的,但是你已经开过灯了
,那么再也不能开灯了,如果出来灯是关着的,你还没有开过灯就开,是开着
的就代表是别人开的,你就不要动。不是第一次出来的话,就不要动灯的开关
,就当没有这次出来。A每次出来就关灯,如果出来灯是关着的,那么表示在A
上次出来之后,没有新人出来,所以A不要计数,知道你这样关了100次就代表
全部人都出来过了。本来如果是A第一个出来99次就够了,但是无法预知那么这
样的最好情况是198天,大家都出来放风过,如果是最坏情况,那么就........




#include <iostream.h>
#include <stdlib.h>

class Test
{
private:
int _pA; //囚犯A的关灯记忆
int _day; //经历的天数
bool _light; //灯的状态TRUE为开
int _arrP[100]; //数组的一个单元代表一间牢房
public:
//初始化成员变量
Test()
{
_pA=0;
_day=0;
_light=true;
_arrP[0]=2;
for(int i=1;i<100;i++)
_arrP[i]=0;
}
//返回服刑天数
int getDay(){return _day;}
//计算所有囚犯放风后所需要的天数
void count();
};

void Test::count()
{
while(!(_pA==100)) //当囚犯A计算开关次数100次的时候结束
{
int r=rand()%100; //随机产生牢房号
if(_arrP[r]==2 && _light==true) //如果出来的是囚犯A且灯亮则关灯并计数
{
_light=false;
_pA+=1;
}
else
{
if(_arrP[r]==0) //如果是其他囚犯并且灯是关着的则开灯并且他以后不再能做开关运动
if(_light==false)
{_light=true;_arrP[r]=1;}
}
_day+=1; //一天结束
}
}

//对类Test的测试
int main()
{
Test* _t=new Test;
_t->count();
int d=_t->getDay();
cout<<\"经历了:\"<<d<<\"天。\"<<endl;
return 0;
}

搜索更多相关主题的帖子: 囚犯 论题 国王 牢房 开关 
2007-11-12 23:22
longfeng867
Rank: 1
来 自:重庆
等 级:新手上路
威 望:1
帖 子:182
专家分:0
注 册:2007-5-20
收藏
得分:0 

class Test
{
private:
int _pA; //囚犯A的关灯记忆
int _day; //经历的天数
bool _light; //灯的状态TRUE为开
int _arrP[100]; //数组的一个单元代表一间牢房
public:
//初始化成员变量
Test()
{
_pA=0;
_day=0;
_light=true;
_arrP[0]=2; ///这句是什么意思?为什么要=2
for(int i=1;i<100;i++)
_arrP[i]=0;
}
//返回服刑天数
int getDay(){return _day;}
//计算所有囚犯放风后所需要的天数
void count();
};


在这个连处女膜都可以伪造的世界里,还有什么值得我相信!
2007-11-13 09:19
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
MS是ZJU上的题目

倚天照海花无数,流水高山心自知。
2007-11-13 23:20
数棋晕影
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2007-4-15
收藏
得分:0 
回复:(longfeng867)class Test{private: int _p...
2是做个标志,表示0号单元的囚犯为A,即负责计数的人
1表示囚犯出来过
0表示囚犯还没出来过

http://www./Main/default.asp 不可错过的人才招聘网
2007-11-15 20:38
Jacz
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2007-10-29
收藏
得分:0 
灯开始一定为开吗???

2007-11-15 21:55
zkkpkk
Rank: 2
等 级:论坛游民
威 望:5
帖 子:489
专家分:28
注 册:2006-6-17
收藏
得分:0 
以下是引用longfeng867在2007-11-13 9:19:49的发言:

class Test
{
private:
int _pA; //囚犯A的关灯记忆
int _day; //经历的天数
bool _light; //灯的状态TRUE为开
int _arrP[100]; //数组的一个单元代表一间牢房
public:
//初始化成员变量
Test()
{
_pA=0;
_day=0;
_light=true;
_arrP[0]=2; ///这句是什么意思?为什么要=2
for(int i=1;i<100;i++)
_arrP[i]=0;
}
//返回服刑天数
int getDay(){return _day;}
//计算所有囚犯放风后所需要的天数
void count();
};


假设这个是负责计算的囚犯


Viva,espana!
2007-11-15 22:55
快速回复:[讨论]腾论题国王招来100个囚犯
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.033817 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved