您的位置:首页 > 房产 > 建筑 > C语言函数递归练习—青蛙跳台阶、汉诺塔问题

C语言函数递归练习—青蛙跳台阶、汉诺塔问题

2024/12/23 9:00:10 来源:https://blog.csdn.net/weixin_70620792/article/details/140903142  浏览:    关键词:C语言函数递归练习—青蛙跳台阶、汉诺塔问题

文章目录

  • 1. 青蛙跳台阶
    • 1.1 问题描述
    • 1.2 解题思路
  • 2. 汉诺塔问题
    • 2.1 问题描述
    • 2.2 解题思路

1. 青蛙跳台阶

1.1 问题描述

  • 一只青蛙一次跳一个或两个台阶,问:n节台阶青蛙有多少种跳法
  • 一节台阶 --> 1种
  • 两节台阶 --> 2种
  • 三节台阶 --> 3种
  • 四节台阶 --> 5种
    在这里插入图片描述

1.2 解题思路

  • 青蛙的跳法
  • 1 2 3 5 ……
  • 是不是类似斐波切列数的规律呢,第n个数等于前两个数之和
  • n为台阶数,用test(n)实现跳法的计算
  • test(n)= test(n-1)+ test(n-2)
  • 递归解法
//1 2 3 5……
//n=(n-1)+(n-2)
//递归实现
#include <stdio.h>
int test(int n)
{if (n > 1)return test(n - 1) + test(n - 2);elsereturn 1;
}
int main()
{int n = 0;printf("请输入你想计算的台阶数>:");scanf("%d", &n);int ret = test(n);printf("当台阶数为%d时,青蛙有%d种跳法\n", n, ret);return 0;
}

在这里插入图片描述

  • 迭代解法
//非递归解法
//1 2 3 5 8……
//将a、b分别赋给第一、第二项,tmp=a+b,然后把b的值赋给a,tmp的值赋给b,tmp=a+b
//a=1  b=2     tmp = a+b -> 3
//a=b -->2      b = tmp --> 3    tmp = a + b --> 5
//a=b -->3      b = tmp --> 5    tmp = a + b --> 8
#include <stdio.h>
int test(int n)
{int a = 1;int b = 2;int tmp = 0;if (n == 1)return 1;else if (n == 2)return 2;else{while (n > 2){tmp = a + b;a = b;b = tmp;n--;}return tmp;}
}
int main()
{int n = 0;printf("请输入你想计算的台阶数>:");scanf("%d", &n);int ret = test(n);printf("当台阶数为%d时,青蛙有%d种跳法\n", n, ret);return 0;
}

在这里插入图片描述
  注意递归求解时碰见较大的数时,由于庞大的分支使得编译器会报错,而迭代计算相对来说就可以避免类似的问题,因此递归也需要根据使用场景合理使用

2. 汉诺塔问题

2.1 问题描述

  • 现在有A、B、C三根柱子,A柱子上有64张卡片,且64张卡片从小到大堆叠,问:将A柱子上的卡片移到C柱子上,一次只能移一张卡片,可以通过B柱子作为媒介,且转移的过程中必须保持大卡片在下,小卡片在上
    在这里插入图片描述
    在这里插入图片描述
  • 分析:第一步,n-1张卡片放入B;第二步,第n张卡片放入C;第三步,n-1张卡片放入C。
  • 接下来就是n-1张卡片的转移
  • 一样的道理,将n-2张卡片看成一个整体先转移出去,然后把第n-1张卡片转移到C柱

2.2 解题思路

假设现在是三张卡片在这里插入图片描述

第一步,将第一张卡片移到C柱
在这里插入图片描述

第二步,将第二张卡片移到B柱
在这里插入图片描述

第三步,将第一张卡片移到B柱
在这里插入图片描述

第四步,将第三张卡片移到C柱
在这里插入图片描述

第五步,将第1张卡片移到A柱
在这里插入图片描述

第六步,将第2张卡片移到C柱
在这里插入图片描述

第七步,将第1张卡片移到C柱
在这里插入图片描述

//汉诺塔问题
//现在有A、B、C三根柱子,A柱子上有64张卡片,由小到大,将A柱子上的卡片转移到C柱
//转移过程中小的卡片必须在大卡片的上面,一次只能转移一张卡片#include <stdio.h>
void move(int n, char x, char y)
{printf("第%d张卡片从%c--->%c\n", n, x, y);
}
void test(int n, char A, char B, char C)
{if (n == 1)move(n, A, C);else{test(n - 1, A, C, B);//将A柱子上的n-1张卡片移到Bmove(n, A, C);       //将最后一张卡片移到C柱test(n - 1, B, A, C);//将B柱子上的n-1张卡片移到C}
}
int main()
{int n = 0;printf("请输入A柱子上的卡片数>:");scanf("%d", &n);test(n, 'A', 'B', 'C');return 0;
}

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com