国王和100个囚犯

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放： 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部关到死。

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

public interface Demo {
	
	public void doBool(); 

}

public class Demo2 implements Demo{
	
	/**
	 * 普通囚犯
	 * 第一次见灯开着时关掉
	 * 无论出去多少回，只能关灯一次
	 */
	
	public int count = 0;
	public boolean first = true;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(Test.bool && first){
			Test.bool = false;
			first = false;
		}
		count++;
	}
}

public class Demo3 implements Demo{
	
	/**
	 * 计数员
	 * 出去后就开灯
	 * 如果开着就不去动他
	 * 
	 * 直到第99次出去关灯的时候就是100个人都出去过了
	 */
	
	public int closeCount = 0;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(!Test.bool){
			Test.bool = true;
			closeCount++;
			if(closeCount == 99){
				Test.ok = true;
			}
		}
	}
}

public class Test {

	public static boolean bool = false;
	public static boolean ok = false;

	public static void main(String[] args) {
		int num = 0;
		int count = 0;
		Demo[] demo = new Demo[100];
		Demo2 demo2;
		for (int i = 1; i <= 99; i++) {
			demo2 = new Demo2();
			demo2.name = "d" + i;
			demo[i - 1] = demo2;
		}
		Demo3 demo3 = new Demo3();
		demo3.name = "d100";
		demo[99] = demo3;

		while (true) {
			num = (int) (Math.random() * 100);
			demo[num].doBool();
			count++;
			if (ok)
				break;
		}

		for (int j = 0; j < demo.length - 1; j++) {
			Demo2 d2 = (Demo2) demo[j];
			System.out.println(d2.name + ":" + d2.count);
		}
		System.out.println("执行次数:" + count);
	}
}

代码写的不好。

评论

25 楼 tedeyang 2010-01-14  

ageha67 写道

解题的思路差不多是这样子。。至于大概多少年能出来没仔细研究。。
题目中有说“这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门”。。这意味着，可以指定被关进去后的第一天有且只有一个人被放出来——那么，就可以约定，找个人就是负责计数的囚犯；另外，由于负责计数的人可以确定、灯的初始状态也不会影响到——比如按照LZ的算法，如果第一天出来的囚犯、也就是负责计数的人，不论是看到灯是亮、是灭，都把它熄灭，然后再按LZ的思路去处理，不会有问题的。。

题目中提到：“完成封闭，隔绝，囚犯不知道时间”，所以这第一天也是无从判断的。

24 楼 ageha67 2010-01-14  

解题的思路差不多是这样子。。至于大概多少年能出来没仔细研究。。
题目中有说“这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门”。。这意味着，可以指定被关进去后的第一天有且只有一个人被放出来——那么，就可以约定，找个人就是负责计数的囚犯；另外，由于负责计数的人可以确定、灯的初始状态也不会影响到——比如按照LZ的算法，如果第一天出来的囚犯、也就是负责计数的人，不论是看到灯是亮、是灭，都把它熄灭，然后再按LZ的思路去处理，不会有问题的。。

23 楼 pujia12345 2010-01-14  

呵呵，语法不好，见谅

22 楼 shadowlin 2010-01-14  

pujia12345 写道

package KingOfPrisoners;
public class State {
private static int sumDay;//大家在牢房的日子
private static boolean light;//院子灯的状态
public static  int getSumDay() {
return sumDay;
}
public static boolean getLight() {
return light;
}
public static void setLight(boolean light) {
State.light = light;
}
public static void addDay(){
State.sumDay++;
}
    public static void setSumDay(int sumDay) {
State.sumDay = sumDay;
}
}

