设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y)

　　则 Hn =2Hn-1+1 //先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z

　　=2（2Hn-2+1）+1

　　=22 Hn-2+2+1

　　=22（2Hn-3+1）+2+1

　　=23 Hn-3+22+2+1

　　·

　　·

　　·

　　= 2k Hn-k+2k-1 +2k-2 +…+21 +20

　　=2n-1 H1+2n-2+2n-3+…+21+20

　　因为H1=1，所以原式Hn=2n-1+2n-2+…+21+20=2n-1

　　故总盘数为n的Hanoi塔的移动次数是2n-1。

　　3. 对下面过程写出调用P(3)的运行结果。

　　PROCEDURE p（w：integer）;

　　BEGIN

　　IF w>0 THEN

　　BEGIN

　　p(w-1);

　　writeln(w);{输出W}

　　p(w-1）

　　END；

　　END；

　　【西北大学 2001 三、7】

　　【参考答案】

　　运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。）