题目要求：
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
->可认为是斐波那契数列
思路
情况1：如果只有一级台阶：显然只有一种跳法
情况2：如果有2级台阶，那么就有两种跳法。一种是分两次跳。每次跳1级，另一种就算一次跳2级
情况3：如果台阶级数大于2，设为n的话。这时我们把n级台阶时的跳法看成时n的函数，记为f(n) ，第一次跳的时候有两种不同的选择：一是第一次跳1级，此时的跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)，二是第一次跳2级，此时跳法的数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)，因此n级台阶的不同跳法的总数为：f(n) = f(n-1) + f(n-2)，不难看出就是斐波那契数列。
数学函数表达式：
根据上面的函数，我们可以很容易写出代码！
#include<stdio.h> int Frog_Step(int n) { if(n == 0) return 0; else if(n == 1) return 1; else if(n == 2) return 2; else return Frog_Step(n-1)+Frog_Step(n-2); } int main() { int n = 0; scanf("%d",&n); int ret = Frog_Step(n); printf("%d\n",ret); } 复制代码
延申1： 一次可以跳3个台阶
首先我们让青蛙一次可以跳3个台阶
1.当N=1时，有1种方法；
2.当N=2时，有2种方法；
3.当N=3时，青蛙可以选择第一步先跳1个台阶或者2个台阶或者3个台阶，有（1，1，1），（1，>2），（2，1），（3） 共四种方法；
4.当N=4时，青蛙选择第一步跳1层时，剩下3个台阶则时n=3时的方法； 青蛙第一步选择跳2层时，剩>下2个台阶则是n=2时的方法；
青蛙第一步选择跳3层时，剩下一个台阶则是n=1时的方法；
所以当n=4时的所有方法为： n=3的所有方法 + n=2的所有方法 + n=1的所有方法； 以此类推，当>N=n时，n层台阶的方法为：n-1 层的方法 + n-2 层的方法 + n-3 的方法；
//一次跳3个台阶 #include<stdio.h> int frog(int n) { if(n == 1) { return 1; } if(n == 2) { return 2; } if(n==3) { return 4; } return frog(n-1) + frog(n-2) + frog(n-3); } int main() { int n; scanf("%d",&n); int ways = frog(n); printf("%d\n",ways); return 0; } 复制代码
延申2：一次可以跳k层台阶
我们再继续向下延申，若青蛙一次可以跳k层台阶呢？
很显然，经过上面的讨论，这个问题已经变得不那么复杂了，我们只需要计算出青蛙在跳 1 层台阶一>直到青蛙跳 k 层台阶分别有多少种方法，再利用递归，就会轻而易举的得到结果。
int frog(int n, int k) { if(n == 1) { return 1; } if(n == 2) { return 2; } ....... ....... if(n == k) { return ?//跳 k 层台阶时的方法 } return frog(n-1) + frog(n-2)+ ........+frog(n-k); } 复制代码
