- 最后登录
- 2013-11-11
- 在线时间
- 873 小时
- 阅读权限
- 40
- 注册时间
- 2008-9-15
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
|
考虑了一下,有以下递推方法:设棋子归位的期望为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 编辑 ] |
|