谈如何简单懒汉式理解汉诺塔

heidern0612

以下部分文字和图片摘自网络，仅供个人理解参考。

注：如果以下整段整段文字让你看的头晕，那就从中找段自己能看懂的开始看起，等看懂了后再从头看。

汉诺塔递归是像我这样小白新手理解的一大难点，拆穿了讲，其实就是把大象塞进冰箱的步骤，打开冰箱门---把大象塞进去----关上冰箱门。

所以，汉诺塔永远只有三步：(理解何为起点柱---中转柱----终点柱，并且这个中转柱在过程中并不是固定的。)

1、把（n-1）个圆盘从A柱借助C柱移动到B柱；(为什么要借助C柱移动到B柱，你玩一下就明白了，假定有四个盘子，前三个盘子你能不借助C柱直接移到B柱上？)

2、把大盘子移动从A柱移动到C柱；

3、把（n-1）个圆盘从B柱借助A柱移动到C柱。


思路就是要把(n-1)思考成一个整体，分析完(n-1)后，分析(n-2)层，一层层剥下去。

非要拆开了去想怎么样一步步实现，那是自讨苦吃。拆开了想是计算机干的事，不是我们人脑干的事。

举例来说，如果要把一个N层汉诺塔从A搬到C，那么：如果前N-1层可以找别人搞定，咱只管搬第N层，会不会变得非常容易？

你看，这一下就简单了：这时当它只有两层就好了，先把前N-1层看作一个整体，把它搬到B；

然后把最下面的第N层搬到C；然后再把前N-1层从B搬到C。



类似的，假如接到“搬前N-1层”这个任务的是我们，怎么搬呢？

简单，像前东家一样，把前N-2层外包出去，我们只搬第N-1层——其实和前面讨论过的“外包N-1层，只搬第N层”完全一样嘛。

依此类推，一层层“外包”下去——我不管你们有多伤脑筋，反正只要你们把我外包给你的活干了，我就能干了我的活！

注意，这里千万别管“接到外包工作的家伙有多伤脑筋”——丢给他就让他头疼去，我们就别再捡回来痛苦自己了。



这一步就是“递推”。注意这里的搬法：搬第N层，就需要把前N-1层搬两次，另外再把第N层搬一次；搬第N-1层，又需要把前N-2层搬两次，然后再把N-1层搬一次，依此类推。

很容易知道，一共需要搬2*N-1次。


一步步递推下去，终究会有个“包工头”，接到“搬第一层”的任务。

第一层怎么搬？太简单了，让搬哪搬哪。换句话说，到此，“递推”就到了极限，简单粗暴直接做就可以了。


既然第一层搬了，那么第二层当然就可以搬了；第二层搬了，第三层又可以搬了……依次类推，直到第N层。


于是问题搞定。这一步就是“回归”。如上三步加起来，就是“递归”。


推而广之，任何问题，不管规模为N时有多复杂，只要把N-1那块“外包”给别人做之后，我们在这个基础上可以轻易完成N，那么它很可能就适合用“递归”解决。

那么，怎么最终确定它能不能用“递归”做呢？看当N取1或2之类最简情况时，问题是否可以解决——然后写程序解决它。



换句话说，只要我们：

1、写程序告诉电脑“如何分解一个问题”；

2、写程序告诉电脑“当该问题分解到最简时如何处理”；

那么，“具体如何递推、如何回归”这个简单问题就不要再操心了，电脑自己能搞定。



写出问题分解方法、写出分解到最简后如何解决，这是我们的任务；把问题搞定，是电脑的任务。这就是递归的魅力。

正是由于这种“我提供思路你搞定细节”的特点，“一切皆递归”的函数系语言才被称为“声明式编程”（而不是必须一步一步指导电脑如何做的“命令式编程”）。



或许有一部分人知道这个函数如何编写，也似懂非懂的了解这个函数注释的意义。

但是可能会纠结为什么函数写成这样子就能详细地列出具体的移动步骤

（我就是这部分人啊，研究这个问题没少钻牛角尖），

下面就跟大家分享下我的另外一个见解。




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

那么我们必须先将上面3个盘子移动到B，然后再将最大的盘子从A移动到C，接着将在B上的三个盘子从B移动到A才能达到目的。这个过程的关键在于第一步，怎么把上面的3个盘子从A移动到B？（move3层  a--->c--->b）

前面说要移动4个就必须先移动上面3个，所以这里我们要移动3个就必须移动上面2个，但是并不是移动到B哦。

因为B已经被我们预定好了要用于存放前面移动的3个盘子，如果是将上面2个盘子移动到B，那根据游戏规则第三个盘子就没办法放进去B了，这样子就没办法完成B存放3个盘子的预定目标，所以要移动的上面两个是计划放在C上。

那问题接着就到了该怎么移动上面2个盘子，这时你可能会想要先移走最上面的盘子（这时候要移到B，因为C被我们预定了要存放2个盘子，且B这时候是没有盘子的），没错，那最上面的盘子怎么移？

