【C语言刷题】青蛙跳台阶

一、问题描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

二、问题分析

青蛙跳台阶，相信大家一开始看到这道题也是没有一点思路，但是不要担心，相信自己一定能解决这道经典题目的。

这道题我们无法直接肉眼观察出一些规律，但是我们有数学归纳法，直接看不出来，我们先写三项，三项看不出来，我们写五项，写的多了总会看出来的。

1.当n=1时

显然只有1级台阶，那么肯定只有一种跳法了。

2.当n=2时

这个时候我们有两种跳法，一种是直接跳两级，另外一种是先跳一级，再跳一级。

3.当n=3时

这个时候我们的选择可就多了，单纯的打字打出来并不是一种明智的选择，我们画一个图试试看

青蛙第一次可以选择跳一层，也可以第一次跳两层，为了方便起见，不妨我们定义青蛙跳n层台阶共有f（n）种跳法

那么f（3）就有如下图所示，第一次跳1或者2，如果是1，则第二次继续跳1，或者2，如果第一次是2，那么直接跳1即可

4.n=4，n=5........n=n时

其实在这块已经有人能看到规律了，因为第一步无非就两种跳法，要么跳1，要么跳2。如果假设n个台阶有f（n）种跳法。那么则第二步有f（n-1）和f（n-2）种跳法。然后我们就发现，这不就是斐波那契数列吗。只不过就是把第二项变为2了。其余一个都没变

事实上，确实是这样的，这道题规律是比汉诺塔要好找很多的。

三、代码实现

既然本质上上就是一个斐波那契数列求第n项，只不过是第二项变为2了这种情况。那么问题迎刃而解，斐波那契数列在之前的文章中花费了大量的篇幅去详细讲解，这里给出传送门：http://t.csdn.cn/Khk31

我们直接实现代码吧

#include<stdio.h>
int f(int n)
{
  if (n == 1)
  {
    return 1;
  }
  else if (n == 2)
  {
    return 2;
  }
  else
  {
    return f(n - 1) + f(n - 2);
  }
}
int main()
{
  int n;
  scanf("%d", &n);
  int ret = f(n);
  printf("%d", ret);
  return 0;
}

总结

好了本期内容就讲解这么多，青蛙跳台阶和汉诺塔问题有点类似，都是需要透过现象看本质。寻找规律，从而一举制胜。