汉诺塔问题

——及其递归与循环解决方法

Category: Math

原创: 欢迎各种形式的搬运，但请务必注明本文出处

不然我顺着网线摸过去干你，打到你🐎都不认识

汉诺塔很多人都玩er过，这个游戏需要些技巧，但也不能说是一个非常益智的游戏，中等益智吧。对于没有玩er过这个的读者，或者玩er过但不知道这个游戏名字的读者，您可是有福了，您不仅能从这篇文章中全面了解到汉诺塔及其玩er法，还能全面感受到我对您的全面的嘲讽🤭

为了迅速填补部分读者在汉诺塔游戏领域的知识空白，我决定贴图来感性描述一下这个游戏👇

看到上面这俩，有的读者可能回忆起了童年时某个下午的愉快时光，有的读者可能已经有些眼花了。其实把两个动图分开，都不至于眼花的，但是放在一起就不太友好了，特别是对眼睛不太好的朋友，所以我说左边的动图被裁窄了基本不会影响读者体验🐶

汉诺塔作为一种玩具，要吸引小孩儿，造型也是多样的。有下面这样的，标标准准，ABC三柱分立。

@阿里巴巴某网店

也有的带一点艺术感，追求造型匀称，花里胡哨的，容易让人迷惑，不朴实。

另一个造型的汉诺塔，骚是骚的，图是糊的

汉诺塔问题定义：

• 起始状态：
  1. 三根高度相同的柱子，一些大小不同的圆盘；
  2. 三根柱子分别为起始柱(A)、辅助柱(B)及目标柱(C)；
  3. 在起始柱上，圆盘以从大到小的顺序叠放成金字塔形。
• 目标：
  • 玩家应尽可能快且以最少步数将这些圆盘从起始柱(A)移动到目标柱(C)上。
• 移动过程中必须遵循的规则：
  1. 一次只能移动一个圆盘；
  2. 任何非当前移动的圆盘必须放置于柱子上；
  3. 较大的圆盘不能放在较小的圆盘上。

汉诺塔本是一个游戏，怎么个玩er法才是汉诺塔问题。网上关于汉诺塔问题解法的介绍一搜就是一大片，大部分还附带C/C++代码，有些还写得特别好，不比我写的差。

    那么，为什么我还要再写一篇呢？来凑数吗？

这个问题其实与各位看官无关，对于这种“雨女无瓜”的问题，我向来是点到即止，勾起各位的好奇心即可；这种不厚道的做法主要有两点原因：一是不要在这种比较水的地方浪费大家的时间，二是我懒得写。

上面一段权当是玩笑话，我还是集中精力讨论这个游戏怎么玩er吧。各位看官也莫生气，您继续往下读，都是干货——我们是受过专业训练的，不会随便讲一堆废话来水字数，嗯，除非忍不住😂

先欣赏下别人的代码

public static void moveDish(int level, char from,char inter, char to) {
    if (level == 1) {
        System.out.println("从 "+from+" 移动盘子 1 号到 "+to);
    } else {
        moveDish(level - 1,from,to,inter);
        System.out.println("从 "+from+" 移动盘子 "+level+" 号到 "+to);
        moveDish(level - 1,inter,from,to);
    }
}

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 0)
        return;
    hannoi (n - 1, from, to, buffer);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hannoi (n - 1, buffer, from, to);
}

所以，大家都是两次递归调用，两次调用间输出了一下 （第一段代码调两次 moveDish，第二段调两次 hannoi）

为啥这么写是对的？到这里还不能直接给大家这个问题的答案。要分析这个问题，我们就要用玩游戏的态度：如果你是个孩子，拿到这个游戏，你会怎么玩？

这里要温馨提醒各位家长一句：在给您的宝宝玩这个游戏前，请准确评估您的宝宝的智力水平和搞破坏的能力，不要一上来就给 TA 玩 7,8 层的；如果是我，我就先从两层的开始，’cause I wanna be basic.

