鱼C论坛

 找回密码
 立即注册
查看: 1777|回复: 9

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

[复制链接]
发表于 2020-1-14 11:28:24 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Cool_Breeze 于 2020-1-14 14:54 编辑

  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. }
复制代码
最佳答案
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. }
复制代码

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

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-1-14 11:33:20 | 显示全部楼层
搞不懂啊!(头都大了)!!太难了!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-14 11:34:06 | 显示全部楼层
这根本不是汉诺塔递归啊。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-14 11:36:22 | 显示全部楼层
zltzlt 发表于 2020-1-14 11:34
这根本不是汉诺塔递归啊。。

这是我写的递归(我想因该是)!但是汉诺塔那个我理解不了!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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. }
复制代码

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

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-14 12:23:51 | 显示全部楼层
把形参的本质搞明白,你就明白汉诺塔了
楼主写的求和工具是递归
写成f(x)的形式就是这样:(认为x是整数):
当x等于一时 f(x) = 1
当x大于一时 f(x) = f(x - 1)
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-14 12:25:41 | 显示全部楼层
你要搞清楚哪个是起始,哪个是中介,哪个是目标
至于过程,就是冰箱开开,大象塞进去,冰箱关上的步骤。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-14 14:45:43 | 显示全部楼层
你可以看看数据结构C语言第五版上面的过程很清楚,圆盘从大到小编码1~n,有A,B,C三个棍子,当只有一个圆盘的时候把A上的直接移动到C上,否则将n-1个圆盘按A~C~B移动,再将第n个圆盘移到C,再将n-1个圆盘又B~A~C移动就好了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-14 14:49:13 | 显示全部楼层
汉诺塔递归,其实有很多人都没有完全明白。我了说一下自己的理解,看看能否帮得上你。

递归第一层:任务是把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层的一坨搬过去?……
当深入下去,只剩下一层的时候,就可以直接搬了。

所谓递归,就是一层一层的进去,到了最底层的时候得到结果,然后再一层一层的返回来,得到最后需要的结果
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-14 14:53:59 | 显示全部楼层
我想先放下这个?看完后再回头继续!谢谢大家!!!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2025-7-13 17:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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