【数据结构与算法】递归汉诺塔

汉诺塔


汉诺塔是根据一个传说形成的数学问题(关于汉诺塔):
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
技术分享
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

递归汉诺塔


解题思路:
技术分享
可以把问题简化成2个盘子的情况,如:A上有两个盘子,B和C是空的。如果要把A的两个盘子全部移动到C,需要经过以下步骤:
1.A移动一个盘子到B
技术分享
2.A移动一个盘子到C
技术分享
3.B移动一个盘子到C
技术分享
到这里已经把所有盘子移动到C盘,其实可以把底盘上面的盘子看成一个整体,这就简化成3步了,然后使用递归重复这3个步骤就完成了所有盘子的位移。

使用递归解汉诺塔,并实时打印每一步的变化和计算步数。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。