如果有看官要杠：“博主你为啥不讨论1，就从2开始了呢？1不是比2更简单吗？”
emmm… 我得感谢有人这么杠，虽然这位杠精对汉诺塔理解比较浅，但是这确实是个很好的问题！一层塔看似只需要移动一步，但是这一步却是最难解释的一步，实话和大家说，我对一层塔的解决并不是很完美，所以先搁置一下。

好的，我们刚刚说到要讨论两层汉诺塔的玩法，下面我就向大家演示一下两层的汉诺塔怎么移动。

上面的那些过程都不重要！开头和结果才是重要的。我们只需要知道，把一根柱上的头两层移动到另一柱上，对我们来说是很轻松的；而且！步骤最少的移动方式只有唯一的一种！而且！而且！我们知道这种移动方式具体包括4个状态、3个步骤！

⇩ 3步 ⇩

@bugdealer
Ⅰ类操作就是把一根柱上的头两层移动到另一根柱上

我把这种操作称为Ⅰ类操作。🔗

有Ⅰ类操作，当然就有Ⅱ类操作，但是不会再有Ⅲ类操作了，哈哈。

Ⅰ类操作又分为两种——操作0和操作1。如何区分这两种操作？其实这与Ⅱ类操作有关，所以需要先解释什么是Ⅱ类操作。

经过一波Ⅰ类操作，我们解决了两层塔的问题，但是无法解决三层塔。
下面就来看看三层塔是怎么玩的↓

@bugdealer

上图中，A柱上的头两层经过操作0移动到了B柱，原本A柱上的最下层变成了第一层，然后经过一个Ⅱ类操作，A柱上的第一层被移到C柱，最后操作1把B柱上的头两层移动到C柱。

那么就不难理解了：Ⅱ类操作就是把一根柱上的第一层移动到另一柱上，而操作0就是Ⅱ类操作之前的Ⅰ类操作，操作1就是Ⅱ类操作之后的Ⅰ类操作。大家可能发现我并没有在定义Ⅰ类操作和Ⅱ类操作时用“起始柱”和“目标柱”的说法，这只是为了避免歧义——“起始柱”和“目标柱”在整个游戏中始终是A柱和C柱，而Ⅰ类操作和Ⅱ类操作的起点和终点并不总是A柱和C柱。

写到这里，我突然发现自己犯了一个严重的错误：Ⅰ类操作不就是连续三次Ⅱ类操作吗？在这个游戏中什么操作不是Ⅱ类操作呢？不好意思了各位，恕我能力不足，这波装逼失败。。。

哈哈，俗话说 “知错能改，善莫大焉。” 我来明确给Ⅱ类操作界定下范围。Ⅱ类操作也分为两类：操作2和操作3，而且只包括这两种操作。操作2所移动的圆盘在是经过Ⅰ类操作才成为第一层的，也就是说这个圆盘之前还没有被暴露出来，必须经过一波Ⅰ类操作才将其暴露出来；而操作3就是：

@bugdealer
操作3就是一层塔的移动

现在稍微总结一下上面的模式，我们就得到了：

Ⅰ类操作 → Ⅱ类操作 → Ⅰ类操作

别人代码里写的是

递归 → 输出 → 递归

对比之下，好像懂了什么。。。

    此中有真意，但我不想辩

接下来，我就要触及这个问题的核心了：只靠这两类操作就够了吗？🔗

这样足够了！Here’s Why:

• 如果有 N 层塔，那么就先把上面 N-1 层从A移到B，再把第 N 层从A移到C，最后把B上的 N-1 层移到C；
• 要把 N-1 层从A移到B，那么就先把上面 N-2 层从A移到C，再把第 N-1 层从A移到B，最后把C上的 N-2 层移到B；
• 要把 N-1 层从B移到C，那么就先把上面 N-2 层从B移到A，再把第 N-1 层从B移到C，最后把A上的 N-2 层移到C；
• … （以下省略的步骤可以写到世界末日）

