大佬们是怎么理解汉诺塔递归的?
本帖最后由 Cool_Breeze 于 2020-1-14 14:54 编辑{:5_105:} #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);
} 搞不懂啊！（头都大了）！！太难了！ 这根本不是汉诺塔递归啊。。 zltzlt 发表于 2020-1-14 11:34
这根本不是汉诺塔递归啊。。
这是我写的递归（我想因该是）！但是汉诺塔那个我理解不了！ 先写一个空函数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;
}
这就是汉诺塔需要的递归代码了
把形参的本质搞明白,你就明白汉诺塔了
楼主写的求和工具是递归
写成f(x)的形式就是这样：(认为x是整数)：
当x等于一时 f(x) = 1
当x大于一时 f(x) = f(x - 1)
你要搞清楚哪个是起始，哪个是中介，哪个是目标
至于过程，就是冰箱开开，大象塞进去，冰箱关上的步骤。
你可以看看数据结构C语言第五版上面的过程很清楚，圆盘从大到小编码1~n,有A,B,C三个棍子，当只有一个圆盘的时候把A上的直接移动到C上，否则将n-1个圆盘按A~C~B移动，再将第n个圆盘移到C，再将n-1个圆盘又B~A~C移动就好了 汉诺塔递归，其实有很多人都没有完全明白。我了说一下自己的理解，看看能否帮得上你。
递归第一层：任务是把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层的一坨搬过去？……
当深入下去，只剩下一层的时候，就可以直接搬了。
所谓递归，就是一层一层的进去，到了最底层的时候得到结果，然后再一层一层的返回来，得到最后需要的结果 我想先放下这个？看完后再回头继续！谢谢大家！！！
页:
[1]