K-小さなミツバチ...

小さなミツバチが...

タイトルの説明

訓練を受けたミツバチは右側の隣のミツバチの部屋にしか登れず、逆方向に登れない.ミツバチがミツバチの部屋aからミツバチの部屋bに登る可能性のあるルート数をプログラミングして計算してください.このうち、蜂の巣の構造は以下の通りです.

Iutput

入力データの最初の行は整数Nであり、テストインスタンスの個数を表し、次にN行データであり、各行には2つの整数aおよびb(0

Output

各試験例について、ミツバチがミツバチ室aからミツバチ室bに登る可能性のある経路数を出力し、各例の出力が1行を占める.

Sample Input

2 1 2 3 6

Sample Output

1 3

考え方:

ミツバチという問題は原理的にH問題と同じで、階段を上る起点と終点を調整したのと同じで、プッシュの原理は公式と同じです.しかし、この問題では、変数を定義するにはlong long型を使用しなければなりません.そうしないとオーバーフローします.

コード#コード#

#include 
int s,e;
int main()
{
    int n;
    int i;
    long long a[55];
    a[1]=0;
    a[2]=1;
    a[3]=2;
    for(i=4; i<55; i++)
    {
        a[i]=a[i-1]+a[i-2];
    }
    scanf("%d",&n);
    while(n)
    {
        scanf("%d%d",&s,&e);
        printf("%lld
",a[e-s+1]);
        n--;
    }
    return 0;
}