棋子归位问题

lulijie

n-1个棋子（标号从1至n-1），随机放在1*n的格子上（格子编号1-n），每个格子放一个棋子。
每次只能移动一个棋子到空格上，为了让棋子归位（棋子全都放在同号的格子上），
1. 应如何移动棋子才能保证移动的次数最少，请给出移动的方案。
2. 求移动次数的期望值。

lulijie

移动一次就是拿起一个棋子直接放在空格上，不需要一格一格移

lulijie

3楼的方法是正确的。
至于期望值，我想用递推来做，但是却没找到可行的方法

lulijie

考虑了一下，有以下递推方法：设棋子归位的期望为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 编辑 ]