----------------------------
package KingOfPrisoners;
public class Prisoners {
    private String name;//姓名：15分钟时间商量谁是计数员(谁进院子看到灯是灭的就开亮)
private int outTimes;//该人出去过的次数：主要看看是否是首次出去
private int judgementNumber;//该人敢于判定当前已经出去过的人数(重复出去的算一人)：主要是计数员使用

public Prisoners(String name){
this.name=name;
}
public void out(){//出牢房到院子去
State.addDay();//时间过去了一天
if("计数员".equals(name)) { //如果是他们内定的“计数员"
if(State.getLight()==false) {//这个“计数员"进院子发现灯是灭的，就开灯，并将进院子的人数+1
State.setLight(true);
judgementNumber++;
}
}
else{//进院子的不是“计数员"
if(outTimes==0){//如果是首次进院子
if(State.getLight()==true)//发现灯是开着的，就关灯
    State.setLight(false);
else {outTimes=0;return;}//如果发现灯本来就是开着的，那就说明在你前面有人第一次来过并且中间计数员没有来计数，那你就认为自己这次不算是第一次来把。
}
else {//非首次进院子，不做动作
}
}
outTimes++;//自身出去次数+1
}

public boolean gameOver() {
//if("计数员".equals(name)) System.out.println(name+"    "+outTimes+"    "+judgementNumber+"    "+State.getSumDay());
if("计数员".equals(name) && judgementNumber==99){
return true;
}
else return false;
}
}
-------------------------
package KingOfPrisoners;

import java.util.*;

