论坛首页 Java企业应用论坛

国王和100个囚犯

浏览 36152 次
精华帖 (0) :: 良好帖 (10) :: 新手帖 (0) :: 隐藏帖 (8)
作者 正文
   发表时间:2010-02-08  
刚才小改了一下程序,变成暴君!
发现这帮哥们要50多年才能出来。

另:prisoner拼错了、、、
0 请登录后投票
   发表时间:2010-02-18  
我看这道题无非是围绕两种情况,一是初始灯是开的还是关的,二是那个计数员是不是第一个出去。现在他们商量计数员讲灯熄灭,其他人将灯打开。
  针对多种情况需要进行多种的分析:

1、灯初始是开的,计数员判断:无法知道这个情况是第一个出去还是已经有人将灯开过了:
如果他是第一个出去,那么他应该以第二次熄灯开始计算;
如果他不是第一个出去,那么他应该第一次熄灯就开始计算;

安全起见,针对灯初始时开的,应该从他第二次熄灯开始计算。

2、灯初始是关的,计数员判断:
如果他发现灯是关的,那么他可以判断是他第一个到来,并且灯初始时关的(没有第二种可能性了),那么他需不动灯状态,第二次熄灯开始计算;

如果发现灯不是关的,他的判断有多种情况:灯初始时开的,或者有人开过了,那么跟灯初始时开的情况一样,把灯熄灭,第二次再熄灭开始计算。



-------------------------------------------------

综合以上几种除了他第一次进去遇到灯是关的情况,都先熄灯,然后按照他第二次熄灯开始计算,算到99就是成功;


这是逻辑题目,做测试时候,10个人跟100个人没有区别,为了方便计算,可以把数目算成10个,以方便测试
0 请登录后投票
   发表时间:2010-02-20  
15-40年内万一有人死了怎么办呢
0 请登录后投票
   发表时间:2010-02-22  
这个好残酷啊
0 请登录后投票
   发表时间:2010-02-23  
基本上没有出来的可能也没法证明
0 请登录后投票
   发表时间:2010-03-18   最后修改:2010-03-18
计数人员遇到灯亮就关灯然后计数一次,非计数员的囚犯可以关灯两次是个好办法,结束条件是计数到198。
这样一来,如果初始灯是灭的非计数员的囚犯关灯99+99=198,计数员计数198,结束;
如果灯一开始是亮的计数员多记一次,非计数员的囚犯关灯99+98=197时计数结束,此时也可以保证每人至少关过一次灯了。
不过这样一来,等计数结束要50多年,而且假设这些年他们还一个都不是,万一一个倒霉的没关过一次灯就死了,大家就等不到那一天了。
0 请登录后投票
   发表时间: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+年。。。  估计都老死在里面了。
0 请登录后投票
   发表时间:2010-09-07  
这个题我06年的时候就见过,在蓝色经典论坛上给出了三种算法,其中一种我不是很明白,另外两种都是没问题的。

其实这是一个算法题,考的是算法,而不是结果,楼上好多同学都拘泥于这个结果,思维太僵化了。

还有就是,计数者并不需要一开始就指定,只要谁第一个出来放风,他就是计数者,无论灯的初始状态是什么,计数者把灯灭了就行。

这样,从第二个人开始,就不需要考虑计数者出来了没这个问题,后面的问题就好办了
0 请登录后投票
   发表时间:2010-09-07  
其实要这样 如果发现灯是开着的,则这次就不要计数!关着的时候才计数!!以为很有可能计数员连续出去两次
0 请登录后投票
   发表时间:2010-09-07  
确实,要是计数者连续出去两次的话,正常人都明白不能计数的,计算机还得加个判断
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics