鱼C论坛

 找回密码
 立即注册
查看: 1324|回复: 1

[已解决]C++汉诺塔问题递归算法

[复制链接]
发表于 2023-9-20 21:44:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include <stdio.h>
int t = 0;
int hanoi(int n, char A, char B, char C) {
        
        if (n == 1) {
                printf("Move sheet %d from %c to %c\n", n, A, C);
                t++;
                return(t);
        }
        else {
                t++;
                hanoi(n - 1, A, C, B);
                printf("Move sheet %d from %c to %c\n", n, A, C);
                hanoi(n - 1, B, A, C);
                return(t);
        }
}

int main() {
        int n;
        int total;
        printf("请输入盘数:");
        scanf_s("%d", &n);
        total=(hanoi(n, 'A', 'B', 'C'));
        printf("total:%d",total);
        return 0;
        //等效于2^n-1
}

我不太能理解此程序的递归过程,以及
else {
        t++;
        hanoi(n - 1, A, C, B);
        printf("Move sheet %d from %c to %c\n", n, A, C);
        hanoi(n - 1, B, A, C);
        return(t);
}
中写两边hanoi()函数的作用
麻烦大佬解答!
最佳答案
2023-9-20 21:44:53
这是一个经典的汉诺塔问题,递归算法是其最优解法之一。

首先,让我们来理解一下汉诺塔问题的规则:有三根柱子,A、B、C,初始时在A柱上有n个盘子,盘子大小不等,大的在下面,小的在上面,现在需要将所有盘子从A柱移动到C柱,移动过程中可以借助B柱,但是在移动过程中,任何时刻都不能出现一个大的盘子放在小的盘子上面的情况。

接下来,我们来看一下这段代码的递归过程:
else {
    t++;
    hanoi(n - 1, A, C, B); // 将A柱上n-1个盘子通过借助C柱移动到B柱上
    printf("Move sheet %d from %c to %c\n", n, A, C); // 将A柱上第n个盘子移动到C柱上
    hanoi(n - 1, B, A, C); // 将B柱上n-1个盘子通过借助A柱移动到C柱上
    return(t);
}

首先,当n=1时,只需要将A柱上的第一个盘子移动到C柱上即可,此时递归结束,返回t=1。

当n>1时,我们需要将A柱上的n个盘子通过借助C柱移动到C柱上。具体的做法是:

1. 将A柱上的n-1个盘子通过借助C柱移动到B柱上;
2. 将A柱上的第n个盘子移动到C柱上;
3. 将B柱上的n-1个盘子通过借助A柱移动到C柱上。

这个过程是一个递归的过程,每次递归都是将A柱上的n-1个盘子通过借助C柱移动到B柱上,然后将A柱上的第n个盘子移动到C柱上,最后将B柱上的n-1个盘子通过借助A柱移动到C柱上。

在递归过程中,t++表示移动次数加一,最后返回移动次数t。

总的移动次数为2^n-1,可以通过数学归纳法证明。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-9-20 21:44:53 | 显示全部楼层    本楼为最佳答案   
这是一个经典的汉诺塔问题,递归算法是其最优解法之一。

首先,让我们来理解一下汉诺塔问题的规则:有三根柱子,A、B、C,初始时在A柱上有n个盘子,盘子大小不等,大的在下面,小的在上面,现在需要将所有盘子从A柱移动到C柱,移动过程中可以借助B柱,但是在移动过程中,任何时刻都不能出现一个大的盘子放在小的盘子上面的情况。

接下来,我们来看一下这段代码的递归过程:
else {
    t++;
    hanoi(n - 1, A, C, B); // 将A柱上n-1个盘子通过借助C柱移动到B柱上
    printf("Move sheet %d from %c to %c\n", n, A, C); // 将A柱上第n个盘子移动到C柱上
    hanoi(n - 1, B, A, C); // 将B柱上n-1个盘子通过借助A柱移动到C柱上
    return(t);
}

首先,当n=1时,只需要将A柱上的第一个盘子移动到C柱上即可,此时递归结束,返回t=1。

当n>1时,我们需要将A柱上的n个盘子通过借助C柱移动到C柱上。具体的做法是:

1. 将A柱上的n-1个盘子通过借助C柱移动到B柱上;
2. 将A柱上的第n个盘子移动到C柱上;
3. 将B柱上的n-1个盘子通过借助A柱移动到C柱上。

这个过程是一个递归的过程,每次递归都是将A柱上的n-1个盘子通过借助C柱移动到B柱上,然后将A柱上的第n个盘子移动到C柱上,最后将B柱上的n-1个盘子通过借助A柱移动到C柱上。

在递归过程中,t++表示移动次数加一,最后返回移动次数t。

总的移动次数为2^n-1,可以通过数学归纳法证明。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 23:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表