极客教程C++程序 求解斐波那契数列
斐波那契数列是以下整数序列。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
在数学上，斐波那契数列的Fn定义为如下递归关系：
Fn = Fn-1 + Fn-2
并且有以下初始值：
F0 = 0 和 F1 = 1.
给定数字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;
}
输出
34
时间复杂度 : 指数级别，因为每个函数调用两个其他函数。
如果原始递归树被实现，则将是此树，但现在对于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;
}
输出
34
时间复杂度： 对于给定的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;
}
输出
34
时间复杂度： 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数提供了以下封闭表达式：
#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;
}
输出
34
时间复杂度： 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;
}
输出
34
时间复杂度: 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）
这个公式是如何工作的？
该公式可以从上述矩阵方程中推导出来。
两边都进行行列式运算，我们得到
（-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;
}
输出
34
时间复杂度: 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;
}
输出
34
时间复杂度 : 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;
}
输出
34