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

c/c++

浏览数:159

2019-3-29

AD:资源代下载服务

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.代码实现: