[C语言】初学者思考-函数递归之汉诺塔

[C语言】初学者思考-函数递归之汉诺塔

函数递归指函数内部对自己的调用，用来将复杂的问题转化为许多简单重复的小问题。

函数递归必须满嘴的条件：

        函数递归必须存在限制条件，用来终止函数递归。

        每次递归对函数的调用都必须接近这个限制条件。

函数递归的实际应用

汉诺塔是指利用A,B,C三根柱子将A柱上的圆盘通过B柱转移到C柱上，其中转移过程中小圆盘必须在大圆盘之上。

汉诺塔问题分为两种可能性

当层数n=1时，

        直接将A柱的圆盘转移到C柱上。

当层数n>1时

        可以使用函数递归完成求解，递归部分分为三个环节。

        ①将A柱除了最大盘以外的圆盘利用C柱转移到B柱上

         ②将A柱最大圆盘直接转移到C柱上，此时最大盘转移到C柱上，剩下的圆盘可以看做n-1层新的汉诺塔

        ③将n-1层的汉诺塔按照以上逻辑最终转移到C柱上

c语言代码实现方式。

#include
//count用来计算转移次数
int count = 0；
//changer函数用来打印转移过程
void changer(char a, char b)
{
    printf("  %c -> %c  ", a, b);
    count++;
}
//hanoi函数的逻辑为“将a柱的圆盘通过b柱转移到c柱上”
void hanoi(int n, char a, char b, char c)
{
    if(n == 1)
    {
        changer(a, c);
    }
    else
    {
        //将a柱上最大盘以外的圆盘通过c柱转移到b柱上
        hanoi(n - 1, a, c, b)
        //将最大盘转移到c柱上
        changer(a, c)
        //将b柱上n-1个圆盘通过a柱转移到c柱上
        hanoi(n - 1, b, a, c)
    }
}
int main()
{
    int n = 0;
    printf("请输入汉诺塔层数：n");
    scanf("%d“, &n)；//输入n
    //n为汉诺塔层数，'A','B','C'字符代表三根柱子。
    hanoi(n, 'A', 'B', 'C');
    printf("总共转移次数 = %的n“, count);
    return 0;
}