題目描述

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

輸入

多組測試樣例。每組測試樣例包含一個整數(shù)n。(1<=n<=100)

輸出

每組測試樣例輸出一行，表示青蛙跳上n級臺階的跳法數(shù)量，所得到的結(jié)果模1000000007

樣例輸入

3
4

樣例輸出

3
5

分析和解決

斐波拉契數(shù)列的變形應用，設跳上n階的跳法數(shù)量為f(n),分兩種情況
1.第一次跳一步，這時的跳法數(shù)量為剩下n-1級臺階的跳法數(shù)量，即f(n-1)
2第一次跳兩步，這時的跳法數(shù)量為剩下n-2級臺階的跳法數(shù)量，即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)