直接移呗怎么移，最上面的盘子都没限制的。所以要移动1个盘子的时候，直接移动：  A--->B，注意，这个步骤中A为起点柱，B为终点柱。


这时你已经移开最上面的盘子了，就可以把第二盘子移走了，A--->C，然后把最小的盘子放到第二个盘子上，B--->C，这样就完成了移动2个盘子的任务了。


总结下移动两个盘子的步骤：

A--->B

A--->C

B--->C

这三个步骤就是move（2，A，B，C）所做的事情，是可以详细列出每步移动的动作的。

既然最上面的2个盘子都调用move（2，A，B，C）移开了，那么第3个盘子自然也可以从A--->B了，之后再把放在C上面的2个盘子从C移动到B上就完成了移动上面3个盘子的任务了。

前面的move（2，A，B，C）函数既然可以将2个盘子从A借助B移动到C并列出详细的移动动作，那么move（2，C，A，B）也就能将放在C上的2个盘子从C借助A移动到B并列出详细的移动动作。


如此说来，移动3个盘子的步骤就可以总结如下了：

move（2，A，B，C）

A--->B

move（2，C，A，B）

这三个步骤就是move（3，A，C，B）所做的事情。

因为我们已经证明move（2，A，B，C）和move（2，C，A，B）是可以详细列出移动2个盘子时每步移动的动作的，而中间的A--->B是一步显而易见的移动动作，所以可以确定move（3，A，C，B）是能列出每步的移动动作的。

然后根据同样的分析，最上面的3个盘子都移开了，接着只要将第4个盘子从A--->C，然后将放在B上的3个盘子移动到C上就完成全部任务了。

前面我们已经证明move（3，A，C，B）能将3个盘子从A借助C移动到B并且列出详细的移动动作，那么move（3，B，A，C）也能将3个盘子从B借助A移动到C并列出每步的移动动作。



这样，移动4个盘子的步骤就出来了：

move（3，A，C，B）

A--->C

move（3，B，A，C）

这三个步骤就是最开始move（4，A，B，C）函数所做的事情。

因为我们已经证明move（3，A，C，B）和move（3，B，A，C）是可以详细列出移动3个盘子时每步移动的动作的，而中间的A--->C是一步显而易见的移动动作，所以可以确定move（4，A，B，C）是能列出每步的移动动作的。

需要说明的是，从xx借助xx移动到xx这样的说法在上面出现了很多次，“从”后面代表的就是起点柱，“借助”后面代表的是中转柱，“移动到”后面代表的是终点柱。你也能注意到到起点柱，中转柱，终点柱在不同层级下是不一样的。


附图理解小甲鱼老师的算法流程

13572044595

虽然看不懂，但是感觉你用心了~

heidern0612

13572044595 发表于 2018-11-24 20:11
虽然看不懂，但是感觉你用心了~

你慢点看，理解了再看下一段。应该都能理解，不理解就多看几遍

魔神游者

哇，厉害了，看那个图就懂了

胖豆lucky

明白了！终于明白了！！谢谢楼楼！！！

unitaology

感谢楼主！

‘算法流程图’ 太棒了！ 借助它，终于看懂了 ‘递归函数’ 的调用流程。

之前，找了不少其它帖子，能搞懂搬运步骤。但一直不明白这个函数工作过程。

看了楼主提供的算法流程图，才明白问题出在了，函数调用流程没全明白，还有形参和实参转换上没有做记录。

楼主的图，既有流程，又有形实参转换标注。这个应该是必须每一步动手做记录的。

这个问题真是烧脑， 再次感谢 heidern0612

四点好

记号一下，明天再看

mhb789456

为什么第一个n=2时，执行else语句时，变成了move(1,'A','B','C')

wyft5t5

实际工作当中，有用到汉诺塔相关的知识点吗？？

lanmon丶

终于看懂了

沉默的人e

现在是认为a是起始,b是中介,c是结尾

如果认为形参a是中介,形参b是结尾,形参c是起始应该怎么写?

一路狂奔2020

从xx借助xx移动到xx这样的说法在上面出现了很多次，“从”后面代表的就是起点柱，“借助”后面代表的是中转柱，“移动到”后面代表的是终点柱。你也能注意到到起点柱，中转柱，终点柱在不同层级下是不一样的。

这句话突然就解开了我的困惑
感谢！！！！！！！！！！

永远的渣滓

看的懂，用不来

风铃-

写的很好，我大概知道怎么去用，但是怎么实现的我还是看不太懂T T好难……

想摸妹妹大腚

牛鼻啊能加你个微信QQ吗？交个朋友

yuanying05322

第一次来这里，好激动啊

daoxu-ac

反反复复看了好几遍一点点清楚

海月清辉

我原以为楼主只负责搞笑的，而且是专业的那种的

guozhenyu411

先马克一下

yrhhh

楼主 另外一个见解 的第二行是不是写错了 第一个句号前面应该是从B移动到C吧