当前位置：网站首页>用函数递归的方法解决汉诺塔问题

用函数递归的方法解决汉诺塔问题

2022-08-02 16:52:00 【51CTO】

函数递归算法的运用有一个经典例题，那就是汉诺塔问题，接下来就让我们一起来看看如何用函数递归来解决汉诺塔问题叭！

汉诺塔问题的起源：

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。

汉诺塔游戏规则：

简单来说，就是把a柱上的n个圆盘，通过b柱作为辅助全部搬运到c柱上去。在搬运的过程中一次只能搬运一个圆盘，而且大圆盘不能放到小圆盘上面。

用函数递归的方法解决汉诺塔问题_递归函数

什么是递归？

要用递归的方法解决这个问题，我们首先要知道何为递归。
递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。
当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。
所以递归要有两个要素，结束条件与递推关系。

问题分析：

我们很容易知道：
当n=1时，我们直接将盘子从a柱移到c柱便解决了问题。
当n=2时，我们可以先把a柱上的第一个盘子移动到b柱（a柱最上面的盘子编号为1，向下依次递增），然后将a柱上的第二个盘子移动到c柱，再将b柱上的盘子移动到c柱即可。
但是当n的值为3及以上时问题便变得麻烦起来了。那么我们能否将后面复杂的问题化简为前面简单的两种情况呢？
答案是肯定的，这也是函数递归的目的：将复杂的问题简单化。

代码实现：

我们只需将盘子个数为n的分为两类解决即可：

当n=1时，将盘子从a->c即可。

当n>1时，将a柱上的n-1个盘子移动到b柱上，再将a柱上剩下的一个（也就是第n个）移动到c柱上，然后将b柱上的n-1个移动到，c柱上即可。（记住我们这里是将n-1个盘子看为一个整体）

用函数递归的方法解决汉诺塔问题_算法_02

       
       #define
       
       #include<stdio.h>
       
       int 
       
       count 
       
       = 
       
       0;
       
       void 
       
       move(
       
       int 
       
       n, 
       
       char 
       
       a, 
       
       char 
       
       b, 
       
       char 
       
       c)
       
{
       
       if (
       
       n 
       
       == 
       
       1)
       
       printf(
       
       "第%d次:%c->%c\n", 
       
       ++
       
       count, 
       
       a, 
       
       c);
       
       else
       
  {
       
       move(
       
       n 
       
       - 
       
       1, 
       
       a, 
       
       c, 
       
       b);
       
       printf(
       
       "第%d次:%c->%c\n", 
       
       ++
       
       count, 
       
       a, 
       
       c);
       
       move(
       
       n 
       
       - 
       
       1, 
       
       b, 
       
       a, 
       
       c);
       
  }
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n 
       
       = 
       
       0;
       
       scanf(
       
       "%d", 
       
       &
       
       n);
       
       move(
       
       n, 
       
       'a', 
       
       'b', 
       
       'c');
       
       printf(
       
       "共移动了%d次\n", 
       
       count);
       
       return 
       
       0;
       
}
       
       //汉诺塔问题
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.