C语言实现青蛙跳台阶问题

前言

青蛙跳台阶是一个非常经典的递归问题，其具体问题是：

一只青蛙想要跳上一个台阶，这个台阶一共有n级，青蛙一次可以选择跳1级台阶或者跳2级台阶，那么青蛙一共有多少种方法可以跳上台阶呢？

一、问题分析

1.当台阶只有1级时

此时青蛙只有一种跳法，那就是跳1级

2.当台阶有2级时

不难看出，青蛙有两种跳法，一是跳1级再跳1级，二是一下跳2级。

3.当台阶有n级时

当台阶有n级时，题目好像一下子就复杂起来了，青蛙该怎么跳啊，其实不然，我们换个方向思考。

假如青蛙已经跳到了最上面，也就是第n级台阶，那青蛙有几种方法跳上来的呢？这就很清晰了，青蛙可能是从n-1级台阶跳了1级台阶上来的，又或者是从n-2级台阶跳了2级台阶上来的。

n来自n-1或者n-2，n-1来自n-2或者n-3，n-2来自n-3或者n-4…

一直到n-（n-1）来自0，n-（n-2）来自1或者0。

不难发现，这个方法在不断根据一个未知去往前推到已知，很标准的递归方式，故本题使用递归方法就可实现。

二、代码实现

1.完整代码

代码如下：

#include<stdio.h>
int main()
{
  int step = 0;
  scanf("%d", &step);
  int ret = jump(step);
  printf("青蛙有%d种方式跳到%d级台阶上", ret, step);
  return 0;
}
int jump(int step)
{
  //只跳了一级
  if (1 == step)
  {
    return 1;
  }
  //跳了两级
  else if (2 == step)
    return 2;
  else
    return jump(step - 1) + jump(step - 2);
}

2.结果测试

结果如下：

1级台阶：

2级台阶：

20级台阶：

台阶数不宜过多，因为递归算法重复计算的数据较多，占用时间长，过多的重复计算会导致程序执行很慢。

总结

本篇浅显了介绍了如何在C语言中使用递归算法实现小小的青蛙跳台阶的问题，重点不再如何解决问题，而在于对递归思想的一种理解和加深。递归可以解决很多新奇有趣的题目，若是日后遇见看不懂且感觉有规律的题，不妨用用递归。