递归求解汉诺塔问题解析 -- 抽象思维

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

至此，所有的程序逻辑都完成了，把程序连起来即可。

1. def hano(n,x,y,z):
   
2.         if n>1:
   
3.                 hano(n-1,x,z,y)
   
4.                 print (x,'-->',z)
   
5.                 hano(n-1,y,x,z)
   
6.         else:
   
7.                 print (x,'-->',z)
   
8. hano(4,'x','y','z')

复制代码

输出：
x --> y
x --> z
y --> z
x --> y
z --> x
z --> y
x --> y
x --> z
y --> z
y --> x
z --> x
y --> z
x --> y
x --> z
y --> z

汉诺塔问题拓展：

如果你理解了前面那段程序的逻辑，那么同样的，我们可以改写汉诺塔程序，用两层一递归的写法。（注意：这样写，层数必须是双数）

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

让我想到，以前有道脑筋急转弯的题目：问把大象塞进冰箱有几个步骤？
解答：3个，1.开冰箱门 2.塞大象 3.关冰箱门
至于怎么塞的，这可以看做一个整体，单独处理。
递归解题也是一样，把步骤划分清就可以了

maikeweisi

看看 从来寄没看懂过

qaz123765

看看

tang888

赞

tjugcglcl

学习一下

你长得真好看

谢谢

神马烂昵称

sddd

背课汗木

看看

宫爆鸡丁丁

这个递归确实太抽象了。。。。

宫爆鸡丁丁

这个程序建议把变量x，y，z和参数x，y，z区分开来看，程序写成这样对新手来说误导性太大了。

dundao999

看看

小生℡

茅塞顿开