• 文章
  • 斐波那契的最佳實現
作者：
2015年3月28日

斐波那契的最佳實現

評分：3.5/5（530 票）
*****
這篇文章將討論一個我在大學工程專業考試中遇到的問題。它是一道作業題。問題如下：

編寫一個最高效的程式，打印出斐波那契數列，直到執行時給定的數值為止，並將這些值儲存在一個數據結構中以備後用。你的程式碼必須非常節省記憶體，並且時間複雜度要遠優於普通程式。你不能使用動態記憶體分配！

嗯，確切地說，有很多種方法可以解決這個問題。人們使用了很多技巧來解答這道題。但是等等，這個問題本身有一個難點，那就是語言的選擇。如果你想用傳統的C語言來做，那麼在儲存數值的時候就會遇到問題。

你看，問題中提到，你不僅要打印出某個值之前的數列，還需要將資料儲存到一個數據結構中。在C語言中，我們只有一個基本的資料結構可以在連續的記憶體位置上儲存一系列資料：陣列。但C語言中陣列的問題在於，你不能宣告一個可變大小的陣列。例如，`int a[size]` 這行程式碼會導致程式崩潰。因此，你無法在執行時宣告陣列的大小，而這恰恰是程式的目標。

下一個解決方案是使用動態記憶體分配，像這樣：

1
2
3
4
5
6
7
 

    int size;
    printf("Enter the length of the series :: ");
    scanf("%d", &size);
    int *memPtr = (int *)malloc( (size_t)( (int)sizeof(int) * size ) );
    // insert the series..
    free(memPtr);



但在題目中明確提到，你不能使用動態記憶體分配，因此這個選項完全無效。

所以事實是，你無法用傳統的C語言來設計它……至少據我所知是這樣。因此，我轉向了C++，經過一些調整和改進，我最終設計出了一個我的教授喜歡並最終接受的方案。因此，本文的目的是展示我的設計，並向社群的同行們徵求是否有更好的解決方案。

我建立了一個頭檔案，名為 fibo.h，以及它的定義檔案 fibo.cpp、main.cpp，當然還有 Makefile。下面是我的各個檔案：

fibo.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
    #ifndef _fibo_h_
    #define _fibo_h_
    #include <vector>
    class Fibonacii{
    private:
    int size;
    std::vector<long> data;
    public:
    Fibonacii(int);
    void create_series(void);
    void get_data(void);
    };
    #endif // _fibo_h_


fibo.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    #include "fibo.h"
    #include <iostream>
    #include <vector>
    using namespace std;
    // This creates a Fibonacii series
    void Fibonacii::create_series(void){
    data.push_back(0);
    data.push_back(1);
    for (int i = 2; i < size; ++i)
    {
    /* code */
    data.push_back(data[i - 2] + data[i - 1]);
    }
    }
    // This is a constructor
    Fibonacii::Fibonacii(int s){
    size = s;
    }
    // This method is used to print the series
    void Fibonacii::get_data(void){
    for (long i: data)
    cout << i << endl;
    }

main.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
    #include "fibo.h"
    #include <string>
    #include <iostream>
    #include <string>
    using namespace std;
    int main(int argc, char *argv[])
    {
    /* code */
    if (argc == 2) {
    int value = stoul(argv[1], nullptr, 10);
    static Fibonacii Fibo(value);
    Fibo.create_series();
    Fibo.get_data();
    return 0;
    }
    }


Makefile 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    MAIN = main
    HEADER_DEFINITIONS = fibo
    CC = g++-4.9 -std=c++11
    COMPILE = -c
    EXE = $(MAIN)
    OPTIMIZE = -Os
    SHELL = /bin/bash
    ARGS = 20
    all: link
    @echo "Executing..........."
    @echo " > > > > > > OUTPUT < < < < < < "
    @$(SHELL) -c './$(EXE) $(ARGS)'
    link: compile
    @echo -n "Linking............."
    @$(SHELL) -c '$(CC) -o $(EXE) *.o'
    compile: $(MAIN).cpp $(HEADER_DEFINITIONS).cpp
    @echo -n "Compiling........."
    @$(SHELL) -c '$(CC) $(OPTIMIZE) $(COMPILE) $^'
    clean:
    @echo "Cleaning............"
    @$(SHELL) -c 'rm -f *~ *.o $(EXE)'




【注意：如果你沒有g++4.9版本，就只用g++。但別忘了加上-std=c++11引數】

【注意：vector是一種資料結構，據我所知，它是透過類模板和動態記憶體分配實現的。因此，這個程式仍然間接使用了動態記憶體分配】

【注意：如果你需要改變數列的長度，請將ARGS = 20的值修改為你想要的任何值】

要執行該程式，只需在你的終端中進入該目錄，然後輸入 `make all`