锁定老帖子 主题:国王和100个囚犯
精华帖 (0) :: 良好帖 (10) :: 新手帖 (0) :: 隐藏帖 (8)
|
|
---|---|
作者 | 正文 |
发表时间:2010-02-08
刚才小改了一下程序,变成暴君!
发现这帮哥们要50多年才能出来。 另:prisoner拼错了、、、 |
|
返回顶楼 | |
发表时间:2010-02-18
我看这道题无非是围绕两种情况,一是初始灯是开的还是关的,二是那个计数员是不是第一个出去。现在他们商量计数员讲灯熄灭,其他人将灯打开。
针对多种情况需要进行多种的分析: 1、灯初始是开的,计数员判断:无法知道这个情况是第一个出去还是已经有人将灯开过了: 如果他是第一个出去,那么他应该以第二次熄灯开始计算; 如果他不是第一个出去,那么他应该第一次熄灯就开始计算; 安全起见,针对灯初始时开的,应该从他第二次熄灯开始计算。 2、灯初始是关的,计数员判断: 如果他发现灯是关的,那么他可以判断是他第一个到来,并且灯初始时关的(没有第二种可能性了),那么他需不动灯状态,第二次熄灯开始计算; 如果发现灯不是关的,他的判断有多种情况:灯初始时开的,或者有人开过了,那么跟灯初始时开的情况一样,把灯熄灭,第二次再熄灭开始计算。 ------------------------------------------------- 综合以上几种除了他第一次进去遇到灯是关的情况,都先熄灯,然后按照他第二次熄灯开始计算,算到99就是成功; 这是逻辑题目,做测试时候,10个人跟100个人没有区别,为了方便计算,可以把数目算成10个,以方便测试 |
|
返回顶楼 | |
发表时间:2010-02-20
15-40年内万一有人死了怎么办呢
|
|
返回顶楼 | |
发表时间:2010-02-22
这个好残酷啊
|
|
返回顶楼 | |
发表时间:2010-02-23
基本上没有出来的可能也没法证明
|
|
返回顶楼 | |
发表时间:2010-03-18
最后修改:2010-03-18
计数人员遇到灯亮就关灯然后计数一次,非计数员的囚犯可以关灯两次是个好办法,结束条件是计数到198。
这样一来,如果初始灯是灭的非计数员的囚犯关灯99+99=198,计数员计数198,结束; 如果灯一开始是亮的计数员多记一次,非计数员的囚犯关灯99+98=197时计数结束,此时也可以保证每人至少关过一次灯了。 不过这样一来,等计数结束要50多年,而且假设这些年他们还一个都不是,万一一个倒霉的没关过一次灯就死了,大家就等不到那一天了。 |
|
返回顶楼 | |
发表时间:2010-08-02
最后修改:2010-08-03
import java.util.Random; public class Prision implements Runnable{ public static void main(String[] args) { Runnable[] _runTimes = new Prision[20]; for(int i = 0; i < 20; i++) { _runTimes[i] = new Prision(); _runTimes[i].run(); } } public void start() { int days = 0; int status = Prisoner.LIGHT_ON; Counter c = new Counter(); Prisoner[] _100Prison = new Prisoner[100]; Random r = new Random(); int j = r.nextInt(100); _100Prison[j] = c; for (int i = 0; i < 99; i++) { while (_100Prison[j] != null) { j = r.nextInt(100); } _100Prison[j] = new Fellows(); } while (c.getCounter() != 99) { j = r.nextInt(100); Prisoner p = _100Prison[j];// 随即放风一个犯人 days++; // 日子又过了一天。。。 status = p.turnLight(status); // 放风前灯的状态 } System.out.println("After " + days + "," + days/365 + " years,finally~"); System.out.println("Hooray, we are free!!"); } public void run() { start(); } } interface Prisoner { // return light status public int turnLight(int status); static final int LIGHT_ON = 1; static final int LIGHT_OFF = 0; } /** * Counter 第二次看到灯开了就计数,然后关闭灯; * * @author Darren * */ class Counter implements Prisoner { int count = 0; public int turnLight(int status) { int ret = LIGHT_ON; if (status == Prisoner.LIGHT_ON) { if (count == 2) // 第二次看到灯是亮着的 ret = LIGHT_OFF; // 关灯 count++; } return ret; } public int getCounter() { return this.count; } } class Fellows implements Prisoner { /** * 如果灯开着,就关掉。 */ public int turnLight(int status) { if (status == LIGHT_ON) return LIGHT_OFF; return LIGHT_ON; } } 平均要50+年。。。 估计都老死在里面了。 |
|
返回顶楼 | |
发表时间:2010-09-07
这个题我06年的时候就见过,在蓝色经典论坛上给出了三种算法,其中一种我不是很明白,另外两种都是没问题的。
其实这是一个算法题,考的是算法,而不是结果,楼上好多同学都拘泥于这个结果,思维太僵化了。 还有就是,计数者并不需要一开始就指定,只要谁第一个出来放风,他就是计数者,无论灯的初始状态是什么,计数者把灯灭了就行。 这样,从第二个人开始,就不需要考虑计数者出来了没这个问题,后面的问题就好办了 |
|
返回顶楼 | |
发表时间:2010-09-07
其实要这样 如果发现灯是开着的,则这次就不要计数!关着的时候才计数!!以为很有可能计数员连续出去两次
|
|
返回顶楼 | |
发表时间:2010-09-07
确实,要是计数者连续出去两次的话,正常人都明白不能计数的,计算机还得加个判断
|
|
返回顶楼 | |