剣指OFFERの踊り場(九度OJ 1388)

タイトルの説明:

1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.

入力:

入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=70)を含む.
 

出力:

各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
 

サンプル入力:

5

サンプル出力:

8

テーマ分析：

この問題は明らかに順方向分析ではだめだ.つまり、一番後ろの階段は、前の階段に依存しなければならない.したがって,最後のステップの方法数は前から計算できる.では、よく考えてみると、カエルは1~2歩しか踊れません.つまり、最後の階段は前の階段か前の2つの階段で上がったに違いありません(このとき階段の数が長いと仮定します).最後のステップに達する方法の数は、前のステップの方法の数と前の2つのステップの方法の数に等しいことが明らかになった.ここでは、これは典型的なフィボナッチ数列であることが分かった.問題はよく解決して、前の問題の構想の上で見て、受けなければならない2つの問題:
1タイムアウトしない
2データのフォーマットに注意し、long long出力時に%lldを使用する

コード#コード#

#include <stdio.h>

long long stair[71];

void getStair(void);

int main(){

    int n;

    getStair();

    while(scanf("%d",&n) != EOF && n>=1 && n <= 70){

        printf("%lld
",stair[n]);

    }

    return 0;

}

void getStair(void){

    int i;

    stair[0] = 1;

    stair[1] = 1;

    for(i=2;i<71;i++){

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

    }

}

/**************************************************************

    Problem: 1388

    User: xhalo

    Language: C

    Result: Accepted

    Time:0 ms

    Memory:916 kb

****************************************************************/