魔方吧·中文魔方俱乐部

标题: 开关与亮灯问题（已解答） [打印本页]

作者: lulijie 时间: 2009-11-8 17:25:45 标题: 开关与亮灯问题（已解答）

A、B、C、D、E五个开关都是触摸式开关（即只要被按过，就一直保持开通状态），初始五个开关都处于断开状态。
现在每次随机按一个开关，求平均按多少次（期望值）开关，灯会亮？（任一开关被选择的概率都相等）
---------------------------------------------------------------------------------------------
对于一般情况(n+m)：
答案见26楼（递推公式见21楼）
化简答案见28楼
对公式的解释见29楼
基本知识见贴【囚徒放风问题系列之二】
http://bbs.mf8-china.com/viewthread.php?tid=42245&;extra=page%3D1

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

附件: 3.JPG (2009-11-8 17:25:45, 9.65 KB) / 下载次数 70
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NzYzMjh8ODEwMmQ3OTF8MTc0MDgwMDE2OXwwfDA%3D

作者: Paracel_007 时间: 2009-11-8 17:30:27

我最不懂的就是概率了

作者: tm__xk 时间: 2009-11-8 20:55:29

7/2 ?
字数字数字数字数....

作者: 乌冬仔 时间: 2009-11-8 21:00:42

上楼的7/2..本来就不合题意！

作者: tm__xk 时间: 2009-11-8 21:06:34 标题: 回复 4# 的帖子

何解?
字数字数字数字数....

作者: 骰迷 时间: 2009-11-9 17:51:47

能解釋一下麼..樓上是怎麼求的

作者: himan 时间: 2009-11-9 17:55:17

概率是最让人头疼的题目``````

作者: superacid 时间: 2009-11-9 18:07:04

看来LZ是概率高手啊

作者: 骰迷 时间: 2009-11-9 18:19:57

問一個問題：如果電制第二次碰觸會關掉，那麼期望值是不是無限？

作者: dhlsoft 时间: 2009-11-9 18:25:44

。。。。。忘得差不多了，记得好像高三学的吧。。。。。。。。挺简单的题。。。。。就是忘了怎么做了。。。。。

作者: superacid 时间: 2009-11-9 19:12:28 标题: 回复 10# 的帖子

高三学的有这么难吗？

作者: tm__xk 时间: 2009-11-9 20:19:24

3L MS理解错误了....
待我重新算....

作者: Cielo 时间: 2009-11-10 01:45:27

相当于 coupon collector's problem 的推广吧？

先只考虑上面一条，设 n(>0) 次还没把上面一条变为通路的概率：
a[sub]n[/sub] = 3*(2/3)^n-3*(1/3)^n = (2^n-1)/3^(n-1)；
n(>0) 次还没把下面一条变为通路的概率：
b[sub]n[/sub] = 2*(1/2)^n = 1/2^(n-1)

n(>0) 次还没把任意一条变为通路的概率：
∑a[sub]m[/sub]*b[sub]n-m[/sub]（也许还要乘系数，待修改）

用 1 减去上式，然后再求期望（待补充）

作者: tm__xk 时间: 2009-11-10 02:49:59

21/4=5.25........
看来这次我终于没算错了........

[ 本帖最后由 tm__xk 于 2009-11-10 06:57 编辑 ]

作者: superacid 时间: 2009-11-10 09:18:27

算错了...

[ 本帖最后由 superacid 于 2009-11-10 20:35 编辑 ]

作者: 外野手 时间: 2009-11-10 11:07:24

就列举法貌似很简单
不考虑顺序的情况下
按2次亮灯有1种可能；
按3次亮灯有4种可能；
按4次亮灯有5种可能；
考虑顺序
按2次亮灯有1×2=2种情况；
按3次亮灯有4×6=24种情况；
按4次亮灯有5×24=120种情况；

总的按开关次数是4+72+480＝556
总的可能数是146次
答案：556/146＝3.81

作者: superacid 时间: 2009-11-10 13:27:46

原帖由 外野手 于 2009-11-10 11:07 发表
就列举法貌似很简单
不考虑顺序的情况下
按2次亮灯有1种可能；
按3次亮灯有4种可能；
按4次亮灯有5种可能；
考虑顺序
按2次亮灯有1×2=2种情况；
按3次亮灯有4×6=24种情况；
按4次亮灯有5×24=120种情况；
...

