• 中文
    • English
  • 注册
  • 查看作者
  • 自然语言、图形、代码三种形式,彻底搞懂汉诺塔问题

    一.  前言

    汉诺塔问题从我们初学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');
    }

    六.  详解

    看到这里似乎已经没有什么问题。但是n = 2的时候,我们每次都是只移动一个盘子,就完成了这三个状态

    如果n = 3,状态一我们就需要将2个盘子移到B,如果n =4,状态一我们就需要用将3个盘子移动到B

    如果有n个盘子,状态一我们就需要将n – 1 个盘子移动到B

    那么有多个盘子的时候,我们如何才能完成状态一和状态三呢?

    其实很简单:我们只需要将n 看成n – 1就可以了

    这里我们以n = 3 为例,进行讲解

    (这里我们不再使用A — > B 这种写法,而是带入具体的圆盘代号,比如1 —> B)

    n = 3 时,A为开始柱,B为中转站,C为目标柱

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

    首先进入n = 3的状态一:将n – 1 个圆盘从开始柱移动到中转柱,对应代码:

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

    此时,我们可以暂时忽略掉3这个圆盘,也就是将n看成n – 1,则n = 2 。

    这个问题便已经成了将A中的1和2这两个盘子都移动到B的问题。如下图:

    (灰色数字代表我们还未移动但是准备移动完成的效果,绿色数字代表我们暂时将这个圆盘忽略)

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

    我们进入n = 2 的状态一:将n – 1 个圆盘从开始柱,移动到中转注意,此时n = 3 的状态一还未结束

    也就是此时A成了开始柱,B成了目标柱,C成了中转柱

    则将 1 —> C

    n = 2 的状态一完成

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

    进入n = 2 状态二: 开始柱中剩余的那一个最大的圆盘,移动到目标柱

    则将2 —> B

    n = 2 的状态二完成

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

    进入n = 2 状态三:将中转柱中n – 1个圆盘移动到目标柱

    也就是将C中 n – 1 = 1个盘子移动到B:

    n = 2 的状态三完成

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

    则此时n = 2 全部移动完成

    同时,n = 3 的状态一才刚刚完成

    我们回到n = 3,再开始进入n = 3的状态二:开始柱中剩余的那一个最大的圆盘,移动到目标柱。,对应代码:

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

    则将3 —> C

    n = 3的状态二完成

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

    进入n = 3 的状态三:将中转柱中n – 1个圆盘移动到目标柱,对应代码:

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

    则此时我们再次将3忽略

    也就是再次将n 看成n – 1 ,则此时n = 2,则此时B成了开始柱,C成了目标柱,A成了中转柱,

    也就是将B中的1和2这两个圆盘移动到C即可

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

    我们再一次进入n = 2 时的状态一:将n – 1 个圆盘从开始柱,移动到中转柱

    我们将1 —> A

    n = 2 的状态一完成

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

    进入n = 2 的状态二:开始柱中剩余的那一个最大的圆盘,移动到目标柱

    则将2 —> C

    n = 2的状态二完成

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

    进入n = 2 的状态三:将中转柱中n – 1个圆盘移动到目标柱

    则将1 —> C

    n = 2 的状态三完成

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

    此时n = 3 的状态三才刚刚完成,整个移动也完成了

    七.  n = 3总结

    1.  首先看n,若n = 1 ,则直接移动

    2.  若n > 1,则进入三个状态:

               2.1  进入n 的第一个状态

               2.2  将n 看成n – 1,然后进入n – 1 的第一个状态

               2.3  n – 1 完成第三个状态后,进入n 的第二个状态

               2.4  n完成第二个状态后,进入n的第三个状态

               2.5  将n 看成n – 1,然后进入n – 1 的第一个状态

               2.6  n – 1 完成第三个状态后,n的第三个状态也完成

    n 等于其他数字的时候,都按照这个规律来就可以了

     

  • 0
  • 0
  • 0
  • 4.3k
  • 请登录之后再进行评论

    登录

    赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    单栏布局 侧栏位置: