斐波那契数列生成

- 日理万妓 2022-06-11 01:23 75阅读 0赞

## 前言 ##

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）。

下面将测试3中不同的方式（测试为40）去生成斐波那契数列， 比较运行的效率。

## 1. 递归产生 ##

//递归生成第n项斐波那契数列
    int fibonacii_recursive(int num)
    {
        if(0 == num)
            return 0;
        if(1 == num)
            return 1;
    
        return fibonacii_recursive(num-1)+fibonacii_recursive(num-2);
    }

运行结果

![SouthEast][]

## 2. for循环生成 ##

//for生成第n项斐波那契数列
    int fibonacii_for(int num)
    {
        if(num < 1)
            return -1;
        if(num <= 2)
            return 1;
        int f1 = 1;
        int f2 = 1;
    
        int value;
        for(int i=3; i<=num; ++i)
        {
            value = f1 + f2;
            f1 = f2;
            f2 = value;
        }
    
        return value;
    }

运行结果

![SouthEast 1][]

## 3. 动态规划思想 ##

使用一个缓存数组来存储中间变量，避免重复计算

int *fibo = nullptr;
    //使用动态规划的思想得到第n项斐波那契数列
    int fibonacii_dyna(int num)
    {
        if(0 == num)
            return 0;
        if(1 == num)
            return 1;
        if(fibo[num] != 0)
            return fibo[num];
    
        fibo[num] = fibonacii_dyna(num-1) + fibonacii_dyna(num-2);
    
        return fibo[num];
    }
    
    fibo = new int[num+1];
    for(int i=0; i<=num; ++i)
    {
          fibo[i] = 0;
    }
    fibonacii_dyna(num); //num=40
    delete [] fibo;
    fibo = nullptr;

运行结果

![SouthEast 2][]

[SouthEast]: /images/20220611/2d4d8275046e4a479b18f75afd5c5698.png
[SouthEast 1]: /images/20220611/c9d7c4ad96ac4adf953c0a566c1646c3.png
[SouthEast 2]: /images/20220611/042f257e9dbd4c5ca14b13d3787917bd.png