C++程序求解斐波那契数列

斐波那契数列是以下整数序列。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

在数学上，斐波那契数列的Fn定义为如下递归关系：

Fn = Fn-1 + Fn-2

并且有以下初始值：

F0 = 0 和 F1 = 1.

C++程序求解斐波那契数列

给定数字n，输出第n个斐波那契数。

示例：

输入：n = 2
输出：1

输入：n = 9
输出：34

编写一个函数 int fib(int n) 返回F n 。例如，如果 n = 0，那么 fib() 应该返回0。如果n = 1，那么它应该返回1。对于n > 1，它应该返回F n-1 + F n-2

对于n = 9
输出：34

下面是获得第n个斐波那契数的不同方法。

方法1（使用递归）

一个简单的直接递归实现数学递推关系的方法如上所述。

// 使用递归的斐波那契数列
#include <bits/stdc++.h>
using namespace std;
  
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
  
int main()
{
    int n = 9;
    cout << fib(n);
    getchar();
    return 0;
}

输出

时间复杂度 : 指数级别，因为每个函数调用两个其他函数。

如果原始递归树被实现，则将是此树，但现在对于n次调用递归函数。

原始递归树

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

用于上面代码的递归的优化树

fib(5)

fib(4)

fib(3)

fib(2)

fib(1)

额外的空间： 如果我们考虑函数调用堆栈大小，则为O（n），否则为O（1）。

方法2（使用动态规划）我们可以通过存储到目前为止计算的斐波那契数来避免方法1中重复的计算。

// C++程序斐波那契数列
//使用动态规划 
#include<bits/stdc++.h>
using namespace std;
  
