フィボナッチ数列

再帰を使ったフィボナッチ数列

このアルゴリズムには一つの欠陥がある！

計算量の大きさ

なぜなら、fibonacchi()をf()と表すと、例えばf(5)を求める際にf(4),f(3)が必要となるが、更にf(4)で再びf(3)を呼び出す必要がある。つまり。一度計算した値を再び計算するという無駄・欠陥がある！！

#include<bits/stdc++.h>
using namespace std;

int fibonacci(int n){
    if (n==0 || n==1) return 1;
    else return fibonacci(n-2) + fibonacci(n-1);
}

int main(){
    int N,ans; cin >> N;
    ans=fibonacci(N);
    cout << ans;
}

動的計画法を使ったフィボナッチ数列

このアルゴリズムでは、フィボナッチ数を小さいほうから計算していくので、F[i]を計算するときには既にF[i-1]とF[i-2]が計算されており、それらを有効利用できる！

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    int F[50];

    F[0]=F[1]=1;
    for (int i=2; i<=n; i++) F[i]=F[i-1]+F[i-2];

    cout << F[n] << endl;
    return 0;
}

メモ化再帰によるフィボナッチ数列

このアルゴリズムでは、一度計算したf[i]の値を配列の要素F[n]に記録しておくことで再計算を回避できる！

#include<bits/stdc++.h>
using namespace std;

int fibonacci(int n){
    int  F[100]={0};
    if (n==0 || n==1) return F[n]=1;
    if (F[n]!=0) return F[n];

    return F[n] = fibonacci(n-2) + fibonacci(n-1);
}

int main(){
    int N,ans; cin >> N;
    ans=fibonacci(N);
    cout << ans << endl;
    return 0;
}

注意 vectorを用いて処理するとTLになる

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector <int> A(n);
    A[0]=A[1]=1;

    for (int i=2; i<=n; i++){
        A[i]=A[i-1]+A[i-2];
    }

    cout << A[n] << endl;//n=5までしか出力できない！
}