斐波拉契数列的应用

题目

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input
输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output
对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

样例

Sample Input

2

1 2

3 6

Sample Output

1

3

思路

观察给出的图，以f[i]表示相隔距离为i 的两个房间之间的路线数；
我们发现，若要到达第i个房间，则会通过第i-1,i-2号房间，而从i-1和i-2房走到第I号房有分别只有一种路线；
所以，f[i]=f[i-1]+f[i-2]

代码

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register int

#define fp(i,a,b) for(re i=a,I=b;i<=I;++i)

#define fd(i,a,b) for(re i=a,I=b;i>=I;--i)

#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);

using namespace std;

ll f[50];

inline ll solve(int a){

    if(a==1) return 1;

    if(a==2) return 2;

    for(register int i=3;i<=a;i++) f[i]=f[i-1]+f[i-2];

    return f[a];

}

int main(){

    //file("s");

    int n;

    cin>>n;

    f[1]=1;

    f[2]=2;

    for(register int i=1;i<=n;++i) {

        int a,b;

        cin>>a;

        cin>>b;

        cout<<solve(b-a)<<endl;

    }

    return 0;

}