锁定老帖子 主题:国王与100个囚犯
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (6)
|
|
---|---|
作者 | 正文 |
发表时间:2010-08-03
这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。院子里有一盏路灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。 除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净(包括在灯上作的任何记号)。 牢房是完全封闭的,院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。 好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放: 若干天以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人无法自圆其说,你们就全部砍头。所以,要珍惜这次机会。如果你们永远做不到我的要求,你们就全部关到死。 现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。 --------------------------- 思路: ·选被关后第一天出去的囚犯作为特殊的计数员 ·计数员被放出去,第一天将灯打开,今后每次放出去的时候,如果遇见灯是熄灭的,则将灯打开,并将记数加1 ·而其他囚犯为普通囚犯,普通囚犯如果被放出去,在第一次遇见灯是打开的时候将其关闭(其他情况,即遇见灯是熄灭或第2,3,4..次遇见灯是开着的时候什么也不做) 至于灯的初试状态没有什么关系,如果设成true,只需在day==0的时候加个判断就行了。。 import java.util.Date; import java.util.Random; public class King_100Prisoner { // 记数器(由记数员囚犯用来计数囚犯放出去的人数) public int count; // 记数员囚犯编号 public int counterman; // 用来标记1到50编号的囚犯是否被放过风且关过灯 public long _1_50 = 0; // 用来标记51到100编号的囚犯是否被放过风且关过灯 public long _51_100 = 0; // 标识灯是否亮着 public boolean isLightOn = false; // 标记经过的天数 public int day = 0; // 返回放风囚犯记数 public int getCount(){ return count; } // 返回经历的天数 public int getDay(){ return day; } // 囚犯被放风 public void releasePrisoner(int prisoner){ // 放出不明生物 if(prisoner>100 || prisoner<0){ System.out.println("放出不明生物"); return; } // 第一天被放风的做记数员 if(day==0){ counterman = prisoner; } String name = (prisoner==counterman)?"记数员":"囚犯" ; System.out.print("第"+day+"天: "+ name +prisoner + "放风..."); // 如果放风的是记数员 if(prisoner == counterman){ // 如果灯是关着的,将其打开,并且放风计数加1 if(!isLightOn){ isLightOn = true; count++; System.out.print("发现灯是关着的将放风计数+1"); } }else{ // 如果放风的是普通囚犯 // 如果囚犯未被放过风且关过灯 if((prisoner&_1_50)==0 && (prisoner&_51_100)==0){ // 第一次放风遇见灯时开着时,关灯,记录该囚犯放过风且关过灯 if(isLightOn==true){ isLightOn = false; if(prisoner<=50){ _1_50 = _1_50 | (0x1L<<(prisoner-1)); }else{ _51_100 = _51_100 | (0x1L<<(prisoner-1)); } System.out.print("第一次遇见灯开着,于是将灯关了,并且记住从此放风什么也不干了"); }else{ System.out.println("发现灯是关着的,什么也没干"); } }else{ System.out.println("已经放过风,关过灯,于是什么也没干"); } } day++; } public static void main(String[] args) { King_100Prisoner demo = new King_100Prisoner(); Random r = new Random(new Date().getTime()); int prisoner = 0; while(demo.getCount()<100){ prisoner = r.nextInt(100)+1; demo.releasePrisoner(prisoner); } } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2010-08-04
面向对象的思想有时候是很耗费资源的事情,看前面有人解决的时候将囚犯封装为一个类,100个囚犯就要构造100个对象,虽然更直观,但是总觉得不舒服
其实两个long变量(和起来有128位)就足以标记100个囚犯开灯的状态 |
|
返回顶楼 | |
发表时间:2010-08-04
算法难归难,有时挺好玩的。
|
|
返回顶楼 | |
发表时间:2010-08-04
题目是说被关进去后就不知道时间……那他们怎么知道自己是第一个被放出去的人呢?
|
|
返回顶楼 | |
发表时间:2010-08-04
晕,你自己想想你被关进去后,第一天释放的是你,你知不知道?
看问题不能太死哦~ |
|
返回顶楼 | |
发表时间:2010-08-04
请问结束的条件是什么,不明白
|
|
返回顶楼 | |
发表时间:2010-08-04
不知道,因为不知道时间,你不知道前面有谁被放出去了
|
|
返回顶楼 | |
发表时间:2010-08-04
对啊,那怎么判定每个人都已经出来过呢
|
|
返回顶楼 | |
发表时间:2010-08-04
while(demo.getCount()<100)
计数的囚犯第100次开灯的时候(如果初始灯是关闭的) |
|
返回顶楼 | |
发表时间:2010-08-04
最后修改:2010-08-04
如果灯的初试状态未知,可以这样:
import java.util.Date; import java.util.Random; public class King_100Prisoner { // 记数器(由记数员囚犯用来计数囚犯放出去的人数) private int count; // 记数员囚犯编号 private int counterman; // 用来标记1到50编号的囚犯是否被放过风且关过灯 private long _1_50 = 0; // 用来标记51到100编号的囚犯是否被放过风且关过灯 private long _51_100 = 0; // 标识灯是否亮着 private boolean isLightOn = false; // 标记经过的天数 private int day = 0; // 返回放风囚犯记数 public int getCount(){ return count; } // 返回经历的天数 public int getDay(){ return day; } // constructor public King_100Prisoner(boolean isLightOn){ this.isLightOn = isLightOn; } // 囚犯被放风 public void releasePrisoner(int prisoner){ // 放出不明生物 if(prisoner>100 || prisoner<0){ System.out.println("放出不明生物"); return; } // 第一天 if(day==0){ counterman = prisoner; if(!isLightOn){ isLightOn = true; } count++; // 第一天以后的日子 }else{ // 如果放风的是记数员 if(prisoner == counterman){ // 如果灯是关着的,将其打开,并且放风计数加1 if(!isLightOn){ isLightOn = true; count++; } }else{ // 如果放风的是普通囚犯 // 如果囚犯未关过灯 if((prisoner&_1_50)==0 && (prisoner&_51_100)==0){ // 第一次放风遇见灯开着,关灯,记录该囚犯放过风且关过灯 if(isLightOn==true){ isLightOn = false; if(prisoner<=50){ _1_50 = _1_50 | (0x1L<<(prisoner-1)); }else{ _51_100 = _51_100 | (0x1L<<(prisoner-1)); } // 遇见灯是关着的,什么也不做 }else{ // do nothing } // 如果囚犯已经关过灯 ,什么也不做 }else{ // do nothing } } } day++; } public static void main(String[] args) { King_100Prisoner demo = new King_100Prisoner(true); Random r = new Random(new Date().getTime()); int prisoner = 0; while(demo.getCount()<100){ prisoner = r.nextInt(100)+1; demo.releasePrisoner(prisoner); } System.out.println("需要"+demo.getDay()+"天"); } } |
|
返回顶楼 | |