题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入
多组测试样例。每组测试样例包含一个整数n。(1<=n<=100)
输出
每组测试样例输出一行，表示青蛙跳上n级台阶的跳法数量，所得到的结果模1000000007
样例输入
3
4
样例输出
3
5
分析和解决
斐波拉契数列的变形应用，设跳上n阶的跳法数量为f(n),分两种情况
1.第一次跳一步，这时的跳法数量为剩下n-1级台阶的跳法数量，即f(n-1)
2第一次跳两步，这时的跳法数量为剩下n-2级台阶的跳法数量，即f(n-2)
所以，f(n)=f(n-1)+f(n-2)
代码
#include<iostream>
using namespace std;
const int mod=1e9+7;
int main()
{
int count[105];
count[1]=1;
count[2]=2;
for(int i=3;i<101;i++){
count[i]=(count[i-1]+count[i-2])%mod;
}
int n;
while(cin>>n) cout<<count[n]<<endl;
}
-
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1.当n=1时，f(1)=1
2.当n=2时，第一次可以跳1或者2步，f(2)=f(2-1)+1
3.当n=3时，第一次可以跳1或者2或者3步，f(3)=f(3-1)+f(3-2)+1
4.以此类推，f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-1))+1
f(n-1)=f(n-2)+f(n-3)+...+f(n-(n-1))+1
所以f(n)=2*f(n-1)
