HDU 2044 一只小蜜蜂...

Problem Description

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

其中，蜂房的结构如下所示。

image.jpeg

Input

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

Output

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

Sample Input

2 1 2 3 6

Sample Output

1 3

题目意思就是找到蜜蜂从 a 出发到达 b 的所有可能路线；

由题意可以推得：

  从 1 到 2 的可能路径为： 1->2；                                                                                                                                                          1种

  从 1 到 3 的可能路径为： 1->2->3，1->3；                                                                                                                                        2种

  从 1 到 4 的可能路径为： 1->2->3->4，1->3->4，1->2->4；                                                                                                          3种

  从 1 到 5 的可能路径为： 1->2->3->4->5，1->2->4->5，1->3->4->5，1->2->3->5，1->3->5；                                             5种

  从 1 到 6 的可能路径为： ......                8种；

由此可以推知第 n 个的可能路径为 f(n)=f(n-1)+f(n-2); 和斐波那契数列的递推公式一样；

c++ code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

long long F(int a, int b)

{

    int n;

    n = b - a;

    long long  f[55];

    f[1] = 1;

    f[2] = 2;

    if (n > 2)

    {

        for (int i = 3; i <= n; i++)

            f[i] = f[i - 1] + f[i - 2];

    }

    return f[n];

}

int main()

{

    int a, b, n;

    cin >> n;

    while (n--)

    {

        cin >> a >> b;

        cout << F(a,b) << endl;

    }

}```