棋子归位问题

tm__xk

空位不是n就把对应的棋子拿过去,否则就随便那一个错的.
ms每个错误棋子一步,每个圈额外一步,是最优了吧..
(我也没看的太仔细..有不对的可能性..)

tm__xk

到3l那里确实很显然,但是要求期望就..暂时看不出好的办法..

tm__xk

我算出来结果是    (1/2+1/3+...+1/n)+(n-1)(n-2)/n

n=2,3,4时分别为 1/2,3/2,31/12
与人手穷举的结果相同.
所以应该错不了.

过程算短了,计算也不繁.
lz应该希望自己先算算的..所以我先不放过程..

tm__xk

对了..我用的过程..计算不繁琐的同时..更偏向技巧性..

tm__xk

趁现在没事干码下字吧..
下面反白给出的是我的完整过程.

以下反白内容严重剧透~~~~
不愿此时被限制思维的人请小心操控鼠标和键盘~~~~

################################
"空位不是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 .
################################