算法与数据结构之递归算法

1.递归算法的核心思想：

将问题转化为同类问题的子问题进行求解。

2.递归算法的应用：

• 汉诺塔

3.问题分析：

1.汉诺塔问题：

描述：64个盘子从a移到c，要求一次只能移动一个盘子，并且小盘子在上，大盘子在下。

编写功能函数：

void hanoi(int n,char a,char b,char c)

• 含义：
  n：盘子数量。
  a,b,c:三个轴。

• 思路：

  n=1时，只需要将盘子从a移动到C即可。记作：a->c。

  n>1时，进行如下思考：

技巧：

我们知道装大象的步骤如下：

1.打开冰箱

2.装大象

3.关冰箱门

观察如下图：

接下来，我们将要打开冰箱

我们发现当n=2时，汉诺塔游戏可以抽象成一个装大象的过程，过程及其简单易懂。

事实上，无论n为多少，我们都可以吧汉诺塔抽象成两个来看，也就是将两个看成一个整体！

而那两个模块（冰箱）我们又可以把它看成一次大象装冰箱的过程，也就是说3个盘子模块会实现2次装大象的过程。

随着盘子数量越来越多，装大象的过程越来越多，我们可以利用函数调用自身函数达到重复循环装的作用，当然你也可以选择for循环，我们这里讨论递归思想。

语句等价翻译

hanoi(n-1,a,c,b);//该语句代表打开冰箱！  
a->c;//该语句代表装大象！  
hanoi(n-1,b,a,c);//该语句代表关冰箱门！

具体分析：

hanoi(n-1,a,c,b):表示将冰箱从a这个地方绕过c轴到达b轴这个地方。其中n-1代表冰箱！

a->c：表示将a轴上的最后一个模块盘子（最大的，最底部的大象）直接送到c轴上去！

hanoi(n-1,b,a,c):表示将b轴上的的冰箱绕过a关到c轴上！

以上分析表示了装大象的过程，也是汉诺塔游戏的过程。

4.hanoi函数的具体实现：

void hanoi(int n, char a,char b,char c)//定义hanoi函数
{
    if(n==1)
    printf("%c->%c",a,c);//如果只有一个盘子，也就是说只有大象没有冰箱门的时候，直接把大象装进冰箱里
    else
    {
        hanoi(n-1,a,c,b);//打开冰箱
        printf("%c->%c",a,c);//装大象
        hanoi(n-1,b,a,c);//关冰箱门
    }
}

5.主函数的实现：

#include<stdio.h>
int main()
{
    int n;
    printf("请输入盘子个数：\n）；
    scanf("%d",&n);
    hanoi(n,a,b,c);//调用函数
    return 0;
}

6.代码实现：