[已解决]关于python第24课递归汉诺塔

李胖虎

问题二（“”将Y上的63个盘子借助X移动到Z上“”）拆解为：
①将前62个盘子从Y移动到X上。
②将最底下的第63个盘子移动到Z上。
③将X上的62个盘子移动到Y上。

想问下为什么第三部不是 移动到Z上，而是移动到Y上

最佳答案

月排行榜 / 总排行榜

heidern0612

2018-12-24 18:09:41

李胖虎 发表于 2018-12-24 15:19
假设现在我们要移动一个4层的汉诺塔，从A--->C：(move4层  a--->b--->c)

那么我们必须先将上面3个盘子移 ...

移动到A是起点，你不移动到A，上面三层能直接移动到C上？

三层在A，最后一层在C。

然后再开始下一次循环，下一次循环的结果是二层在A，二层在C。

其实就是最大的一层移动到C的话，就不用管它了，就当它消失了。

你要做的就是把圆盘恢复成初始的默认状态。

跳转到最佳答案楼层

猪儿2018

应该的作者写错PPT了，我理解是移动到Y上。

heidern0612

作者没写错，是你理解错了。

移动到Y上，正好下次循环开始：

①、将前61个盘子从Y移动到X上；

②、将最底下的第62个盘子移动到Z上；

③、将X上的61个盘子移动到Y上。

你没看出来吗？ 第③步之后的第①步就是你最终的移动到Z上的过程。

也就是顺序其实是①--②--③（盘子减1）--①--②--③（盘子减1）--①--②--③……的过程。

期间不同的其实只是中转柱和终点柱的不同。 戳我前进懒人式理解汉诺塔

如果像你那么说的话，直接一下就把所有的盘子移到终点，完成最终步骤了，还怎么递归了？

李胖虎

heidern0612 发表于 2018-12-21 08:05
作者没写错，是你理解错了。

移动到Y上，正好下次循环开始：

也就是说y已经不是原来的y了，z也不是原来的z了对嘛？

heidern0612

李胖虎 发表于 2018-12-21 09:43
也就是说y已经不是原来的y了，z也不是原来的z了对嘛？

我简单给你挪一下你就明白了，假如五层的汉诺塔：

X、Y、Z三根柱子。



第五层移动（Z中转柱，Y终点柱）：

①，我需要把上面四层借助Z中转柱移动到Y终点柱上；

②、把第五层从X上直接移动到Z上。


第四层移动（Z中转柱，X终点柱）：

①、我需要把上三层借助Z中转柱移动到X终点柱上；

②、把第四层从Y移动到Z上。


第三层移动（Z中转，Y终点柱）

①、我需要把最上面二层借助Z中转柱移动到Y上；

②、把第三层移动到Z上。

……

以上，你可以看出来移动的时候，中转柱和终点柱都是不断变化的，但是有规律。

都是隔一层变化一次。所以其实最终移动的步数也等于2N-1次。（一层的时候直接移动）。



其实我上面那个引用的帖子里面都有写，你可以仔细看看。

李胖虎

heidern0612 发表于 2018-12-21 10:02
我简单给你挪一下你就明白了，假如五层的汉诺塔：

X、Y、Z三根柱子。

除了最后一步z永远不会是终点柱？

heidern0612

李胖虎 发表于 2018-12-24 14:41
除了最后一步z永远不会是终点柱？

从X借助Y移动到Z的时候，Z就是终点柱呗

李胖虎

heidern0612 发表于 2018-12-21 08:05
作者没写错，是你理解错了。

移动到Y上，正好下次循环开始：

还是无法理解，照你这样说那么x,y始终是目标柱子，只是在x，y之间变换而已，而z只有当最底下那个抽出来时候才是目标柱子。

heidern0612

李胖虎 发表于 2018-12-24 15:07
还是无法理解，照你这样说那么x,y始终是目标柱子，只是在x，y之间变换而已，而z只有当最底下那个抽出来时 ...

不一定就叫开始柱，中转柱，终点柱。

你可以起个简单的叫法，比如起点柱、中转柱、结束数之类的。

不要考虑单个步骤怎么走。


递归的步骤都是重复的，你能把重复的条件写出来，再弄个结束条件，递归就有了，越考虑越乱。

你还是看看我上面链接的那个帖子吧。

李胖虎

假设现在我们要移动一个4层的汉诺塔，从A--->C：(move4层  a--->b--->c)

那么我们必须先将上面3个盘子移动到B，然后再将最大的盘子从A移动到C，接着将在B上的三个盘子从B移动到A才能达到目的。这个过程的关键在于第一步，怎么把上面的3个盘子从A移动到B？
到底为什么要移回去A呢我是怎么想也想不通

heidern0612

李胖虎 发表于 2018-12-24 15:19
假设现在我们要移动一个4层的汉诺塔，从A--->C：(move4层  a--->b--->c)

那么我们必须先将上面3个盘子移 ...

移动到A是起点，你不移动到A，上面三层能直接移动到C上？

三层在A，最后一层在C。

然后再开始下一次循环，下一次循环的结果是二层在A，二层在C。

其实就是最大的一层移动到C的话，就不用管它了，就当它消失了。

你要做的就是把圆盘恢复成初始的默认状态。

李胖虎

heidern0612 发表于 2018-12-24 18:09
移动到A是起点，你不移动到A，上面三层能直接移动到C上？

三层在A，最后一层在C。

原来移回A的作用是还原，等于操作了以后就变成了一个和原来一样只是少了一个盘子的汉诺塔，那么这样应该就不是最优化的步骤了，只是保证可以解出来对嘛

heidern0612

李胖虎 发表于 2018-12-24 18:32
原来移回A的作用是还原，等于操作了以后就变成了一个和原来一样只是少了一个盘子的汉诺塔，那么这样应该 ...

重复的步骤是一样的，这不就是递归么？

递归重复的步骤不就一样么？不同的只是层数不同。

李胖虎

heidern0612 发表于 2018-12-24 18:42
重复的步骤是一样的，这不就是递归么？

递归重复的步骤不就一样么？不同的只是层数不同。

为什么 问题一（将x上的63个盘子借助z移动到y上） 第三步是直接z上的62个移动到y了，为什么问题一可以直接移动到y，而不是像问题二的方式一样先还原到x上。

heidern0612

李胖虎 发表于 2018-12-24 21:42
为什么 问题一（将x上的63个盘子借助z移动到y上） 第三步是直接z上的62个移动到y了，为什么问题一可以直 ...

你要是实在不理解，就先放着吧。

我一开始也不理解，后面学多前面就融会贯通了，没必要钻牛角尖。