• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

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

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

      一.  前言

      汉诺塔问题从我们初学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
    • 3.3k
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: