寻找斐波那契数列最优解(C++)

• 斐波那契数列简介
• 算法部分
  • 一、原版递归
  • 二、尾递归（存值版递归）
  • 三、双指针缓存（存值版非递归）
  • 四、二阶矩阵

因为在刷《剑指offer》的时候又又又又遇到了这个题，脑子里响起了“塔塔开，不塔塔开就无法胜利啊！”，于是我准备好好把斐波那契数列弄明白，然后此文就诞生了。

斐波那契数列简介

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、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）**

算法部分

一、原版递归

long long fibonacci(unsigned int n) {
long long f[2] = {0, 1};
if(n<2)return f[n];

return fibonacci(n-1) + fibonacci(n-2);
}


n = 5

n = 40(尝试了一下n=100，结果渣机在两分钟之内没跑出来)

#include
using namespace std;
int main(void) {
long long out = fibonacci(40);
cout < return 0;
}


消耗时间：0.9454s

当n比较小的时候，运算还是比较愉快的~

但是当n比较大的时候事请就变得严重了~

那么，为什么呢？

其实斐波那契数列的递归过程可以看作一棵完全二叉树的建立（以n=5为例）：

最后f[5] = f[1] + f[0] + f[1] + f[1] + f[0] + f[1] + f[0] + f[1] = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5

我们发现，有好多没必要的重复计算出现。

比方说f(2)已经求出来了，但是我没有储存这个结果，于是计算机就得再求一遍，那么时间就会增加，这好吗？这不好！

这个例子f(2)求了3遍 f(3)求了2遍，而求f(5)只需要分别求1遍f(4),f(3),f(2)。

这样递归相当于浪费了一半的时间！

于是捏，我们就可以把已经求过了的f给存起来，给计算机减负。

二、尾递归（存值版递归）

long long fibonacci(int f0,int f1,unsigned int n) {

if(n > 0) {
return fibonacci(f0+f1,f0,n-1);
}

return f0;
}


n = 40

#include
using namespace std;
int main(void) {
long long out = fibonacci(0,1,5);//当然f0=0,f1=1咯，带进去就好了
cout < return 0;
}


消耗的时间：0.2618s

三、双指针缓存（存值版非递归）

long long fibonacci(unsigned int n) {
long long f[100000] = {0, 1};
if(n<2)return f[n];

for(size_t i=2;i<=n;i++){
f[i] = f[i-1] + f[i-2];//每一次循环记录下新的f的值，不重复计算
}

return f[n];
}


n = 40

#include
using namespace std;
int main(void) {
long long out = fibonacci(40);
cout < return 0;
}


消耗时间：0.1321s

存下值后再进行计算是不是快了很多！！！

但是，俗话说得好，活到老，学到老。

所以有没有更快、更强的方法呢？

别急，马上安排上！

四、二阶矩阵

这个算法的时间复杂度为log(n)，但前提是你要有一点点线代的知识，什么，你说没有？那我现场教你！

在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利首先提出。

矩阵求值：

好了教完了，以上知识均来自于百度，但是我为什么要教你呢？因为你如果不懂这些的话大概率不会自学，不自学就不会往下看，不往下看我就不能装13，装不了13我就会很难受，所以为了我能装13，我必须教大家这个。

首先有这样一个这个公式：{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}^n-1

不知道也很简单，自己证明一下，上面的知识加上你高中数学知识足够证明出来。

有了这个公式，要求f(n)，我们只需要求矩阵{1, 1, 1,0}的(n-1)次方。

但是如果我们从0开始循环，n次方仍然需要n次运算，和存值版没啥大的区别。

但是！他是乘方啊，乘方就可以分成两半，这样我们就不需要n的时间复杂度了，而是二分法所带来的趋于log(n)的时间复杂度！！！！

别懵，我来举个例子。

比方说你要求：2⁶

普通人：2 * 2 = 4

​ 4 * 2 = 8

​ 8 * 2 = 16

​ 16 * 2 = 32

​ 32 * 2 = 64

二分人：2² = 2 * 2 = 4

​ 2³ = 2² * 2 = 8

​ 2⁶ = 2³ * 2³ = 8 * 8 = 64

普通人算了五次，而二分人只算了三次

了解了这些之后我们直接上代码！

struct Matrix2By2//2x2矩阵
{
Matrix2By2(long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0):m_00(m00), m_01(m01), m_10(m10), m_11(m11){}//初始化二元矩阵的四个元素
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};
Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1, const Matrix2By2& matrix2){
return Matrix2By2(matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}//矩阵乘法
Matrix2By2 MatrixPower(unsigned int n)
{
Matrix2By2 matrix;
if(n == 1)
{
matrix = Matrix2By2(1, 1, 1, 0);
}
else if(n % 2 == 0)
{
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix, matrix);
}
else if(n % 2 == 1)
{
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
}
return matrix;
}//矩阵乘方
int fibonacci(unsigned int n) {
int result[2] = {0, 1};
if(n <= 2)return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n-1);
return PowerNMinus2.m_00;//返回的就是f[n],记不得可以回去看下公式
}


n=40

int main(void) {
long long out = fibonacci(40);
cout < return 0;
}


消耗时间：0.09125s

太帅了！

试试之前那哥们儿算不出来的n=100

int main(void) {
unsigned long long out = fibonacci(100);//不加unsigned就溢出啦，可想而知斐波那契数列的威力巨大
cout < return 0;
}


消耗时间：0.1228s

emmmm~

算你勉强合格吧！

大家要好好吃饭，每天都要开开心心的！