class GFG{
      
public:
int fib(int n)
{
      
    // 声明一个数组来存储 
    // 斐波那契数。
    // 多申请一个用于处理 
    // n=0的情况
    int f[n + 2]; 
    int i;
  
    // 数列中第0和第1个数为
    f[0] = 0;
    f[1] = 1;
  
    for(i = 2; i <= n; i++)
    {
          
       //将前两个相加
       // 然后存储这个值
       f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
    }
};
  
// 主函数
int main ()
{
    GFG g;
    int n = 9;
      
    cout << g.fib(n);
    return 0;
}

输出

时间复杂度： 对于给定的n是O（n）

辅助空间： O（n）

方法3：(空间优化方法2)

我们可以通过仅存储前两个数字来优化方法2中使用的空间，因为这是我们需要获取系列中下一个Fibonacci数的全部内容。

// 使用空间优化方法的Fibonacci序列
#include<bits/stdc++.h>
using namespace std;
  
int fib(int n)
{
    int a = 0, b = 1, c, i;
    if( n == 0)
        return a;
    for(i = 2; i <= n; i++)
    {
       c = a + b;
       a = b;
       b = c;
    }
    return b;
}
  
// 驱动程序代码
int main()
{
    int n = 9;
      
    cout << fib(n);
    return 0;
}

输出

时间复杂度： O(n)

额外空间： O(1)

方法4：使用矩阵{{1，1}，{1，0}}的幂

这是另一个O(n)的方法，它依赖于这样一个事实：如果我们n次将大小为2 * 2的矩阵M ={{1,1}，{1,0}}相乘（换句话说，计算power(M，n)），那么我们得到第（n + 1）个Fibonacci数作为结果矩阵中的行和列（0, 0）处的元素。

矩阵表示为Fibonacci数提供了以下封闭表达式：

C++程序求解斐波那契数列

#include<bits/stdc++.h>
using namespace std;
  
// Helper function that multiplies 2 
// matrices F and M of size 2*2, and
// puts the multiplication result 
// back to F[][] 
void multiply(int F[2][2], int M[2][2]);
  
// Helper function that calculates F[][] 
// raise to the power n and puts the
// result in F[][]
// Note that this function is designed 
// only for fib() and won't work as 
// general power function 
void power(int F[2][2], int n);
  
int fib(int n)
{
    int F[2][2] = { { 1, 1 }, { 1, 0 } };
      
    if (n == 0)
        return 0;
          
    power(F, n - 1);
      
    return F[0][0];
}
  
void multiply(int F[2][2], int M[2][2])
{
    int x = F[0][0] * M[0][0] + 
            F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + 
            F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + 
            F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] +            F[1][1] * M[1][1];
      
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
  
void power(int F[2][2], int n)
{
    int i;
    int M[2][2] = { { 1, 1 }, { 1, 0 } };
      
    // n - 1次将矩阵乘到{{1,0}，{0，1}}
    for(i = 2; i <= n; i++)
        multiply(F, M);
}
  
// 驱动程序代码
int main()
{
    int n = 9;
      
    cout << " " << fib(n);
      
    return 0;
}

输出

时间复杂度： O(n)

额外空间： O(1)

方法5：（优化方法4）

方法4可以优化为O(Logn)的时间复杂度。我们可以在先前的方法中进行递归乘法，以获取power（M，n）（类似于本文中所做的优化）

// 使用优化方法的 Fibonacci数列 
#include <bits/stdc++.h>
using namespace std;
  
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
  
// 返回第n个Fibonacci数列的函数
int fib(int n)
{
    int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
  
    return F[0][0];
}
  
// 在方法4中优化的power()函数
void power(int F[2][2], int n)
{
    if(n == 0 || n == 1)
       return;
    int M[2][2] = {{1, 1}, {1, 0}};
      
    power(F, n / 2);
    multiply(F, F);
      
    if (n % 2 != 0)
        multiply(F, M);
}
  
void multiply(int F[2][2], int M[2][2])
{
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
      
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
  
// 主函数
int main()
{
    int n = 9;
      
    cout << fib(9);
    getchar();
      
    return 0;
}

输出

时间复杂度: O（logn）

额外空间： 如果考虑函数调用堆栈大小，则为O（logn），否则为O（1）。

第6种方法：（O（Log n）时间）

以下是另一个有趣的递推公式，可以用来在O（Log n）时间内找到n’th Fibonacci数。

如果n是偶数，则k = n / 2：
F(n) = [2*F(k-1) + F(k)]*F(k)

如果n是奇数，则k =（n + 1）/ 2
F（n）= F（k）* F（k）+ F（k-1）* F（k-1）

这个公式是如何工作的？

该公式可以从上述矩阵方程中推导出来。

C++程序求解斐波那契数列

两边都进行行列式运算，我们得到

（-1）n = Fn+1Fn-1 – Fn²

此外，由于对于任何平方矩阵A，AnAm=An+m，
可以得到以下标识（它们是从矩阵乘积的两个不同系数得到的）

FmFn+Fm-1Fn-1=Fm+n-1—————————-(1)

将n=n+1放入方程（1）中，

FmFn+1+Fm-1Fn=Fm+n—————————-(2)

在等式（1）中将m=n，

F2n-1=Fn²+Fn-1²

在等式（2）中放置m=n，

F2n=(Fn-1+Fn+1)Fn=(2Fn-1+Fn)Fn（来源：Wiki）——–

（通过放置Fn + 1 = Fn + Fn-1）

要得到要证明的公式，我们只需要执行以下操作

如果n是偶数，则可以放置k = n / 2
如果n是奇数，则可以放置k =（n + 1）/ 2

下面是上述思路的实现。

// C++程序，用O(Log n)算术操作找到n个斐波那契数
#include <bits/stdc++.h>
using namespace std;
  
const int MAX = 1000;
  
// 创建一个记忆数组
int f[MAX] = {0};
  
// 使用数组f[]返回第n个斐波那契数
int fib(int n)
{
    // 基本情况
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
  
    // 如果已经计算了fib(n)
    if (f[n])
        return f[n];
  
    int k = (n & 1)? (n+1)/2 : n/2;
  
    // 应用上面的公式[注意，当n为奇数时，值n&1为1，否则为0。]
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
           : (2*fib(k-1) + fib(k))*fib(k);
  
    return f[n];
}
  
// 测试上面函数的主函数
int main()
{
    int n = 9;
    printf("%d ", fib(n));
    return 0;
}

输出

时间复杂度: O(Log n)，因为我们在每次递归调用中把问题分成两半。

方法7：(将Binet的公式作为方法）

在这种方法中，我们直接实现斐波那契数列中第n项的公式。

F n = {[(√5 + 1)/2] ^ n} / √5

注意： 上面的公式只针对n<71有效。因为随着n的增加，四舍五入误差会变得显著大。但是，对于n=71，使用floor函数而不是round函数将会得到正确的结果。但是，在n=72之后，这个公式也会失败。

例如：对于n=72，正确结果是498454011879264，但是上面的公式得出498454011879265。

// C++程序，查找第n个斐波那契数
#include<iostream>
#include<cmath>
  
int fib(int n) {
  double phi = (1 + sqrt(5)) / 2;
  return round(pow(phi, n) / sqrt (5));
}
  
// 驱动程序
int main ()
{
  int n = 9;
  std::cout << fib(n) << std::endl;
  return 0;
}

输出

时间复杂度 : O(logn)，这是因为计算phi^n需要logn的时间

辅助空间 : O(1)

方法8：DP（自上而下方法）使用记忆化技术

我们可以通过存储到目前为止计算出来的斐波那契数来避免方法1中重复的工作。我们只需要将所有值存储在一个数组中。

#include <bits/stdc++.h>
using namespace std;
int dp[10];
int fib(int n)
{
    if (n <= 1)
        return n;
  
    // 临时变量，用于存储
    // fib(n-1)和fib(n-2)的值
    int first, second;
  
    if (dp[n - 1] != -1)
        first = dp[n - 1];
    else
        first = fib(n - 1);
  
    if (dp[n - 2] != -1)
        second = dp[n - 2];
    else
        second = fib(n - 2);
  
    // 记忆化
    return dp[n] = first + second;
}
  
// 测试上面函数的主函数
int main()
{
    int n = 9;
  
    memset(dp, -1, sizeof(dp));
  
    cout << fib(n);
    getchar();
    return 0;
  
}