魔方吧·中文魔方俱乐部

标题: 囚徒放风问题系列之二（已解答） [打印本页]

作者: lulijie 时间: 2009-11-10 21:10:46 标题: 囚徒放风问题系列之二（已解答）

有n个被判无期的囚徒，其中男囚徒m人。每天会有一个囚徒被随机地抽出来放风。
有一天国王实行大赦，决定：当所有的男囚徒都放过风后就将大家全部释放。
那么，平均多少天（期望值）后所有囚徒将重获自由？
--------------------------------
见7楼的解答

[ 本帖最后由 lulijie 于 2009-11-11 21:56 编辑 ]

作者: wendaomaye 时间: 2009-11-10 21:13:47

先沙发再想问题。。。。。

作者: 露天粮仓 时间: 2009-11-10 21:48:31

好难，不是一般的。难。。。

作者: superacid 时间: 2009-11-10 21:57:52

先占楼，有空了再算

作者: wangguo35367 时间: 2009-11-10 22:13:45

..................慢慢算

作者: lulijie 时间: 2009-11-10 23:09:54

我发这个贴的目的是给解答帖子【开关与亮灯问题】  做基础准备的。
--------------------------------------------------------------------------------------------
将结束条件    当所有的男囚徒都放过风后就将大家全部释放。
改为                当所有的男囚徒都放过风或所有的女囚徒都放过风后就将大家全部释放。
那么题目就等同于开关与亮灯问题。

作者: tm__xk 时间: 2009-11-11 01:52:41

既然如此,记号同那边....
初始值为f(m)=0,状态转移方程为f(i)=(n+(m-i)*f(i+1))/(m-i).
算出来有f(0)=n*sum(1/i,i=1..m).

作者: superacid 时间: 2009-11-11 13:13:03

...状态转移方程...

作者: tm__xk 时间: 2009-11-11 20:01:15 标题: 回复 8# 的帖子

一时冒出了这么个词....
还是说递推公式吧....

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)