024递归：汉诺塔

人若有情死得早

1.汉诺塔的由来：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
2.汉诺塔游戏的规则与编程剖析
假设汉诺塔有x，y，z三根柱子，已知柱子x上有n个盘子，盘子大小各不相同呈金字塔状放置；要求将n个盘子从柱子x上移到柱子z上，条件是每次只能移到一个盘子，而且必须永远是大盘子在下小盘子在上的移到状态。
将n个盘子从柱子x移到柱子z上，无法直接实现该过程，需借助柱子y；
①首先，将柱子x上的n-1个盘子移动到柱子y上；
②然后，将柱子x上最后一个盘子移动到柱子z上；
③最后，将柱子y上的n-1个盘子移动到柱子z上。
3.用递归方法编写汉诺塔游戏程序

1. def hanoi(n, x, y, z):
   
2.     if n == 1:
   
3.         print(x, ' --> ', z)
   
4.     else:
   
5.         hanoi(n-1, x, z, y) #将前n-1个盘子从x移动到y上
   
6.         print(x, ' --> ', z ) #将最底下的最后一个盘子从x移动到z上
   
7.         hanoi(n-1, y, x, z) #将y上的n-1个盘子移动到z上
   
8. 
   
9. n = int(input('请输入汉诺塔的层数:'))
   
10. hanoi(n, 'x', 'y', 'z')

复制代码

小甲鱼

支持一个！