魔方吧·中文魔方俱乐部
标题:
棋子归位问题
[打印本页]
作者:
lulijie
时间:
2011-7-9 10:46:59
标题:
棋子归位问题
n-1个棋子(标号从1至n-1),随机放在1*n的格子上(格子编号1-n),每个格子放一个棋子。
每次只能移动一个棋子到空格上,为了让棋子归位(棋子全都放在同号的格子上),
1. 应如何移动棋子才能保证移动的次数最少,请给出移动的方案。
2. 求移动次数的期望值。
作者:
pumpitup
时间:
2011-7-9 10:53:52
移动是指,拿起再放下?还是一格一格地走?如果一格一格地走的话,应该允许跳跃的吧。如果允许跳跃,那可以跃过多少棋子呢,一个还是任意?
作者:
tm__xk
时间:
2011-7-9 11:15:34
空位不是n就把对应的棋子拿过去,否则就随便那一个错的.
ms每个错误棋子一步,每个圈额外一步,是最优了吧..
(我也没看的太仔细..有不对的可能性..)
作者:
lulijie
时间:
2011-7-9 13:17:55
移动一次就是拿起一个棋子直接放在空格上,不需要一格一格移
作者:
lulijie
时间:
2011-7-9 21:04:47
3楼的方法是正确的。
至于期望值,我想用递推来做,但是却没找到可行的方法
作者:
tm__xk
时间:
2011-7-9 22:07:34
标题:
回复 5# 的帖子
到3l那里确实很显然,但是要求期望就..暂时看不出好的办法..
作者:
tm__xk
时间:
2011-7-10 00:32:50
我算出来结果是 (1/2+1/3+...+1/n)+(n-1)(n-2)/n
n=2,3,4时分别为 1/2,3/2,31/12
与人手穷举的结果相同.
所以应该错不了.
过程算短了,计算也不繁.
lz应该希望自己先算算的..所以我先不放过程..
作者:
tm__xk
时间:
2011-7-10 01:07:11
对了..我用的过程..计算不繁琐的同时..更偏向技巧性..
作者:
tm__xk
时间:
2011-7-10 02:42:06
趁现在没事干码下字吧..
下面反白给出的是我的完整过程.
以下反白内容严重剧透~~~~
不愿此时被限制思维的人请小心操控鼠标和键盘~~~~
################################
"空位不是n时就把对应的棋子拿过去,否则就随便拿一个错的"
这样的做法很容易想到,也很容易知道是最优的.(证明此处略.)
所以我们要求的就是此策略对应的步数期望.
易知,
若初始状态空位为n,则 步数 = 错误棋子个数 + 长度大于1的圈的个数 ;
若初始状态空位不为n,则 步数 = 错误棋子个数 + 长度大于1的圈的个数 - 1 .
于是,我们分别计算每项的期望.
错误棋子个数的期望:
每个棋子错误的概率为(n-1)/n,于是错误棋子个数的期望为(n-1)^2/n.
长度大于1的圈的个数(-1):
我们令每个长度为k>1的圈中的每个棋子贡献为1/k.
对于一个棋子,易知其所在圈长度为1,2,3,...,n的概率均为1/n,
故每个棋子贡献为(1/2+1/3+...+1/n)/n,
总数为贡献为1/2+1/3+...+1/n.
然而,初始空位不为n的那些状态被多算了1,因此需在期望中再减去(n-1)/n.
因此,最终答案为 (n-1)^2/n + (1/2+1/3+...+1/n) - (n-1)/n ,
即 (1/2+1/3+...+1/n)+(n-1)(n-2)/n .
################################
作者:
lulijie
时间:
2011-7-10 11:49:55
考虑了一下,有以下递推方法:设棋子归位的期望为f(n)
▲空格在n位,概率为
1/n
先将1号棋子放在n位,剩下的棋子归位需f(n-1)步,最后还要将放在n位的1号棋子归位,所以总共要
f(n-1)+2
步。
其中1号棋子本来位置正确的(概率为1/(n-1)),用此方法会多算了2步,所以要减去
2*1/(n-1)
.
▲空格不在n位,概率为
1-1/n
先将空格所在的位置对应的棋子归位,剩下的n-1个棋子归位需f(n-1)步,总共
f(n-1)+1
步。
-----------------------
所以f(n)=
1/n
*(
f(n-1)+2-2*1/(n-1)
)+
(1-1/n)
*(
f(n-1)+1
)
=f(n-1)+1+1/n-2/[n(n-1)]
所以得到递推公式
f(2)=1/2
f(n)=f(n-1)+1+1/n-2/[n(n-1)]
即 f(n)= f(n-1)+1+1/n-2(1/(n-1)-1/n) 式1
利用式1得f(n)=f(2)+n-2+(1/3+...+1/n)-2(1/2-1/n)
=(1/2+1/3+...+1/n)-3+n+2/n
=(1/2+1/3+...+1/n)+(n-1)(n-2)/n
为方便,用E(n)表示调和级数=1/1+1/2+1/3+...+1/n
------------------------------------------------
综上:f(n)=E(n)-1+(n-1)(n-2)/n
或递推公式 f(1)=0
f(n)=f(n-1)+1+(n-3)/[n(n-1)]=f(n-1)+(n^2-3)/(n^2-n)
[
本帖最后由 lulijie 于 2011-7-10 12:51 编辑
]
欢迎光临 魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)
Powered by Discuz! X2