关于国王和100个囚犯

今天在论坛看到一题目 国王和100个囚犯 http://www.iteye.com/topic/569275

 

大概在去年，朋友问过过我这个问题。

 

方案比较简单：

 

首先，第一天出来的人，担当“计数者”，它把灯开起来（原来开着就不必动了）

 

然后每天出来一个囚犯。

   

    如果他不是“计数者”，并且没有关过灯， 并且灯开着， 那么就把灯关了。

 

    如果他是“计数者”， 如果灯关了， 就把他开起来（计数+1）。 当然如果灯被关了99次， 那么就去和国王说吧。

 

 

但显然也是一个概论问题， 因为每次出来的囚犯随机，

 

现在问题是， 如果采用这个方案， 大概他们多久可以出来？

 

 先不忙着用数学进行计算， 我们用程序统计平均天数：

 

首先， 进行一次实验的天数是这样的：

 

	public static int escapeDays() {
		Random rand = new Random();
		
		int days = 1;	// 第一天
		int counter = rand.nextInt(100);  // 出来一个 计数者
		
		boolean light = true; // 开灯
		List<Integer> list = new ArrayList();	// 计数者知道关灯的次数 为 list.size()
		
		while (true) {
			days++; // 又过了一天
			int prison = rand.nextInt(100); // 出来一个囚犯
			if (prison == counter) { // 如果是计数者
				if (list.size() == 99) {  // 成功啦
					break;
				}
				if (!light) { // 灯关了，就把它开起来
					light = true;
				}
			} else {
				if (light && !list.contains(prison)) {	// 如果没有关过灯，并且灯开着
					light = false; // 就把它关了
					list.add(prison);
				}
			}
		}
		
		return days;
	}

 

然后我们让实验进行一万次。

 

	public static void main(String[] args) {
		int times = 10000; 	// 统计平均天数, 我们把这个实验做一万次
		int days = 0;
		for (int i = 0; i < times; i++) {
			days += escapeDays();
		}
		System.out.println("平均需要的天数：" + days / times);
	}

 

 

在我的电脑上输出：

 

平均需要的天数：10428

差不多是  28 ~ 29 年时间。超过无期徒刑了， 国王还真会玩, 要是被囚犯们知道， 直接撞墙自杀了。

 

 

让我们再用数学去计算一下：

 

首先，第一天出来的是“计数者”， 这是一个必然事件， 没啥好说的。

 

从第二天开始， 我们要完成以下过程 99 次

 

 

出来一个新的囚犯， 然后等待“计数者”出来把灯开起来。

 

 

第一次出来新的囚犯的概率是： 99 / 100 --- 除去计数者， 其他任何囚犯出来都满足要求

 

完成这一步的平均时间是 100 / 99  天

 

 

完成上面这个过程后，接着要求“计数者”出来，开灯。 这个概率是 1 / 100

 

完成这一步的平均时间是 100 天

 

 

第二次， 新囚犯出来的概率是 98 / 100

 

完成这一步的平均时间是 100 / 98

 

计数者出来的率还是 1 / 100

 

完成这一步的平均时间还是 100 天

 

...

 

第99次， 新囚犯出来的概率是 1 / 100 (只有一个囚犯没有出来了)

 

计数者出来的率还是 1 / 100

 

 

然后我们把时间加起来:

 

100 / 99 + 100 + 100 / 98 + 100 + ... 100 / 1 + 100

 

=  100 * 99 + 100 * (1 / 99 + 1 / 98 + 1 / 97 + ... + 1)

=  9900 + 100 * (1 + 1 / 2 + 1 / 3 + ... 1 / 99)

 

呼呼， 上面 1 + 1 / 2 + 1 / 3 + ... 1 / 99 这是一个调和级数 大概等于 ln 99 + 1 ，

 

当然可以用程序 很容易求得 值为: 5.177

 

所以上述值为： 10417

 

 

和上面程序测试10000次的值吻合！

 

 

题目的描述里面很重要的一点：
囚犯没有时间的概念，不能知道自己是第几天，第几个被放出来的！

那就在商量的时候。指定一个“计数者”

过程就从他出来的时候开始进行。这大概要多上一百天。

不知道时间啊 老兄。

囚犯不知道时间没关系，国王知道就行了。

"从他出来的时候开始进行" ?? 他如何知道自己是什么时候出来的，如果不知道，那么灯的初始状态就有关系了！！

最后要完成任务的是囚犯，而不是国王。国王知道有什么用？

比如我就是那个“计数者”，我是在15分钟内被大伙指定的。

然后某一天，我第一次被放出来。我不管灯是否开关。 我只要这次让灯开着。。

然后计数， 我只要以后出来。看到灯被关掉99次。 就可以了。

因为每个犯人只允许关灯一次。

国王当然要知道一天一天，因为他还要等每一天叫他的守卫去放人。。

一开始灯开着

第一天 某个其他人被放出来 按照大家商量的 他打关了灯 并且从今以后他再也不关了

某天你第一次被放出来 你看到灯关着 然后你打开了他 从这天起 你最多只能看到灯被关掉98次了