总之，任你层数再多，我都不带怕的；所有的移动，如果还不是这两类操作之一，那么一定可以继续分解，最终都归结为这两类操作。所以，这两类操作是真正的原子操作

进一步地，我们可以发现，在这种操作的分解中，一个对 N 层塔的操作总是可以被分为三个操作，即

移动 N-1 层塔 → 对原本的第 N 层做Ⅱ类操作 → 移动 N-1 层塔

科代表这时要打断我了：“不断地一分为三，这不就是三叉树结构嘛！” 🔗

这位科代表，请你坐下 ！

                                                               博主如是说到

当然我不能说用三叉树表示就不对，这样表示是很容易理解的，我一开始也是打算用三叉树；但是仔细看一下上面的分解，中间的一步已经是原子操作了，不用继续分解，真正需要分解的是第一步和第三步，所以用三叉树的话中间的子节点都是一种虚的操作，直到叶节点才是实的操作，如果写在程序里就是一种空间的浪费。中间的子节点对理解是有帮助的，提出使用三叉树的人对这个问题的理解是没有问题的，但是此人在编程方面修为不高。

只有心里有B树，才能找到最优的数据结构！🔗

B树可能会缺席，但从不会迟到。那么我们真的能用B树表达整个操作吗？

废话不说，以图为证！

@bugdealer
三层塔的解法

三层塔还是很容易的，我想各位都能看懂吧：先来个操作0，再接个操作2，最后是操作1，和之前讨论的是一样的。我们加点难度，看看四层塔的B树解法。

@bugdealer
四层塔的解法

哈哈，有点没看懂？那么我们从根节点开始梳理一下：根节点是对最大的圆盘（也就是初始状态时的第四层）施加操作2，把它移到C柱上；根节点的左子树就是在移动最大的圆盘前，要把其它三个圆盘移动到B柱上，所以和三层塔的解法长得一样的；根节点的右子树是把B柱上的三个圆盘进一步移动到C柱上，所以也和三层塔的解法长得一样 。

上面两个例子表明，在汉诺塔问题中使用B树，没有任何一个节点的操作是虚的，都是实打实的原子操作，而且要从建立的B树中得到整个解法，只需要对B树进行中序遍历，还有，当塔大于2层时，我之前提出的“Ⅰ类操作和Ⅱ类操作交替出现”的规律是普适的。

写到此，我们就要进一步深入，揭开Ⅰ类操作和Ⅱ类操作的本质特点了。🔗

• Ⅰ类操作永远处在B树的叶节点位置——只不过有时也恰好处在根节点位置；
• Ⅱ类操作永远处在B树的根节点和中间子节点位置——只不过有时也恰好处在叶节点位置。
• 而操作0、操作1 也和二叉树常用的二进制分支编码 0,1 相对应。

妙啊。

如果还觉得不够妙，那接下来我对Ⅰ类操作的扩展，一定会精妙到让您合不拢腿☻。🔗

Ⅰ类操作移动的是最上面两层，沿着这个思路，扩展的Ⅰ类操作即从起点移动好几层（至少两层）到终点；鉴于这个操作的全称有点长，所以下文都用它的简称：扩Ⅰ。

现在我们还不知道每一个原子操作的具体的起点和终点，定义这个扩Ⅰ，就是要把虚操作暂时请回来，从一个我们好理解的角度推断每个原子操作的起点和终点。

一旦有了这个扩展，那自然就有了扩展的操作0和扩展的操作1（简称扩0和扩1）。我们再回过头看B树的时候，突然就发现所有二叉分支，往左边走的就是扩0，往右边走的就是扩1，如果依此来给B树各连接边赋值，那么就得到了：

@bugdealer
四层塔扩Ⅰ 边权

