张甲49站长

2017-11-05 11:51电脑端

查看作者

自然语言、图形、代码三种形式，彻底搞懂汉诺塔问题

一. 前言

汉诺塔问题从我们初学C语言的时候，就已经接触到

但是大多数人基本上只是以背代码的方式了结了这个问题，并没有彻底的搞懂，我便是其中一个

最近学数据结构的时候又遇到了这个问题，便想着顺水推舟，解决这个问题

在网上查阅了各种资料，大多数都讲的含糊不清，干脆自己写一份

下面我们通过自然语言、图形、代码三种形式，彻底搞懂汉诺塔问题

因为所有文字均为手打，又整理的比较仓促

难免出现错别字或者思路错误的地方。

欢迎各路大神指点批评

如果一遍看不懂没有关系，一个步骤一个步骤的多看几遍就可以了（要有耐心ヾ(ﾟ∀ﾟゞ)）

为了表示方便，我们用以下方式代表相应的自然语言：

箭头 —>表示移动的意思，且一次只移动一个。

比如A —> C代表将A柱当前最上面的1个盘子移动到C

A（n）代表A柱中当前有n个盘子

二. 汉诺塔问题简介

假设有三根标号为A,B,C的柱子，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子移动到柱子C上，并且每次只能移动一个，移动过程中不能把大盘子放在比自己小的盘子上面，请问至少需要多少次移动多少次才能完成？

三. 文字解答

其实无论n等于几，我们都可以将n分为两种情况：

第一种：n = 1 的时候，只有一个盘子，直接移动就可以

第二种：n > 1 的时候，因为一次只能移动一个盘子，所以我们需要借助其他柱子来移动

这里我们可以看出本题符合递归的条件了，第一种情况自然很容易实现

难就难在第二种情况，如何将第二种情况实现呢？

其实当n > 1 的时候，无论n等于几，也无论一共移动了多少次，汉诺塔一定会出现三种状态：

状态一：将n – 1 个圆盘从开始柱，移动到中转柱，此时A（1），B（n – 1），C（0）

状态二：将开始柱中剩余的那一个最大圆盘，移动到目标柱，此时A（0），B（n – 1），C（1）

状态三：将中转柱中n – 1个圆盘移动到目标柱，移动完成，，此时A（0），B（0），C（n）

（ps. 也就是说这是三个大的步骤，每个步骤再细分成小的操作才完成。状态二自然好说，只有一个盘子，直接移动就可以了，但是状态一和状态三，是如何将n – 1 个盘子全部移动到其他柱子上的呢？先不要着急，这里我们先不用管是如何实现的，只需要了解到这样的一个解题思路，具体的实现我们在本文的第六节中我们会详细的解答）

我们可以看出，第一部分的操作和第三部分的操作是类似的，都是将n – 1个盘子，移动到其他柱子上面

所以第一部分和第三部分的移动次数是相同的

我们假设总移动次数为Hn

则将n-1个盘子从A移动到B所需次数为H（n – 1)

那么Hn = H（n- 1) + H（n- 1) + 1

= 2^n – 1

也就是状态一的移动次数+是状态二的移动次数+状态三的移动次数 = 总移动次数

可能上面的文字可能难以理解，下面我们用图片的形式来表达

四. 图形解答

这里我们以n = 4 为例，n > 1，符合第二种情况，则进入三个状态：

状态一：将n – 1 个圆盘从开始柱，移动到中转柱

也就是将A中 n – 1 个盘子全部移动B，此时 A（1） B（4 – 1）C（0）。如下图：

状态二：将开始柱中剩余的那一个最大的圆盘，移动到目标柱

也就是将A中剩下的最大的那个盘子，移动到C ，此时A（0） B（4 – 1）C（1）。如下图：

状态三：将中转柱中n – 1个圆盘移动到目标柱，移动完成

将B中n – 1 所有盘子全部移动到C，此时A（0） B（0）C（4），移动完成，如下图：

我们可以发现，无论n 等于多少，总是会在某一步中出现上面的三个状态

具体的每一步的实现步骤请看动图：

五. 代码实现

这里我们设计一个move(int n, char A, char B, char C)方法

其中n = 第n个圆盘，A = 开始柱，B = 中转柱，C = 目标柱

我们先从n = 1 看起，n = 1 ，符合第三节中我们提到的第一种情况，则直接将从A —> C 即可

void move(int n,char A, char B, char C) 
{

	if(n == 1)
	{
	    printf("%c -> %c %d \n",A,C,n);
	}
		
}

接下来，我们从n = 2 看起，n = 2 > 1，符合第二种情况，我们便采用第二种情况的三个状态来解决

状态一：将n – 1 个圆盘从开始柱，移动到中转柱

也就是以C为中转站，将A中 n – 1 = 1个盘子全部移动B。此时 A（1） B（1）C（0）

move(n-1,A,C,B);

状态二：将开始柱中剩余的那一个最大的圆盘，移动到目标柱

也就是将A中剩下的最大的那个盘子，移动到C （由于是直接移动，则省略方法，直接输出），此时 A（0） B（1）C（1）

printf("%c -> %c %d \n",A,C,n)

状态三：将中转柱中n – 1个圆盘移动到目标柱，移动完成

也就是以A为中转站，将B中n – 1 所有盘子全部移动到C，完成，此时 A（0） B（0）C（2）

move(n-1,B,A,C);

则总的实现代码为：

#include<stdio.h>

void move(int n,char A, char B, char C)
{

    if(n == 1)
    {
        printf("%c -> %c %d \n",A,C,n);
    }
    else
    {
        move(n-1,A,C,B);
        printf("%c -> %c %d \n",A,C,n);
        move(n-1,B,A,C);
    }


}

void main()
{
    move(1,'A','B','C');
}