国王和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);
	}
}

代码写的不好。

评论

105 楼 xx167 2010-09-14  

不知道思路。。但是看了代码之后，会清晰很多。

104 楼 叩舷而歌 2010-09-14  

结果让人好伤心……太遥远太漫长了……

103 楼 snovian 2010-09-13  

灯的初始状态是什么？如果初始是关的呢？

102 楼 LeeHomWong 2010-09-12  

不是有15分钟的时间商量么，100个人先指定一个人负责开灯，其余的人只能关灯，每次得那指定的人来开灯，这要等到何年马月

101 楼 hong_kun 2010-09-11  

liyun_1981 写道

除了计算员计数到198次可以确保所有人都出来过，还有一种方法应该也行，呵呵。
我的思路是：
1、每个人第一次出来时都改变灯的状态并记住。
2、每个人以后每次出来只要看到灯的状态较上一次改变了就累加计数值1，然后改变灯的状态并记住。
3、任意一个人的计数值累加到99就可以确保每个人都出来过了。

你这样就是让这些囚犯都老死在那了，我觉得不是很好的思路。

100 楼 hadesmile 2010-09-08  

package com.azure.prisoner;

import java.util.ArrayList;

public class Algo3 {

	// 信号灯 囚徒只能开且开一次灯
	private boolean light;

	// 运行天数
	private int dayCount;

	// 囚徒个数
	private final int prisonerNum = 100;

	// 监狱
	private ArrayList<Prisoner> prisoners;

	private boolean debug;

	private String debugString;

	public static void main(String[] args) {
		int times = 100;
		double count = 0d;
		for (int i = 0; i < times; i++) {
			count += new Algo3().go();
			System.out.println("=============================");
		}
		System.out.println("运行" + times + "次，平均每次花费" + count / times / 365
				+ "年");
	}

