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

Cool_Breeze

1. #include <stdio.h>
   
2. int s=0;
   
3. int sum(int);
   
4. int main(void)
   
5. {
   
6.         int a;
   
7.         printf("Pls number:");
   
8.         scanf("%d",&a);
   
9.         printf("sum = %d\n",sum(a));
   
10.         return 0;
    
11. }
    
12. int sum(int a)
    
13. {
    
14.         s+=a;
    
15.         a-=1;
    
16.         if (a==0) return s;
    
17.         sum(a);
    
18. }

复制代码

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-14 12:10:45

先写一个空函数

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

复制代码

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

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

1. int func(int n) {
   
2.         if (n == 1) {
   
3.                 return 1;
   
4.         }
   
5.         else {
   
6.                 //...
   
7.         }
   
8.         return 0;
   
9. }
   

复制代码

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

1. int func(int n) {
   
2.         if (n == 1) {
   
3.                 return 1;
   
4.         }
   
5.         else {
   
6.                 int step_count = 0;//记录步数
   
7.                 step_count += func(a - 1);  //移动上面的n-1个圆盘
   
8.                 step_count += 1;            //移动最下面的圆盘
   
9.                 step_count += func(a - 1);  //移动最上面的n-1个圆盘
   
10.                 return step_count；
    
11.                 //...
    
12.         }
    
13.         return 0;
    
14. }

复制代码

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

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

复制代码

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

跳转到最佳答案楼层

Cool_Breeze

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

zltzlt

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

Cool_Breeze

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

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

Croper

先写一个空函数

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

复制代码

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

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

1. int func(int n) {
   
2.         if (n == 1) {
   
3.                 return 1;
   
4.         }
   
5.         else {
   
6.                 //...
   
7.         }
   
8.         return 0;
   
9. }
   

复制代码

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

1. int func(int n) {
   
2.         if (n == 1) {
   
3.                 return 1;
   
4.         }
   
5.         else {
   
6.                 int step_count = 0;//记录步数
   
7.                 step_count += func(a - 1);  //移动上面的n-1个圆盘
   
8.                 step_count += 1;            //移动最下面的圆盘
   
9.                 step_count += func(a - 1);  //移动最上面的n-1个圆盘
   
10.                 return step_count；
    
11.                 //...
    
12.         }
    
13.         return 0;
    
14. }

复制代码

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

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

复制代码

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

沉默的人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

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