可见，扩Ⅰ以边权重的形式存在，其实就是之前提到的虚操作，并不是原子操作，但是我这么做并不是想回到三叉树的“虚操作”方向上，而是为了明确每一个原子操作的起点和终点。而且大可不必有所担心，现在采用B树结构，这就保证了无论怎样是回不到“虚操作”的方向去的，您只管接着看，只有看到如何算出原子操作的起点和终点才能感受到这个扩展妙在何处。

读到此大家也应该看出了虚操作的缺陷，那就是定义不是很明确：由于不限制移动的圆盘层数为2，扩展的Ⅰ类操作可以存在于B树的不同层次，然而这些不同层的操作其实是有明显的、完全不相容的差异的，按道理本不应归为一类 。这种操作是嵌套着定义的，最好还是不要用，我是能力有限，只能通过这个方式讲给大家。

之前已经找到的一些规律到这一步就可以派上用场了。我们已经知道，叶子节点上都是Ⅰ类操作，根节点和中间节点上都是Ⅱ类操作，那么现在对于节点的编码其实是画蛇添足了——我不需要在图上标出0，1，2也能推断出一个节点所对应的是什么操作；单纯以操作类型编码节点在理论上也不可能区分出不同起点和终点的操作，既然如此，要进一步对节点编码就不能只是用操作类型了，要提供更多的信息，区分每一个节点，才可能把每个节点自己的起点终点推算出来。

于是我就像下面这样进行重编码，相当于给每个节点一个id：

@bugdealer
四层塔按边权重编码

不难看懂哈。

根节点是A到C的Ⅱ类操作（别和我说这里不懂），往下一层是编码0和1的Ⅱ类操作，最后一层的叶节点是编码为00，01，10，11的Ⅰ类操作。

懂行的朋友就知道了，这没什么新奇的，就是线性二叉树，只不过把根以下每层都给写出来了。

虽然写到这儿挺激动的，但是我还没有得到每个节点的起点终点，我们想要每个节点都和根节点一样，只有两个字母，一个起点，一个终点，就OK，所以革命尚未成功，兄dei干了这杯再上路。

不是说靠这种编码做不了，也行啊 ，为啥行呢？您看B树的单独一层，从左至右就是二进制从0开始加1再加1，用数组就可以存储，每层一个数组就行，但是还是比较浪费空间：一是就算这么储存了还是需要进一步算出起点和终点，不够直接；二是第二层其实只需要两个bit就行，但是没有这样的数据类型（这个其实是小问题，我有点鸡蛋里挑骨头）。

递归解法详述。🔗

讲了这么多，那么怎么算每个节点的终点和起点呢？很显然是要从根节点开始、自顶向下地算。那如果我搞一个数组，从头开始顺着来存，第一个位置放AC、第二个位置放0节点的起终点、第三个位置放1节点的起终点、第四个位置放00节点的起终点……这样能方便我们自顶向下地寻找和定位节点吗？对于计算机来说难算的也是不难的，也许这样还会快些，但是我没有尝试这样存，因为不直观。（之后我发现还有个更重要的原因，但是那属于意外收获了）

既然已经讲到内存了，那递归派和循环派就要分道扬镳了，我就先讨论递归吧。之前已经得出了中序遍历就能输出正确结果的结论，然而这是在树已经建好、每个节点的起终点已经算好的前提下的，那么我们是否可以将两个工作合并呢？我们是否能写一个递归就既完成节点计算、又完成计算结果输出呢？中序遍历的代码相信大家都很熟了，结构上是递归-输出-递归，真正的特点是递归之后输出——即使进入了输出后的那个递归也是重新回到递归之后输出的模式。结合树的结构，在中序遍历时，输出前的递归都是在不断“向下”、向根节点前进，下到底了才输出，也就是说，“输出”这项工作是在向上返回时才做的，那么我们当然就可以先利用输出前的递归来完成自顶向下的节点起终点计算。

