● hanoi --nju - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: Program
标  题: hanoi  --nju
发信站: 荔园晨风BBS站 (Sun May 11 11:30:57 2003), 转信

Hanoi塔问题移动次数的递推公式：
令h(n)表示n个圆盘所需要的转移次数，根据递归的算法，先把前面的n-1格盘子转移到
B上＃ 后把第n个盘子转移到C上，最后再一次将B上的n-1个盘子转移到C上，
于是有：
  h(n)=2h(n-1)+1,
  h(1)=1,                    (1)
下面利用母函数来解上面的递归式：
设母函数
  H(x)=h(1)x+h(2)x^2+...+h(n)x^n+...,   (2)
将H(x)和-2xH(x)相加得到：
(1-2x)H(x) = h(1)x+[h(2)-2h(1)]x^2+[h(3)-2h(2)]x^3+...
根据递归式(1)可以得到h(2)-2h(1) = 1, h(3)-2h(2)=1,...
于是：
(1-2x)H(x) = x+x^2+x^3+...=x/(1-x)
整理得到：
H(x)= x/[(1-x)(1-2x)]   (3)
我们可以将H(x)化为：
H(x) = 1/(1-2x) - 1/(1-x)
     = (1+2x+(2x)^2+(2x)^3+...) - (1+x+x^2+...)
     = ∑(2^k-1)x^k,  k=1,2,...∞                    (4)
比较(2)(4)得到：
h(k) = 2^k-1
也就是说，对于n个盘子，必须移动2^n-1次才可以。
这里我能做到的也只是利用递推的公式求出移动次数，至于移动的具体步骤，我还没有
仔细
，或许也可以递推的?出来。

--
※ 修改:·huhaiming 於 May 11 11:35:10 修改本文·[FROM: 192.168.0.200]
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店