public class Game {
private Prisoners[] p;
public Game(){
p=new Prisoners[100];
State.setLight(true);
for(int i=0;i<99;i++){
p[i]=new Prisoners("囚犯"+i);
}
p[99]=new Prisoners("计数员");
}
    static public void main(String[] str){
    Set<Integer> set=new TreeSet<Integer>();
    for (int i=0;i<10000;i++){//测试10000次，看看最短 最长需要多少时间，计数员能确认大家都安全自由了
    Game game=new Game();
    while(true){
    int random=(int)(Math.random()*100);
    game.p[random].out();
    if(game.p[random].gameOver()==true) break;
    }
    set.add(State.getSumDay()/365);
    State.setSumDay(0);
    }
    System.out.println(set);
}
}
Result
[18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
按楼主算法 大概范围就在15-40年

ls的名字起错了吧。。。应该是PrisonersOfKing

21 楼 pujia12345 2010-01-14  

package KingOfPrisoners;
public class State {
private static int sumDay;//大家在牢房的日子
private static boolean light;//院子灯的状态
public static  int getSumDay() {
return sumDay;
}
public static boolean getLight() {
return light;
}
public static void setLight(boolean light) {
State.light = light;
}
public static void addDay(){
State.sumDay++;
}
    public static void setSumDay(int sumDay) {
State.sumDay = sumDay;
}
}

----------------------------
package KingOfPrisoners;
public class Prisoners {
    private String name;//姓名：15分钟时间商量谁是计数员(谁进院子看到灯是灭的就开亮)
private int outTimes;//该人出去过的次数：主要看看是否是首次出去
private int judgementNumber;//该人敢于判定当前已经出去过的人数(重复出去的算一人)：主要是计数员使用

public Prisoners(String name){
this.name=name;
}
public void out(){//出牢房到院子去
State.addDay();//时间过去了一天
if("计数员".equals(name)) { //如果是他们内定的“计数员"
if(State.getLight()==false) {//这个“计数员"进院子发现灯是灭的，就开灯，并将进院子的人数+1
State.setLight(true);
judgementNumber++;
}
}
else{//进院子的不是“计数员"
if(outTimes==0){//如果是首次进院子
if(State.getLight()==true)//发现灯是开着的，就关灯
    State.setLight(false);
else {outTimes=0;return;}//如果发现灯本来就是开着的，那就说明在你前面有人第一次来过并且中间计数员没有来计数，那你就认为自己这次不算是第一次来把。
}
else {//非首次进院子，不做动作
}
}
outTimes++;//自身出去次数+1
}

public boolean gameOver() {
//if("计数员".equals(name)) System.out.println(name+"    "+outTimes+"    "+judgementNumber+"    "+State.getSumDay());
if("计数员".equals(name) && judgementNumber==99){
return true;
}
else return false;
}
}
-------------------------
package KingOfPrisoners;

import java.util.*;

public class Game {
private Prisoners[] p;
public Game(){
p=new Prisoners[100];
State.setLight(true);
for(int i=0;i<99;i++){
p[i]=new Prisoners("囚犯"+i);
}
p[99]=new Prisoners("计数员");
}
    static public void main(String[] str){
    Set<Integer> set=new TreeSet<Integer>();
    for (int i=0;i<10000;i++){//测试10000次，看看最短 最长需要多少时间，计数员能确认大家都安全自由了
    Game game=new Game();
    while(true){
    int random=(int)(Math.random()*100);
    game.p[random].out();
    if(game.p[random].gameOver()==true) break;
    }
    set.add(State.getSumDay()/365);
    State.setSumDay(0);
    }
    System.out.println(set);
}
}
Result
[18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
按楼主算法 大概范围就在15-40年

20 楼 pujia12345 2010-01-14  

langshao 写道

pujia12345 写道

关键是，你如何知道自己是第一个出去的？
难道囚犯们给国王提议：
亲爱的陛下，我问有一个小小的要求，让我第一个出去吧。

因为不能确定计数员是那个，就全乱套。都认为自己是计数员，见到开灯就关，不就乱完了

15分钟商量的时候就可以指定计数员啦

嗯，看来还是没有理解好题目

19 楼 langshao 2010-01-14  

pujia12345 写道

关键是，你如何知道自己是第一个出去的？
难道囚犯们给国王提议：
亲爱的陛下，我问有一个小小的要求，让我第一个出去吧。

因为不能确定计数员是那个，就全乱套。都认为自己是计数员，见到开灯就关，不就乱完了

15分钟商量的时候就可以指定计数员啦

18 楼 pujia12345 2010-01-14  

关键是，你如何知道自己是第一个出去的？
难道囚犯们给国王提议：
亲爱的陛下，我问有一个小小的要求，让我第一个出去吧。

因为不能确定计数员是那个，就全乱套。都认为自己是计数员，见到开灯就关，不就乱完了

17 楼 langshao 2010-01-14  

public class Prisoner {
	/**
	 * 犯人数目
	 */
	private static final int PRISONER_COUNT = 100;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Random r = new Random();
		boolean lightStartState = r.nextBoolean(); // 被关进去时看到灯的状态（假设被关进去时都经过院子）
		boolean lightState = lightStartState; // 当前灯的状态
		boolean[] prisoner = new boolean[PRISONER_COUNT]; // 犯人，当出来放过风并且按照约定改变灯过的状态时，其值为true
		final int COUNTER_ID = r.nextInt(PRISONER_COUNT); // 任意指定计数员
		int counter = 0; // 计数员记下的出来放过风的犯人数目
		int days = 0; // 总共所花的天数
		while (counter < PRISONER_COUNT) {
			days++;
			int n = r.nextInt(PRISONER_COUNT); // 随机出来放风的犯人
			if (n == COUNTER_ID) {// 计数员
				if (!prisoner[COUNTER_ID]) {
					counter++;
					prisoner[COUNTER_ID] = true; // 计数员放过风
				}
				if (lightState != lightStartState) { // 灯非初始状态
					// 是有其他犯人出来放过风了
					lightState = lightStartState; // 将灯改回初始状态
					counter++;
				}
			} else { // 其他犯人
				if (!prisoner[n] && lightState == lightStartState) { // 犯人未改过灯的状态，且目前灯的状态和初始状态一致
					// 改变灯的状态，以告诉计数员他出来过
					lightState = !lightStartState;
					prisoner[n] = true;
				}
			}
		}
		// 检查结果
		int sum = 0;
		for (int i = 0; i < PRISONER_COUNT; i++) {
			if (prisoner[i]) {
				sum++;
			}
		}
		System.out.println(sum + "个犯人出来放过风");
		System.out.println("共花了 " + days + "天（" + days / 365 + "年）");
	}
}

16 楼 52356 2010-01-14  

这个问题我有几点看法：
1、囚犯不知道时间，也就是说他们不知道自己会是第几个人。根据条件，他们更不知道是第几天。
2、囚犯随机的放风。这里可能出现同一囚犯放风多次的情况。
3、那个路灯是他们唯一交流的工具。
4、现在最大的问题是不知道灯的初始状态。

我的办法：
1、指定计数囚犯。100囚犯中指定一个唯一的计数囚犯。
2、规则：
（1）所有囚犯除计数囚犯外，当他是第1次放风的时候，如果灯是关着的则设置灯为开，以后再放风，不干涉灯的状态。但第1次放风时，如果灯是开着的，则自己认为自己没放过风。
（2）计数囚犯统计灯开的次数，统计之后将灯关闭。计数到99时，结束。

细节解释：当计数囚犯第1次出门，如果灯是开着的。会有3种情况：1、灯默认是开着的，他是第1个放风的。2、灯是默认开着的，其他囚犯没有去碰开关。3、灯初始是关着的，一放风囚犯将它改为开。
现在问题出现了，由于不知道灯的初始状态，所以在计数囚犯计第1个数时是有误差的，误差为1人。但如果，计数囚犯放风时看到灯是关着的，那就万事大吉了。

15 楼 jy00105276 2010-01-14  

jy00105276 写道

tedeyang 写道

这需要用程序来算吗？应该只能用逻辑推理吧。

随机开门，那就考虑极端情况就可以了。
最快出来的顺序是：
   第一天囚犯A出来，第二天计数员出来。第三天囚犯B，第四天计数员，，，，这样99*2=198天就可以了。
最慢的顺序是：
    每天都是同一个门被打开，关到老死。
至于灯的初始状态倒是不影响任何东西。

初始状态影响很大啊 

计数员只有在知道初始状态的情况下，看到了非初始状态的情况才能计数一次

如果不知道初始状态的话

计数员有理由认为  每天随即的人都是他  并且状态一直没改变过

当然算时间范围是没关系的 198 ——正无穷

14 楼 jy00105276 2010-01-14  

。。。发重复了

13 楼 elan1986 2010-01-14  

楼上说的也有道理
这难道是面试题吗？

12 楼 tedeyang 2010-01-14  

这需要用程序来算吗？应该只能用逻辑推理吧。

随机开门，那就考虑极端情况就可以了。
最快出来的顺序是：
   第一天囚犯A出来，第二天计数员出来。第三天囚犯B，第四天计数员，，，，这样99*2=198天就可以了。
最慢的顺序是：
    每天都是同一个门被打开，关到老死。
至于灯的初始状态倒是不影响任何东西。

11 楼 ubotutwin 2010-01-14  

<div class="quote_title">showr 写道</div>
<div class="quote_div">晕 代码看不懂 <br><br>能说下思路么 ？</div>
<p> </p>
<p>         第一个出去的人的任务：开灯，且只负责开灯</p>
<p>         其他所有人的任务：关灯，且只负责关灯，且只在自己从未关过灯的情况下才可以关灯</p>
<p> </p>
<p>         这样第一个人经过无数次放风后，一共看到了99次关着的灯，他们就自由了</p>

10 楼 langshao 2010-01-14  

mountainhunter 写道

得考虑路灯刚开始 是亮 还是灭吧
不然有问题

就是，没说灯一开始是亮的还是灭的。

如果第一天出去的人就是计数员，那么他可以初始化灯的状态。但是他们都不知道时间，因此可能第二天出去的人还以为自己是第一天出去的，那就麻烦了。

如果他们在被关进去时都能看到灯的状态，那么问题就可以解决了。如果灯是灭的用楼上的程序就OK了，灯是亮的就要求所有人对灯的操作反过来。

9 楼 showr 2010-01-14  

晕 代码看不懂

能说下思路么 ？

8 楼 AntFlow 2010-01-13  

考虑用100个线程来模拟这个问题，结果出现了问题，总的次数总是在10000次左右。能否给每一个线程编号，然后用随机数来激活相应的线程？

7 楼 mountainhunter 2010-01-13  

得考虑路灯刚开始 是亮 还是灭吧
不然有问题

6 楼 yahreso 2010-01-13  

写了个试下。。测了10次，最快的用了22年276天……