当前位置：首页 > news >正文

青蛙跳台阶用函数的递归解决

news 2026/6/18 13:17:41

问题

一只青蛙想要跳到第n级台阶（n为非负整数）。它每次只能跳1 级或2 级台阶，问这只青蛙跳到第n级台阶共有多少种不同的跳法？

举例

首先我们先从简单的开始分析：

当n=1时；青蛙只有一种跳法：就是跳一级台阶；

当n=2时；青蛙只有两种跳法：1.一次跳一级台阶，共跳两次；2.一次跳两级台阶，共跳一次；

当n=3时；青蛙有三种跳法：1.一次跳一级台阶，共跳三次；2.第一次跳两级台阶第二次跳一级台阶，共跳两次；3.第一次跳一级台阶第二次跳两级台阶，共跳两次；

当n=4时；青蛙有五种跳法：1.一次跳一级台阶，共跳4次；2.第一次跳一级台阶第二次跳两级台阶第三次跳一级台阶，共跳三次；3.第一次跳一级台阶第二次跳一级台阶第三次跳两级台阶，共跳三次；4.第一次跳两级台阶第二次跳一级台阶第三次跳一级台阶；共跳三次；5.第一次跳两级台阶第二次跳两级台阶

......

我们看青蛙共有2种跳跃方式：一级或两级台阶；假设要跳跃的台阶为a级；每次跳跃后以跳跃到的台阶为起点发现剩余跳跃的台阶为a-1或a-2级，按照数学思想，a级的台阶跳跃数的种类为(a-1)与(a-2)的种类数之和。由此我们可以用函数的递归来解决这类问题。

代码验证

#include<stdio.h> int frog(int n) { if(n<=2){return n;} else return frog(n-1)+frog(n-2); } int main() { int a; printf("请输入青蛙要跳跃的台阶数：\n"); scanf("%d",&a); printf("青蛙跳跃%d级台阶共有%d种方法",a,frog(a)); return 0; }

扩展

那如果青蛙可以跳k级台阶呢（k ≤ n，即每次最多跳当前剩余台阶数）？

分析

由原问题分析可得，当k>n时，符合上述问题分析（即可将n级台阶分为k组，n级台阶的跳法=n-1与n-2与...n-k级台阶跳法之和)

代码验证

#include <stdio.h> long long frog(int n, int k) { long long recur(int m) { if (m == 0) { return 1; } long long sum = 0; for (int i = 1; i <= k && i <= m; i++) { sum += recur(m - i); } return sum; } return a(n); } int main() { int n, k; printf("请输入台阶数n（非负整数）和最大跳级k："); scanf("%d %d", &n, &k); long long res = frog(n, k); printf("跳到第%d级台阶共有%lld种不同跳法\n", n, res) return 0; }