题目描述

一只青蛙一次可以跳上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)