数据结构考研分类复习真题 第三章 答案[7]

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

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

=（Hn+）+

= Hn++

=（Hn+）++

= Hn+++

·

·

·

= k Hnk+k +k +…+ +

=n H+n+n+…++

因为H=所以原式Hn=n+n+…++=n

故总盘数为n的Hanoi塔的移动次数是n

运行结果为 （注运行结果是每行一个数为节省篇幅放到一行）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []