【经典问题】汉诺塔(递归、C语言实现)

梦里梦外; 2022-06-01 02:44 520阅读 0赞

这个月在学习Python，函数递归那一节提到了汉诺塔问题，这是一个很经典的问题，我们老师在之前也提到过这个例子，感觉蛮重要的，想记录下来。为了向经典致敬，这篇就不用Python实现了，就用C语言~

汉诺塔的来历我就不细说了，这里就自行左拥度娘右抱谷歌脑补一下。请看下面这张图，图片来自Google Images

![SouthEast][]

我们要做的就是将A中的圈圈，移动到C上，每次只能移动一个圈圈，并且要保障大圈在下，小圈在上。

这里我们很容易能够想到一个方案，就是借助剩余的那根柱子B来完成，以下的每一步都要保证大圈在小圈下面（上图有8个圈圈）：

第一步：将A中的7个圈圈移动到柱子B上

第二步：将A剩下的最后一个圈圈移动到C上

第三步：将B中的7个圈圈移动到柱子C上

接下来要简单说一下什么是分治思想，这个是递归的核心思想。分治，即分而治之，将一大问题化解成诺干个非常简单而且相同的小问题，中国古话说：“大事化小，小事化了。”将的就是这个道理。下面我们就把上面的第一步和第三步细化一下：

对于第一步：

1.1：将A中的6个圈圈移动到柱子C上

1.2：将A中剩下的最后一个圈圈移动到柱子B上

1.3：将C上的6个圈圈移动到柱子B上

对于第二步：

2.1：将B中的6个圈圈移动到柱子A上

2.2：将B中剩下的最后一个圈圈移动到柱子C上

2.3：将A上的6个圈圈移动到柱子C上

我们发现1.1、1.3、2.1、2.3又可以细化，一直细化到只有一个圈圈为止。需要注意的是，除了只有一个圈圈的移动，其他的操作都需要借助剩余的那根柱子完成。

好了，有了思路，我们就可以写代码了：

//汉诺塔问题，打印的是整个的移动过程
    #include <stdio.h>
    void hanoi(int n , char A , char B , char C)//n个圈圈在柱子A上，借助柱子B，移动到柱子C上
    {
      if(n == 1)//如果A柱子上只有一个圈圈，直接移动到C上
        printf("%c --> %c\n",A,C);
      else
      {
        hanoi(n-1,A,C,B);//将A柱子上的n-1个圈圈，借助柱子C，移动到柱子B上
        printf("%c --> %c\n",A,C);//将A柱子上的最后一个圈圈移动到柱子C上
        hanoi(n-1,B,A,C);//将B柱子上的n-1个圈圈，借助柱子A，移动到柱子C上
      }
    }
    
    int main()
    {
      hanoi(8,'A','B','C');
      return 0;
    }

运行结果如下：

A --> B
    A --> C
    B --> C
    A --> B
    C --> A
    C --> B
    A --> B
    A --> C
    B --> C
    B --> A
    C --> A
    B --> C
    A --> B
    A --> C
    B --> C
    A --> B
    C --> A
    C --> B
    A --> B
    C --> A
    B --> C
    B --> A
    C --> A
    ...后面太长了，总共大概有200+行，这里就省略了~

[SouthEast]: /images/20220601/c3982fd0181b4e51b014d86df83730c9.png