九度OJ-テーマ1387:フィボナッチ数列

タイトルリンクアドレス:
九度OJ-テーマ1387:フィボナッチ数列
皆さんはフィボナッチ数列を知っています.今、整数nを入力するように要求しています.フィボナッチ数列のn番目の項目を出力してください.フィボナッチ数列の定義は、入力には複数のテストサンプルが含まれる可能性があり、各テストケースについて、入力には整数n(1<=n<=70)が含まれる.
出力:各テストケースに対応して、n番目のフィボナッチ数列の値を出力します.
サンプル入力:3
サンプル出力:2
問題解決の考え方:
フィボナッチ数列は古典的な数学問題であり、フィボナッチ数列の公式によると、すぐに再帰的な解法を考え、以下のコードを書くことができます.
long long getFibonacci(int n) {       if(0 == n)               return 0;       else if(1 == n)               return 1;       else               return getFibonacci(n - 1) + getFibonacci(n - 2); } しかし、このような効率はあまりにも低く、弟はこのコードで40番目のフィボナッチ数列を求めるのに2.7秒ほどかかりましたが、私が70番目のフィボナッチ数列を求めるようになったとき、私のノートが熱くなり始め、CPUファンが高速で回転し、長い間70番目のフィボナッチ数列を得ることができませんでした.なぜ再帰の効率がこんなに低いのですか?再帰演算には多くの「繰返し計算」が存在し、再帰は関数が自身を繰り返し呼び出すため、スタックスペースを絶えず申請し、解放する必要があり、時間とスペースのオーバーヘッドが増加しているため、詳細はこのブログを参照してください:漫談再帰:再帰の効率の問題
再帰効率がこんなに低い以上,反復法を用いてこの問題を解決するしかない.問題を通して,0番目と1番目のフィボナッチ数列が分かったが,2番目からフィボナッチ数列はf(n)=f(n−1)+f(n−2),n>1を満たす.したがって、フィボナッチ数列の0番目と1番目を加算してフィボナッチ数列の2番目を得ることができ、1番目と2番目を加算して3番目を得ることができます.順次類推すると,n−2項目とn−1項目を加算してn項目のフィボナッチ数列を得ることができる.反復法を使用すると、前の演算で得られた結果を中間値として新しい結果を推定することができ、再帰アルゴリズムにおける「繰返し計算」の問題を回避し、スタック空間の追加申請と解放を必要とせず、アルゴリズムの時間と空間効率を向上させることができる.フィボナッチ数列の70項目はintの表示範囲を超えているため、64ビット整数でフィボナッチ数列を格納する必要がある.MACコードは以下の通りである.

#include<stdio.h>
#define N 70
 
long long fibonacci[71];        //  long long fibonacci   
 
/**
*  
* @param n   n 
* @return void
*/
void getFibonacci(int n)
{
    int i;
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for(i = 2;i <= n;i++)
    {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }
}
 
int main()
{
    int n;
    getFibonacci(N);
    while(EOF != scanf("%d",&n))
    {
        printf("%lld
",fibonacci[n]);      //  long long   lld
    }
    return 0;
}
 
/**************************************************************
    Problem: 1387
    User: blueshell
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:916 kb
****************************************************************/