	private int go() {

		light = true;
		dayCount = 0;

		// 初始化100个囚徒
		prisoners = new ArrayList<Prisoner>();
		for (int i = 0; i < 100; i++) {
			prisoners.add(new Prisoner(i));
		}
		// 初始化计数者数组
		Counter[] counters = new Counter[2];

		boolean find = false;
		// 循环，直到找到100个出去放过风的囚徒
		while (!find) {
			dayCount++;
			// System.out.print(dayCount + ":");

			// 随机抽取一个囚徒放风
			int random = (int) (Math.random() * (prisonerNum));
			Prisoner outedPrisoner = prisoners.get(random);

			// 取得时间片段
			int timePeriod = getTimePeriod();

			switch (timePeriod) {
			case 1:
				// 初始化交流片段
				System.out.println("==初始化交流片段==");
				counters[0].setCout(false);
				counters[1].setCout(false);

				if (light) {
					if (outedPrisoner instanceof Counter) {
						Counter c = (Counter) outedPrisoner;
						c.count++;
						c.debugString = c.debugString + "," + debugString;
						System.out.println(c.id + "找到 " + debugString + ",总计"
								+ c.count + "开灯");
					} else {
						System.out.println(dayCount + ":" + debugString + "被加到"
								+ outedPrisoner.id + "的cache中");
						outedPrisoner.cache++;
					}
					light = false;
				}
				break;
			case 2:
				// 结束交流片段
				System.out.println("==结束交流片段==");
				if (light) {
					System.out
							.println(dayCount + ":" + outedPrisoner.id + "关灯");
					light = false;
				}
				break;
			case 3:
				// 交流片段
				// System.out.println("交流片段");
				if (outedPrisoner instanceof Counter) {
					Counter c = (Counter) outedPrisoner;

					if (c.Cout) {
						break;
					}

					if (!light && c.count == 50) {
						light = true;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "关灯");
						c.setCout(true);

					} else if (light && c.count == 50) {
						find = true;
						System.out.println("\nSUCCEED!");
					}
				}
				break;
			case 4:
			default:
				// 计数片段
				// System.out.println("计数片段");
				if (counters[0] == null) {
					Counter counter = new Counter(outedPrisoner.id);
					light = false;
					System.out
							.println(dayCount + ":" + outedPrisoner.id + "开灯");
					counter.count++;
					prisoners.set(outedPrisoner.id, counter);
					counters[0] = counter;
					break;
				}

				if (counters[1] == null) {
					if (!outedPrisoner.equals(counters[0])) {
						Counter counter = new Counter(outedPrisoner.id);
						light = false;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "开灯");
						counter.count++;
						prisoners.set(outedPrisoner.id, counter);
						counters[1] = counter;
					}
					break;
				}

				if (outedPrisoner instanceof Counter) {
					Counter c = (Counter) outedPrisoner;
					if (light && c.count < 50) {
						c.count++;
						light = false;
						System.out.println(c.id + "找到 " + debugString + ",总计"
								+ c.count + "开灯");
						c.debugString = c.debugString + "," + debugString;
						debugString = "";
					} else if (!light && c.count > 50) {
						c.count--;
						light = true;
					}
					break;
				}

				// System.out.println("囚徒在放风");
				if (!light) {
					if (outedPrisoner.cache > 0) {
						debugString = "cache_" + outedPrisoner.id;
						outedPrisoner.cache--;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "cache--关灯");
						light = true;
					} else if (!outedPrisoner.isOut()) {
						outedPrisoner.setOut(true);
						light = true;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "囚徒关灯");
						debugString = outedPrisoner.id + "";
					}
				}
				break;
			}

			if (dayCount == 60000) {
				System.out.println();
				for (Prisoner p : prisoners) {
					System.out.println((p instanceof Counter) ? "counter"
							+ p.id + ":" + ((Counter) p).debugString : p.id
							+ ":" + p.isOut() + ":" + p.cache);
				}
				System.out.println(counters[0].count + ":" + counters[1].count);
				debug = true;
				System.exit(0);
			}
		}
		return dayCount;
	}

	public int getTimePeriod() {
		int period = 1000;
		int cPeriod = 200;

		if (dayCount % period == 0) {
			return 2;
		} else if (dayCount % period == (period - cPeriod)) {
			return 1;
		} else if (dayCount % period > ((period - cPeriod))
				&& dayCount % period < period) {
			return 3;
		} else {
			return 4;
		}
	}

	/**
	 * 囚徒类
	 * 
	 * @author Justis_ren
	 * 
	 */
	class Prisoner {

		public int id;

		// 是否有过有效放风
		private boolean out;

		public int cache;

		public Prisoner(int id) {
			this.id = id;
		}

		public boolean isOut() {
			return out;
		}

		public void setOut(boolean out) {
			this.out = out;
		}
	}

	class Counter extends Prisoner {
		private int count;
		private boolean Cout;
		public String debugString;

		public Counter(int id) {
			super(id);
		}

		public boolean isCout() {
			return Cout;
		}

		public void setCout(boolean cout) {
			Cout = cout;
		}
	}
}

99 楼 hadesmile 2010-09-07  

确实，要是计数者连续出去两次的话，正常人都明白不能计数的，计算机还得加个判断

98 楼 lz12366 2010-09-07  

其实要这样 如果发现灯是开着的，则这次就不要计数！关着的时候才计数！！以为很有可能计数员连续出去两次

97 楼 hadesmile 2010-09-07  

这个题我06年的时候就见过，在蓝色经典论坛上给出了三种算法，其中一种我不是很明白，另外两种都是没问题的。

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

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

这样，从第二个人开始，就不需要考虑计数者出来了没这个问题，后面的问题就好办了

96 楼 savegod 2010-08-02  

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+年。。。  估计都老死在里面了。

95 楼 lst00190 2010-03-18  

计数人员遇到灯亮就关灯然后计数一次，非计数员的囚犯可以关灯两次是个好办法，结束条件是计数到198。
这样一来，如果初始灯是灭的非计数员的囚犯关灯99+99=198，计数员计数198，结束；
如果灯一开始是亮的计数员多记一次，非计数员的囚犯关灯99+98=197时计数结束，此时也可以保证每人至少关过一次灯了。
不过这样一来，等计数结束要50多年，而且假设这些年他们还一个都不是，万一一个倒霉的没关过一次灯就死了，大家就等不到那一天了。

94 楼 faylai 2010-02-23  

基本上没有出来的可能也没法证明

93 楼 ziyu_1 2010-02-22  

这个好残酷啊

92 楼 maoxiaolu2000 2010-02-20  

15-40年内万一有人死了怎么办呢

91 楼 zoozooll 2010-02-18  

