C++與演算法

費氏數列(費波那契數列)

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

維基百科 - 費氏數列



永生兔

義大利人費波那契(Leonardo Fibonacci) 他描述兔子生長的數目時用上了這數列。

  • 第一個月初有一對剛誕生的兔子
  • 年齡大於等於兩個月的兔子可以生育
  • 每月每對可生育的兔子會生下一對新兔子
  • 兔子永不死去
月份 1 2 3 4 5 6 7 8 9 10
兔子總數(對) 1 1 2 3 5 8 13 21 34 55
可生育的兔子數(對) 0 1 1 2 3 5 8 13 21 34



code - 遞迴版

#include<iostream>
using namespace std;

int f(int n)
{
    if( n==1 or n==2 )
        return 1;
    if( n >= 3 )
        return f(n-1)+f(n-2);
}

int main()
{
    int n;
    while( cin >> n )
    {
        cout << f(n) << endl;
    }

    return 0;
}

input

5
6
7
8
9

output

5
8
13
21
34

圖片來源



code - 迴圈陣列版

  • 遞迴版會重複計算已經知道的答案，浪費執行時間

  • 利用迴圈與陣列預先計算所有答案，便可瞬間回答問題

#include<iostream>
using namespace std;

int main()
{
    long long fib[75];
    int n, i;

    fib[1] = 1;
    fib[2] = 1;
    for( i=3 ; i<=70 ; i=i+1 )
        fib[i] = fib[i-1] + fib[i-2];

    while( cin >> n )
    {
        cout << fib[n] << endl;
    }

    return 0;
}

input

60
65
70

output

1548008755920
17167680177565
190392490709135



題目練習

自我思考

這些題目和費氏數列的關係是？