斐波那契數列的兩種實作

代碼實作

C++

#include<iostream>
using namespace std;

// 遞歸實作 O(2^n) 一變二 二變四...
long fib1(unsigned int no){
    if (no == 0) {
        return 0;
    }
    else if(no == 1) {
        return 1;
    }
    else { // 重複計算的值太多
        return fib1(no - 1) + fib1(no - 2);
    }
};

// 非遞歸實作 O(n)
long fib2(unsigned int no){
        long pre2 = 0; // 前面的前面
        long pre1 = 1; // 前面
        while(no --){
            long tmp = pre1;
            pre1 = pre2 + pre1;
            pre2 = tmp;
        }
        return pre2;
}

int main(int argc, char const *argv[])
{   
    cout << fib1(0) << endl;
    cout << fib1(1) << endl;
    cout << fib1(30) << endl;
    cout << fib2(0) << endl;
    cout << fib2(1) << endl;
    cout << fib2(30) << endl;
    return 0;
}