那么为什么具体写出来是文章开头“别人的代码”那种样子呢？我就简单解释吧，每个操作2，只要它有子树，一定是左子树扩0、右子树扩1，那么多扩0都是扩0，那么多扩1都是扩1，就是因为从操作2变换到扩0有一定的规律，从操作2变换到扩1也有一定规律；再说直白点：如果你知道一个操作2的起终点，那么它的扩0子树起点就是它的起点，扩0子树的终点就是它的辅助柱，扩1子树的起点就是它的辅助柱，扩1子树的终点就算它的终点。这些也很容易想通，当然，不排除有些人脑子会卡在什么地方，所以我后面还会详细解释一番的！

不管怎样，现在我们再看“别人的代码”就明白多了：总体上就是中序遍历的代码结构，在输出前的遍历是扩0，所以起点参数还是起始柱，终点变成辅助柱，输出之后的遍历是扩1，所以起点参数变成辅助柱，终点还是目标柱。

关于递归解法，还剩最后一个问题：这中序遍历是整挺好，但是没见它之前构建树结构啊，内存里没有树，遍历又是怎么做的呢？介个嘛，我们这个问题中树的结构是满二叉树，树的结构是很明确的，理论上不需要把树的整个结构都用指针标出来，实际上递归的深度也很容易控制，能保证输出正确，再加上递归本来就“堆上自带存储功能”，所以才能做到这样的；嗯，人贵有自知之明，这是专业动作，没有金刚钻请不要自以为是瞎jb乱写。大家一定要记住，递归可能是你一时的情人，但是循环才是一个程序员一辈子的朋友。

循环解法详述。🔗

如果我们将这棵树直接“压扁”，就会发现根节点应该是在正中间，第二层两个节点分别在根节点两侧，隔着一定距离，第三层的节点又在第二层节点两侧，也隔着一定距离……

@bugdealer
数组结构

由于扩0和扩1是为其上一级的扩Ⅰ服务的，其上一级的扩Ⅰ和它们的父节点(操作2)具有相同的起点和终点，所以如果我们要把一个扩Ⅰ拆分成三步——扩0、操作2、扩1，那么就只能先把盘子移到辅助柱上，才能暴露出要进行操作2的盘子，再把辅助柱上的移到目标柱上，也就是说，如果一个扩Ⅰ的起始柱、辅助柱、目标柱分别为XYZ，则将其拆分得到的扩0的三柱就是XZY，操作2的三柱还是XYZ，扩1的三柱是YXZ。

将三柱的位置按上面的顺序分别称为0位、1位、2位，就可以把上面所述的规律总结为一个3×3的矩阵，它反映了三柱地位的交换规律，所以我把它取名为三柱易位阵👇。

@bugdealer
三柱易位阵

这个矩阵就值得好好说道说道了。这矩阵看起来挺抽象，它其实是这么用的：比如输入的扩Ⅰ操作是XYZ，在一个三元数组里面，宁想得到下一层的扩0，怎么个易位法儿？那宁就查这个矩阵，查扩0所对应的第二行，第二行第一个对应0位，是0，OK，就把原来扩Ⅰ的0位搬到一个新数组的0位，第二行1位是2，就把原来的2位搬到新数组的1位，第二行2位是1，就把原来的1位搬到新数组的2位，于是得到扩0的三柱顺序是XZY。这个易位阵还有另一种写法，为了不搅乱各位的思路，这里就不谈了。

有同学可能看出来我这个阵其实只需要用到后两行——毕竟操作2的三柱顺序还是0 1 2，顺其自然的，不需要再查个表，所以可以将三柱易位阵简化为下面这个形式：

@bugdealer
简化版三柱易位阵

有了这个，我心里就有哈数了，那就让我来展示一下真正的实力吧！

⇩

⇩

写到这，坑也差不多填完了，回去休息一阵！祝大家工作轻松薪资高！