魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: lulijie

开关与亮灯问题(已解答) [复制链接]

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老 十年元老

发表于 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)即为所求.

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2009-11-11 13:19:19 |显示全部楼层
大家能否不要过多地用计算机?
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-11-11 14:56:39 |显示全部楼层
tm__xk :能不能写出 f(n,m)的计算表达式,用含n、m的式子。
用递推公式来解,对于较小的n、m值,如本题f(3,2),可以手动写出精确值,
  但n、m较大时,只能利用电脑来算了。
-----------------------------------------------------------------------
本题另有一种巧妙的解法,直接就可写出答案,根本不需要电脑,大家不知能不能想到。
我可是前后想了4天4夜,快认为没着时突然冒出了新思路,有一种佛学中顿悟的味道。

使用道具 举报

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老 十年元老

发表于 2009-11-11 19:59:54 |显示全部楼层

回复 23# 的帖子

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

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-11-11 20:17:27 |显示全部楼层
对了,通项公式很简洁,老兄找找看?
或者先解出一些结果,看看规律?

使用道具 举报

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老 十年元老

发表于 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))....?

使用道具 举报

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老 十年元老

发表于 2009-11-11 21:18:02 |显示全部楼层
从囚犯二的结果来看,26L是对的....
不过我确实是从那个递推公式弄出来的....

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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)

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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))
对该公式的解释是:
    所求的期望值=所有男囚犯都放过风的期望值+所有女囚犯都放过风的期望值-所有囚犯都放过风的期望值

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2009-11-11 21:30:30 |显示全部楼层
如果是三组开关怎么办?
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 14:13

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部