C语言递归实现汉诺塔问题

在使用递归前我们首先要知道什么是递归：

程序调用自身的编程技巧称为递归（ recursion）。

递归的作用：

递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。这里是引用

汉诺塔问题要求将a柱所有盘子从下面开始按大小顺序重新摆放在c柱上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

两个圆盘

1.绿盘移动到b
2.黄盘移动到c
3.绿盘移动到c
三个圆盘

这种情况比上面的两个圆盘就稍微复杂一些：
1.绿盘移动到c
2.黄盘移动到b
3.绿盘移动到b
4.蓝盘移动到c
5.绿盘移动到a
6.黄盘移动到c
7.绿盘移动到c

也可以把上面的绿盘和黄盘看作一个整体：
1.整体移动到b
2.蓝盘移动到c
3.整体移动到c

可以看出将上面的两个盘子看作整体后，问题便又回到了两个圆盘的移动

由此归纳出将最大圆盘（即第n个圆盘）上面的（n-1）个圆盘看作一个整体进行两个圆盘的移动；再将上面的（n-1）个圆盘上面的（n-2）个圆盘看作一个整体进行两个圆盘的移动…直到整体中只包含最小的圆盘，这个最小的圆盘只需要从a移动到c即可

下面是汉诺塔问题C语言的递归写法：

#include <stdio.h>
#include<stdlib.h>
//n个盘子 
void Hanoi(int n, char a,char b,char c); //a为起始柱，b为辅助柱，c为目标柱
void Move(int n, char a, char b); //a为起始柱，b为目标柱
int count;
int main()
{
    int n=0;
    printf("汉诺塔的层数:\n");
    scanf("%d",&n);
    Hanoi(n, 'A', 'B', 'C');
 system("pause");
    return 0;
}
void Hanoi(int n, char a, char b, char c)//a为起始柱，b为辅助柱，c为目标柱
{
    if (n == 1)
    {
        Move(n, a, c);
    }
    else
    {
        Hanoi(n - 1, a, c, b);
        Move(n, a, c);
        Hanoi(n - 1, b, a, c);
    }
}
void Move(int n, char a, char b)//a为起始柱，b为目标柱
{
    count++;
    printf("第%d次移动 Move %d: Move from %c to %c !\n",count,n,a,b);
}

C语言递归实现汉诺塔问题

相关推荐