• 文章
  • 斐波那契的最佳实现
作者：
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`