汉诺塔 问题求解疑惑(什么鬼大哥回答的有些看不明白)

wskmf

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')

复制代码

我想问问 else中 print 为何只有一行它的工作原理

追加

1. def shuju1 (n,x,y,z):
   
2.     if n == 1:
   
3.         print (x, ' -->' ,z)
   
4.         # 这里 -->后面没有空格
   
5.     else:
   
6.         shuju1 (n-1,x,z,y)
   
7.         
   
8.         print (x, ' --> ' ,z)
   
9.         #这里 -->后面有空格
   
10.         shuju1 (n-1,y,x,z)
    
11.         
    
12. n = int (input('输入层数'))
    
13. shuju1 (n,'x','y','z')

复制代码

这是我自己又写了一段代码
得到答案 如下：
输入层数3
x  --> z
x  -->  y
z  --> y
x  -->  z
y  --> x
y  -->  z
x  --> z

他是会返回 if 下的 print 的
这是个神马意思 不是应该 n != 1 时 循环 else 下代码吗（或者循环整个def下的整个函数列表，）

什么鬼…

hanoi会一直迭代展开，最后就相当于一个只有很多print的代码，然后就输出就ok了

wskmf

什么鬼… 发表于 2017-1-7 14:54
hanoi会一直迭代展开，最后就相当于一个只有很多print的代码，然后就输出就ok了

那等于print 放在 else 的任何一行都可以是吧

wskmf

wskmf 发表于 2017-1-7 15:36
那等于print 放在 else 的任何一行都可以是吧

我在学习下迭代吧

什么鬼…

wskmf 发表于 2017-1-7 15:36
那等于print 放在 else 的任何一行都可以是吧

不是的，比如说你现在的hanoi（n，'x','y','z'）执行的时候,当n！=1时，就会执行else
然后就有
hanoi（n-1，x，z，y）
print(x, ' --> ', z)
hanoi(n-1, y, x, z)三个步骤
hanoi（n-1，x，z，y）中，当n-1
不等于1的时候就会执行
hanoi(n-2,x,y,z)
print(x, ' --> ', y)
hanoi(n-2,z,x,y)
然后这个里面再继续展开，直到n=1，代入print(x, ' --> ', z)
这个是前面的部分，
然后再执行print(x, ' --> ', z)
最后再是hanoi(n-1, y, x, z)，hanoi(n-1, y, x, z)的展开和前面
hanoi(n-1, x, z, y)的展开是一样的，最后相当于一个都是print语句所构成的程序了

jerryxjr1220

其实递归问题不用想得太复杂，尽量用抽象思维去理解。
首先，把hano(n,x,y,z)理解成当层数为n层的时候，我们要把x轴上的所有盘子借助y轴移动到z轴上。
那么具体怎么实现呢？那么就把n-1层看作一个整体，我们要做的，总共只有3步:
1.先把x轴上n-1层上的盘子借助z轴移动到y轴，这一步套用hano函数不就是hano(n-1,x,z,y)吗？
2.再把x轴上第n层的那遗留的一个盘子，直接移动到z轴上。那不就是print 'x --> z'?
3.最后把所有y轴上的n-1层的盘子(看作一个整体)借助x轴移动到z轴，就完成了。那不就是hano(n-1,y,x,z)吗？
这样整个n层的移动工作就完成了，至于n-1的工作是怎么做的，那就是递归要去完成的是，我们只要把n层要完成的步骤定义清楚就好了。
最后还有一个特例的情况，那就是n=1的情况，也是递归返回的时候。当n=1时，我们不再需要借助其他轴，直接从x轴移到z轴就好了。这样就是print 'x --> z'。
至此，所有的程序逻辑都完成了，把程序连起来即可。

jerryxjr1220

所以，如果理解了递归的程序逻辑，其实汉诺塔的程序有好多写法。
我们可以写2层一递归的写法

1. def hano(n,x,y,z):
   
2.   if n==2:
   
3.     print x,'-->',y
   
4.     print x,'-->',z
   
5.     print y,'-->',z
   
6.   else:
   
7.     hano(n-2,x,y,z)
   
8.     print x,'-->',y
   
9.     hano(n-2,z,x,y)
   
10.     print x,'-->',z
    
11.     hano(n-2,y,z,x)
    
12.     print y,'-->',z
    
13.     hano(n-2,x,y,z)
    
14. hano(4,'x','y','z')

复制代码

这里的层数必须为双数哦