[已解决]第24讲：关于汉诺塔的问题

赛大爷

def hanoi(n,x,y,z):
    if n==1:
        print(x,'-->',z)
    else:
        hanoi(n-1,x,z,y)#将前n-1个盘子移动到y上
        print(x,'-->',z)#将最后的移动到z上
        hanoi(n-1,y,x,z)#将y上的n-1个盘子移动到z上

这几段代码完全不明白啊
不知道为什么会这么写：
我打个比方
例如我输入
hanoi(3,'a','b','c')
出现以下的形式：
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
谁能解释一下函数是怎么运行的吗？
例如：
hanoi(3,'a','b','c')。
因为n<>1
所以执行
hanoi(2,'a','c','b')
因为你n<>1
所以执行
hanoi(1,'a','b','c')
n=1
所以输出a->c
后面就搞不懂了？
这个问题想了好几天了都弄不懂，谁能帮帮我啊

最佳答案

月排行榜 / 总排行榜

18813034116

2017-3-27 11:25:12

我想先说一句话，递归的好处就是能让你忽略处理问题的细节，仔细纠结它是如何处理问题的我认为没必要，只要你有解决方案，在利用递归把问题解决了就好了，以下是你想知道的代码运行过程：
hanoi(3,a,b,c)先执行hanoi(2,a,c,b),后执行print(a-->c),再执行hanoi(2,c,a,b),为了简单表示，我把它简化成：
(3,a,b,c)>(2,a,c,b)>print(a-->c)>(2,c,a,b);
其中(2,a,c,b)>(1,a,b,c)>print(a-->b)>(1,c,a,b)
其中(1,a,b,c)>print(a-->c);(1,c,a,b)>print(c-->b)
我这里就写到hanoi(2,a,c,b)

跳转到最佳答案楼层

赛大爷

在线等待，快疯掉了！

18813034116

我想先说一句话，递归的好处就是能让你忽略处理问题的细节，仔细纠结它是如何处理问题的我认为没必要，只要你有解决方案，在利用递归把问题解决了就好了，以下是你想知道的代码运行过程：
hanoi(3,a,b,c)先执行hanoi(2,a,c,b),后执行print(a-->c),再执行hanoi(2,c,a,b),为了简单表示，我把它简化成：
(3,a,b,c)>(2,a,c,b)>print(a-->c)>(2,c,a,b);
其中(2,a,c,b)>(1,a,b,c)>print(a-->b)>(1,c,a,b)
其中(1,a,b,c)>print(a-->c);(1,c,a,b)>print(c-->b)
我这里就写到hanoi(2,a,c,b)

隨鈊乄鎍慾

赛大爷 发表于 2017-3-27 09:55
在线等待，快疯掉了！

别着急！汉诺塔问题的确没明白想几天也很正常。我当初也想了几天。后来才想明白。用语言讲不太清楚，我尽量说吧怎么说呢？首先你要理解鱼哥的解题思路，其次你把把汉诺塔这个游戏玩得很666；最后跟着鱼哥的思路（就第一步和第三步很重要；第二步较简单）对应到游戏当中去，你就会慢慢的理解了。最后我提醒一下ABC三根柱子之间是在不停的转换角色如：A在第一层是起始位置但在后面的几层里面A会变成目标柱和中转柱；虽然它的名称还是没变还是A，但它的角色变了。汉诺塔的确很绕，但慢慢的你一定也能理解的。
最后总结一下：其实它们（ABC）就是在哪里实现交叉赋值而已！

ooxx7788

我个人理解递归其实就是数学归纳法。
那需要做的就是两件事：
第一，证明n0的成立，对于汉诺塔而言就是当只有1个盘子而言的时候，怎么做。
第二，假设n时候成立，证明n+1的时候也成立。对于你这个程序而言，就是第n个盘子的时候，让n-1个盘子在y上面，把n从x移到z。就成立了。
中间的具体过程不需要考虑，因为也没必要想。

赛大爷

18813034116 发表于 2017-3-27 11:25
我想先说一句话，递归的好处就是能让你忽略处理问题的细节，仔细纠结它是如何处理问题的我认为没必要，只要 ...

谢谢你啊，我明白了是怎么运行的了，我这个人就是爱纠结，其实知道没这个必要。谢谢了，以后有问题希望能够再求助你。

赛大爷

隨鈊乄鎍慾 发表于 2017-3-27 11:59
别着急！汉诺塔问题的确没明白想几天也很正常。我当初也想了几天。后来才想明白。用语言讲不太清楚，我 ...

谢谢你，明白思路了，其实就是三个参数，第一个是 要移动的，第二个是做为辅助的，第三个是目标柱子，完了给它赋值之后他就会他们就会互换角色，当递归到1的时候就全部解出来了。

赛大爷

ooxx7788 发表于 2017-3-27 12:27
我个人理解递归其实就是数学归纳法。
那需要做的就是两件事：
第一，证明n0的成立，对于汉诺塔而言就是当 ...

你这个角度有道理诶，但我有点没转过来

隨鈊乄鎍慾

赛大爷 发表于 2017-3-27 14:50
谢谢你，明白思路了，其实就是三个参数，第一个是 要移动的，第二个是做为辅助的，第三个是目标柱子，完 ...

正解....................