[已解决]大佬们是怎么理解汉诺塔递归的?

Cool_Breeze

#include <stdio.h>
int s=0;
int sum(int);
int main(void)
{
        int a;
        printf("Pls number:");
        scanf("%d",&a);
        printf("sum = %d\n",sum(a));
        return 0;
}
int sum(int a)
{
        s+=a;
        a-=1;
        if (a==0) return s;
        sum(a);
}

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-14 12:10:45

先写一个空函数

int func(int n) {
        //...
        return 0;  //必须有return，否则无法通过编译
}

代码有n个圆盘时，需要操作的步骤。然后我们一步一步向其中添加代码：

首先，有1个圆盘时，很明显只需要1步，所以有：

int func(int n) {
        if (n == 1) {
                return 1;
        }
        else {
                //...
        }
        return 0;
}

其次，圆盘数目大于1时，首先需要将上面的n-1个圆盘移动到第三根柱子，然后将底部圆盘移动到目标柱子，最后将那n-1个圆盘移动回来：
那么另一部分的代码就可以写成

int func(int n) {
        if (n == 1) {
                return 1;
        }
        else {
                int step_count = 0;//记录步数
                step_count += func(a - 1);  //移动上面的n-1个圆盘
                step_count += 1;            //移动最下面的圆盘
                step_count += func(a - 1);  //移动最上面的n-1个圆盘
                return step_count；
                //...
        }
        return 0;
}

最后，考虑程序的完整性，在输入不合法(小于1）时，返回一个代表错误的值，一般是-1，然后把程序化简，可以得到

int func(int n) {
        if (n < 1) {
                return -1;    //考虑输入不合法的情况，返回-1代表错误
        }
        else if (n == 1) {
                return 1;
        }
        return 2 * func(n - 1) + 1;
}

这就是汉诺塔需要的递归代码了

跳转到最佳答案楼层

Cool_Breeze

搞不懂啊！（头都大了）！！太难了！

zltzlt

这根本不是汉诺塔递归啊。。

Cool_Breeze

zltzlt 发表于 2020-1-14 11:34
这根本不是汉诺塔递归啊。。

这是我写的递归（我想因该是）！但是汉诺塔那个我理解不了！

Croper

先写一个空函数

int func(int n) {
        //...
        return 0;  //必须有return，否则无法通过编译
}

代码有n个圆盘时，需要操作的步骤。然后我们一步一步向其中添加代码：

首先，有1个圆盘时，很明显只需要1步，所以有：

int func(int n) {
        if (n == 1) {
                return 1;
        }
        else {
                //...
        }
        return 0;
}

其次，圆盘数目大于1时，首先需要将上面的n-1个圆盘移动到第三根柱子，然后将底部圆盘移动到目标柱子，最后将那n-1个圆盘移动回来：
那么另一部分的代码就可以写成

int func(int n) {
        if (n == 1) {
                return 1;
        }
        else {
                int step_count = 0;//记录步数
                step_count += func(a - 1);  //移动上面的n-1个圆盘
                step_count += 1;            //移动最下面的圆盘
                step_count += func(a - 1);  //移动最上面的n-1个圆盘
                return step_count；
                //...
        }
        return 0;
}

最后，考虑程序的完整性，在输入不合法(小于1）时，返回一个代表错误的值，一般是-1，然后把程序化简，可以得到

int func(int n) {
        if (n < 1) {
                return -1;    //考虑输入不合法的情况，返回-1代表错误
        }
        else if (n == 1) {
                return 1;
        }
        return 2 * func(n - 1) + 1;
}

这就是汉诺塔需要的递归代码了

沉默的人e

把形参的本质搞明白,你就明白汉诺塔了
楼主写的求和工具是递归
写成f(x)的形式就是这样：(认为x是整数)：
当x等于一时 f(x) = 1
当x大于一时 f(x) = f(x - 1)

沉默的人e

你要搞清楚哪个是起始，哪个是中介，哪个是目标
至于过程，就是冰箱开开，大象塞进去，冰箱关上的步骤。

岁岁周周

你可以看看数据结构C语言第五版上面的过程很清楚，圆盘从大到小编码1~n,有A,B,C三个棍子，当只有一个圆盘的时候把A上的直接移动到C上，否则将n-1个圆盘按A~C~B移动，再将第n个圆盘移到C，再将n-1个圆盘又B~A~C移动就好了

sunrise085

汉诺塔递归，其实有很多人都没有完全明白。我了说一下自己的理解，看看能否帮得上你。

递归第一层：任务是把A上的n层通过B搬运到C上去，把上边的n-1层看成一坨，分三步：第一步，把一坨搬到B上；第二步，把最底层(第n层)搬到C上；第三步，把一坨搬到C上。
现在的问题：如何把n-1层的一坨搬过去？还搬了两次，第一步中一次，第三步中一次。这就进入第二层递归
递归第二层：任务是把A上的n-1层通过C搬运到B上去，把上边的n-2层看成一坨，分三步：第一步，把一坨搬到C上；第二步，把最底层(第n-1层)搬到B上；第三步，把一坨搬到B上。
现在的问题：如何把n-2层的一坨搬过去？……
当深入下去，只剩下一层的时候，就可以直接搬了。

所谓递归，就是一层一层的进去，到了最底层的时候得到结果，然后再一层一层的返回来，得到最后需要的结果

Cool_Breeze

我想先放下这个？看完后再回头继续！谢谢大家！！！