汉诺比塔的递归算法

drew88

关于汉诺比塔的递归算法，else里面的注释可以懂，但是谁告诉我else里Hanoi后的x,y,z换位置是如何来的  ，求大神赐教。
def hanoi(n,x,y,z):
    if n == 1:
        print(x,'→',z)
    else:
        hanoi(n-1,x,z,y)#将前n-1个盘子从x移动到y上
        print(x,'→',z)  #将最低下的盘子移动到z上
        hanoi(n-1,y,z,x)#将n-1盘子从y移到z上
n = int(input('shuru'))
hanoi(n,'X','Y','Z')

海月清辉

我也很想知道    （n,x,y,z）  这几个参数的意义何在？   
hanoi(n-1,x,z,y)#将前n-1个盘子从x移动到y上
        print(x,'→',z)  #将最低下的盘子移动到z上
        hanoi(n-1,y,z,x)#将n-1盘子从y移到z上
这个函数又是怎么执行操作的？  看来其就是参数换了一个位置

v.ki

学习递归最重要的就是放弃，对没错放弃跟踪每一步，只要考虑终止条件和目标
用递归而不用迭代目的就是自己想得少都交给计算机，比如
当n=2时，首先要将n-1 盘子从x移动到y，但是终止条件打印的是从x到z，所以else里第一行
的实参就要改变，将y放在外层函数z 的位置，x不动，也可以理解为将外层函数的z 赋值成y，这样if 里打印出来的就是从x到y
因为这里是n-1 个盘子所以要用递归一直放，而else里第二行只是移动一个盘子所以打印出来就行
我说明白了吗

叶寒潭

最后一步的调用写错了。不是“hanoi(n-1,y,z,x)#将n-1盘子从y移到z上”，应该是 hanoi(n-1,y,x,z)  #将n-1盘子从y移到z上。hanoi(n,x,y,z)表示要将n个棋子从x移动到z，y作为辅助杆，首先要将x杆上的第n个棋子上面的n-1个棋子移动到y杆才行，z杆作为辅助杆，所以有了hanoi(n-1,x,z,y),将n-1个从x移动到y，怎么实现的先不说，假定完成了，然后x杆上还有第n个，其余的都在y杆上，然后将x上的移到z即可，也就有了print(x,'→',z)。剩下的就剩y杆上的n-1个棋子了，然后再将这n-1个棋子从y杆移动到z杆，x杆作为辅助杆，即hanoi(n-1,y,x,z) 。再深入的就是递归调用了，你肯定明白，就不多说了

沉默的人e

看清参数，以下代码为伪代码
hanoi(准备移动片片的个数,准备移动的片片所在的柱子标号,中介柱子的标号,移动目的地的柱子的标号)
这几个参数位置你怎么倒蹬都行，但是要记住每个参数所代表的含义。
你要知道哪怕是形参是（n,a,b,c）
进去之后是（n,b,a,c）
这些位置上参数的含义不会随着参数的变化而变化。
也就是说(n,b,a,c)中，b的含义指的是上面的a的含义，a的含义指的是上面的b的含义。
归根结底，你要把形参和实参弄明白。

18463102026

不知道你还记得高中数学的数列里面有一个递推公式，
Sn+1 = Sn +n
s1=1
    如果我们知道这个数列的第一项和相邻两项之间的关系，那我们就可以知道整个的数列；
这个就是编程语言里面的递归。
当我们能够把一个对象描述为他的递推关系的时候你就可以写出来对应的递归函数啦

autist

就是一开始是   X,Y,Z
打印   X->Z
然后第二次  X,Z,Y                #就是这个的  X   对应上面那次的 X，Z  带入上次的 Y ，Y 对应上次的 Z
这里就会打印    X ->Y           #这次Y是 替代了上次的 Z
然后Y ,Z ,X                           #Y占 X 的位置，Z  占  Y,   X 占  Z
就会打印  Y  - > X

TJBEST

我给大家写一个我自己完成的，没有跟着小甲鱼做，我写了注释大家看看，我觉得我的思路很简单

1. print("------汉诺塔-------")
   
2. def Han(number,name1,name2,name3):
   
3.     '''number 表示碟盘个数 1表示最小的盘子 依次是2，3，4，5....
   
4.     name1是最开始盘子所在的位置，name2是最终盘子所在的位置，name3是备用盘'''
   
5.     if number == 1:
   
6.         print("1:" + name1 + "->" + name2)
   
7.     else:
   
8.         Han(number-1,name1,name3,name2)#先将除了最后1个的所有移动到备用盘
   
9.         print(str(number) + ":" + name1 + "->" + name2)#将最后1个放到最终位置
   
10.         Han(number-1,name3,name2,name1)#再把剩下的盘移动到最终盘
    
11. print('Han(5,"A","B","C")')   
    
12. Han(5,"A","B","C")
    

复制代码

我考虑是假设A B C共三个地方，然后假设N个盘子已经找到从A到B的移动方法，那么此时也就知道了N个盘子从A移动到C的方法（因为轮换对称）。然后若考虑N+1个盘子，那就相当于先把上面N个从A移动到C，再把第N+1(最大的盘子)移动B，然后把前N个盘子从C移动到B。这样就完成了。 然后一个盘子时明显很简单，大于1个时便可迭代了。