我看这道题无非是围绕两种情况，一是初始灯是开的还是关的，二是那个计数员是不是第一个出去。现在他们商量计数员讲灯熄灭，其他人将灯打开。
  针对多种情况需要进行多种的分析：

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

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

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

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



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

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


这是逻辑题目，做测试时候，10个人跟100个人没有区别，为了方便计算，可以把数目算成10个，以方便测试

90 楼 andsofish 2010-02-08  

刚才小改了一下程序，变成暴君！
发现这帮哥们要50多年才能出来。

另：prisoner拼错了、、、

89 楼 andsofish 2010-02-08  

国王

package com.xuz.persionbreak.gamecontrol;

import java.util.Random;

public class King {
	public static int getNum(){
		Random random = new Random();
		return random.nextInt(100) ;
	}
}

抽象类-犯人

package com.xuz.persionbreak.gamer;

public abstract class Person {
	
}

普通犯人

package com.xuz.persionbreak.gamer;

import com.xuz.persionbreak.lamp.Lamp;

public class Persioner extends Person{
	private int count = 0;
	
	public void controlLamp(Lamp lamp){
		if (count < 1) { //如果之前没关过
			if (lamp.getState() == 1) { //如果灯是开的
				lamp.setState(0); //关灯
				System.out.println("我关灯了，以后没我事了");
			} else {
				System.out.println("灯是关着的");
			}
		} else {
			System.out.println("我之前关过灯了");
		}
	}
}

计数员

package com.xuz.persionbreak.gamer;

import com.xuz.persionbreak.lamp.Lamp;

public class Counter extends Person{
	private int count = 0;
	
	private boolean isOpenLamp = false;
	
	public void controlLamp(Lamp lamp){
		if (lamp.getState() == 0) {
			if (isOpenLamp) {
				count++;
				lamp.setState(1);
				System.out.println("已经出来过"+count+"个哥们了");
			} else {
				lamp.setState(1);
				System.out.println("我第一次出来，开灯!");
				isOpenLamp = true;
			}
		} else {
			System.out.println("灯是开的");
		}
	}
	
	public int getCount(){
		return count;
	}
	
}

应用场景

package com.xuz.persionbreak.main;

import com.xuz.persionbreak.gamecontrol.King;
import com.xuz.persionbreak.gamer.Counter;
import com.xuz.persionbreak.gamer.Persioner;
import com.xuz.persionbreak.gamer.Person;
import com.xuz.persionbreak.lamp.Lamp;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int day = 0;
		
		Lamp lamp = new Lamp();
		lamp.setState(0);//一开始灯是关的
		
		Person[] foxRiver = new Person[100];
		for (int i = 0; i < foxRiver.length - 1; i++) {
			foxRiver[i] = new Persioner();
		}
		foxRiver[99] = new Counter();
		
		System.out.println("游戏开始");
		while (true) {
			day++;
			int random = King.getNum();
			System.out.println("放出"+random+"牢房的犯人");
			Person person = foxRiver[random];
			if (person instanceof Persioner) {
				((Persioner) person).controlLamp(lamp);
			} else {
				Counter counter = (Counter)person;
				counter.controlLamp(lamp);
				if (counter.getCount() == 99) {
					break;
				} 
			}
		}
		
		System.out.println(day / 365);
	}

}

作为一个仁主，我一开始就把灯关了。

88 楼 appleandwh1234 2010-02-05  

这个问题，不知道囚犯们知道不知道灯的初始状态。 如果知道那么稍微简单点，因为第一个出去的肯定知道自己是不是技数员，有他来计数就好了。

我来说说如果不知道灯的初始状态，大家看看我想的对不对，指定一个计数员，我们叫他老A。

规则是，只有老A可以开灯，其他人只能关灯，关过一次的人不允许再关。

当老A第一次出来后，他看到灯关着，肯定会想，灯是被第一个人关掉的，还是初始状态就是关掉的。 保险起见，就必须当成没有人出来过，然后那个第一个关灯的人，就必须再关一次，这样就不会漏了他。

然后就简单了，老A开灯，其他人关灯，当老A第99次看到灯被关了，就大功告成。

87 楼 jahcy 2010-02-04  

恩。。。那代码有错误，确实随即初始化灯状态不好搞！

我认错！！！

86 楼 jahcy 2010-02-04  

一百次。。。
max:12706
min:8010