你题目理解错了，另外，就算理解正确最后的计算也是有问题的...

[ 本帖最后由 superacid 于 2009-11-10 13:30 编辑 ]

作者: tm__xk 时间: 2009-11-10 19:41:31

我编程验证过,5.25MS挺合理的....

作者: lulijie 时间: 2009-11-10 19:43:36

14楼的答案是正确的。
用电脑模拟按开关过程一百万次，求得的平均次数是
5.25128100000008
当然可以直接计算出准确的值。
14楼tm_xk 最好能写出计算过程，这样大家可以交流解题思路和技巧，从中找出最简便的方法，对大家都有益处。
-----------------------------------------------
发帖的目的不是考大家，难为谁，不是比谁厉害，而是通过交流，学到好的解题方法，启迪思维，从中获得益处。

作者: lulijie 时间: 2009-11-10 19:45:57

本题属于3+2类型，记作f(3,2)=5.25
若为n+m，那么期望值f(n,m)又是如何呢？

作者: tm__xk 时间: 2009-11-11 00:50:57

接20L思路:
在m+n型中,若已有i+j的开关已开,记仍需的步数期望为f(m,n,i,j).
由于m和n给定,故下简记为f(i,j)....(此处定义与20L不甚一致....)
易知初始值为f(m,j)=f(i,n)=0,状态转移方程为f(i,j)=((m-i)*f(i+1,j)+(n-j)*f(i,j+1)+(m+n))/(m+n-i-j).
由此,f(0,0)即为所求.

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

大家能否不要过多地用计算机？

作者: lulijie 时间: 2009-11-11 14:56:39

tm__xk ：能不能写出 f(n,m)的计算表达式，用含n、m的式子。
用递推公式来解，对于较小的n、m值，如本题f(3,2)，可以手动写出精确值，
但n、m较大时，只能利用电脑来算了。
-----------------------------------------------------------------------
本题另有一种巧妙的解法，直接就可写出答案，根本不需要电脑，大家不知能不能想到。
我可是前后想了4天4夜，快认为没着时突然冒出了新思路，有一种佛学中顿悟的味道。

作者: tm__xk 时间: 2009-11-11 19:59:54 标题: 回复 23# 的帖子

如果是这样,那最起码这个递推式可以算出简单的通项公式..

作者: lulijie 时间: 2009-11-11 20:17:27

对了，通项公式很简洁，老兄找找看？
或者先解出一些结果，看看规律？

作者: tm__xk 时间: 2009-11-11 21:09:52

(m+n)*(sum('1/i','i'=1..m)+sum('1/i','i'=1..n)-sum('1/i','i'=1..m+n))....?

作者: tm__xk 时间: 2009-11-11 21:18:02

从囚犯二的结果来看,26L是对的....
不过我确实是从那个递推公式弄出来的....

作者: lulijie 时间: 2009-11-11 21:18:42

老兄厉害，我花了4天4夜的时间，老兄就1个晚上就搞出来了。
上式可化简为
(m+n)*[ sum( '1/i-1/(n+i)' , 'i'=1..m ) ]
----------------
如：f(3,2)=5*(1+1/2-1/4-1/5)=21/4
f(5,3)=8*(1+1/2+1/3-1/6-1/7-1/8)

作者: lulijie 时间: 2009-11-11 21:23:30

还是就囚犯二来说吧
条件：当所有的男囚徒都放过风或所有的女囚徒都放过风后就将大家全部释放。
----------------------------------------------------------
计算公式(m+n)*(sum('1/i','i'=1..m)+sum('1/i','i'=1..n)-sum('1/i','i'=1..m+n))
对该公式的解释是：
所求的期望值=所有男囚犯都放过风的期望值+所有女囚犯都放过风的期望值-所有囚犯都放过风的期望值

作者: superacid 时间: 2009-11-11 21:30:30

如果是三组开关怎么办？

作者: tm__xk 时间: 2009-11-11 21:30:34

回28L:我算的时候就是用这个形式..我是为了让m和n对称才那样写的....
而且我有用电脑....省了我几分钟时间....

回29L:囚犯二+容斥原理..

作者: tm__xk 时间: 2009-11-11 21:32:57

回30L:囚犯二+容斥原理就可以了吧?

作者: 五叶草 时间: 2009-11-11 21:37:17

我不懂。。。。。。。

作者: superacid 时间: 2009-11-11 21:38:34

我傻了...

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