关于国王和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次的值吻合！

 

 

评论

11 楼 yanghao0 2010-01-21  

开始 2010-01-21 17:56:30
运行2次,囚犯共100人
最小的是：9808天
最大的是：9959天
结束 2010-01-21 17:58:26

--
代码附件,可运行

请提意见

10 楼 bencode 2010-01-20  

哦，对， 我上面的方案有问题。
是我欠考虑，对不起：）

我晚上再好好想想，想不明白，再去看你的解决方案哈。谢谢。

9 楼 dch1287 2010-01-19  

bencode 写道

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

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

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

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

一开始灯开着

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

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

8 楼 bencode 2010-01-18  

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

7 楼 bencode 2010-01-18  

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

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

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

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

6 楼 dch1287 2010-01-18  

dch1287 写道

bencode 写道

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

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

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

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

5 楼 dch1287 2010-01-18  

bencode 写道

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

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

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

4 楼 bencode 2010-01-18  

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

引用

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风

3 楼 beike 2010-01-18  

不知道时间啊 老兄。

2 楼 bencode 2010-01-18  

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

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

1 楼 dch1287 2010-01-17  

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