简化汉诺塔

这段代码是将无论多么复杂的汉诺塔都简化为三步吗？但现实中的汉诺塔是要(2**n-1)步是不是可以这样理解这段代码并不能完全打印出全部步骤只是三步而已大神在上

胡说鱼

2017-07-28

源自：初识Python 7-5

关注问题我要回答

491

操作

收起

1 回答

折翼舞_0 回答被采纳 +2 积分
2017-07-28

对，无论多复杂都是三步，不过，这三步是从宏观上来看的，你看第一步，就是一个自调用（自调用里面还有自调用，也就是递归），第三步又是一个自调用，只有n==1成立时，才停止递归。

1 回复有任何疑惑可以回复我~

收起回答

折翼舞_0

从这里无穷的自调用就能看出并不是只要三步就能移动完

2017-07-28 回复有任何疑惑可以回复我~

折翼舞_0

实际上，真正在移动的就是第二步，第一和三其实还是交给了递归处理，也就是说，每次执行一次自调用，就是移动一次（第二步），每次自调用里面又执行了二次自调用，我们把这个递归函数的深度看作n（如果学过数据结构可以看做深度为n的树），在深度为1时，移动了一次（第二步），同时产生两个分支（一和三步），形成两个节点，处于深度为2的空间，然后每个分支会再移动一次（第二步），并产生2个分支，形成两个节点，处于下一个深度的空间，一直到递归结束，

2017-07-28 回复有任何疑惑可以回复我~

折翼舞_0

可见每个节点就相当于移动一次，深度为n的空间存在2^(n-1)（2的n-1次方）个节点，全部节点数（即总移动次数）也就是 2^0 + 2^1 + …… + 2^(n-1) ,即 2^n - 1。 (次数没有错误，可以打印全部结果)至于为什么2^0 + 2^1 + …… + 2^(n-1) = 2^n - 1。。。。可以逆推，1 就是 2^0, 1+ 2^0 = 2^1 , 2^1 + 2^1 =2^2…………你试着自己加加看，1+2^0 + 2^1 + …… + 2^(n-1) 就是 2^n。

2017-07-28 回复有任何疑惑可以回复我~

查看1条回复

0/150

提交

取消

初识Python

参与学习 758623 人
解答问题 8667 个

学python入门视频教程，让你快速入门并能编写简单的Python程序

进入课程

简化汉诺塔

我要回答关注问题

热搜

最近搜索清空

简化汉诺塔

1 回答

简化汉诺塔