题目描述
大家都知道斐波那契数列, 现在要求输入一个整数 n, 请你输出斐波那契数列的第 n 项 (从 0 开始, 第 0 项为 0).
n<=39
解法 1 递归
解题前先简单说明一下斐波那契数列, 指的是这样一个数列: 1,1,2,3,5,8,13,21,34,......, 因数学家列昂纳多. 斐波那契以兔子繁殖为例子而引入, 故又称为兔子数列. 可以表示为 F(n) = F(n-1) + F(n-2). 这道题在不考虑效率的情况下, 最直接的解法是用递归, 代码如下
实现代码
- public int Fibonacci(int n)
- {
- if (n == 0)
- {
- return 0;
- }
- else if (n == 1 || n == 2)
- {
- return 1;
- }else
- {
- return Fibonacci(n - 1) + Fibonacci(n - 2);
- }
- }
解法 2 动态规划
解法 1 使用递归虽然很直观, 简单, 但是效率太低. 在 n <= 39 的情况下, 运行时间为 1277ms, 究其原因还是算法中存在大量重复运算. 以求解斐波那契数列第 6 项的过程来说明, 如下图, 在求解 F6 的过程中, F4 会被重复计算 2 次, F3 会被重复计算 3 次, 这都导致了多余的消耗, 且随着 n 越来越大冗余计算的增长是爆炸性的.
递归的思想是自顶向下的, Fn 的求解基于 Fn-1 和 Fn-2,Fn-1 的求解又基于 Fn-2 和 Fn-3 等等依次类推. 而现在我们可以反过来, 自底向上, 在已知 F1 = 1,F2 = 1 的情况下求解 F3, 再利用 F3 和 F2 求解 F4 直到求出 Fn. 即不使用递归, 使用循环迭代的方式. 相比于解法 1, 优化后的算法运行时间只有 39ms.
实现代码
- public int FibonacciOptimize(int n)
- {
- if (n == 0)
- {
- return 0;
- }
- int fibl = 1, fibn = 1;
- for(int i = 2; i <n; i++)
- {
- fibn = fibl + fibn;
- fibl = fibn - fibl;
- }
- return fibn;
- }
- // 或者是更简洁一点的写法
- public int FibonacciOptimize2(int n)
- {
- int f = 0, g = 1;
- while(n --> 0)
- {
- g += f;
- f = g - f;
- }
- return f;
- }
动态规划
上面不使用递归, 而使用循环的方式, 我们可以给它起一个高大上的名字, 动态规划. 什么叫做动态规划呢, 其实和它本身字面上的意思并没有太大关系.
对于递归算法, 编译器常常都只能做很低效的处理, 递归算法如此慢的原因在于, 编译器模拟的递归不能保留预先算出来的值, 对已经求解过的子问题仍在递归的进行调用, 导致了大量的冗余计算, 比如上面的斐波那契递归算法. 当我们想要改善这种情况时, 可以将递归算法改成非递归算法, 让后者把那些子问题的答案系统地记录下来, 利用这种方法的一种技巧就叫做动态规划. 比如上面的代码, 我们都是用了两个变量把上一次的计算结果记录了下来, 避免了重复计算.
可能上面的算法对动态规划的体现并不是那么直观, 可以看下面这段代码. 我们用一个数组, 将每次求解出来的 Fn 都记录了下来, 当一个子问题被求解过以后, 下一次就可以直接通过索引访问数组得到, 而避免了再次求解.
- public int FibonacciOptimize3(int n)
- {
- if (n == 0)
- {
- return 0;
- }
- int[] array = new int[n + 1];
- array[0] = 1;
- array[1] = 1;
- for(int i = 2; i <n; i++)
- {
- array[i] = array[i - 1] + array[i - 2];
- }
- return array[n - 1];
- }
解法 3
除了使用递归和动态规划外, 我们还可以使用矩阵来求解斐波那契数列. 对于矩阵这里不再进行扩展, 只介绍本算法会用到的基本概念. 如下所示的 M 就是一个 2x2 的矩阵, 2 行 2 列.
\[M = \left[ \begin{matrix} 1 & 2\\ 3 & 4\\ \end{matrix} \right] \]
矩阵和矩阵之间可以相乘, 一个 rxn 的矩阵 M 和一个 nxc 的矩阵 N 相乘, 它们的结果 MN 将会是一个 rxc 大小的矩阵. 注意如果两个矩阵的行列不满足上面的规定, 则这两个矩阵就不能相乘. 怎样计算新的矩阵 MN 呢, 可以用一个简单的方式描述: 对于每个元素 c~ij~, 我们找到 M 中的第 i 行和 N 中的第 j 列, 然后把它们对应元素相乘后再加起来, 这个和就是 c~ij~, 对于有矩阵 M,N 如下
\[M = \left[ \begin{matrix} a & b\\ c & d\\ \end{matrix} \right] N = \left[ \begin{matrix} e & f\\ g & i\\ \end{matrix} \right] \]
则 MN 为
\[MN = \left[ \begin{matrix} ae + bg & af + bi\\ ce + dg & cf + di\\ \end{matrix} \right] \]
那么斐波那契数列和矩阵有什么关系呢?
我们已知斐波那契第 n 项, Fn = F(n - 1) + F(n - 2), 可以将它们转换成如下所示的矩阵形式
\[ \left[ \begin{matrix} F(n)\\ F(n-1)\\ \end{matrix} \right] = \left[ \begin{matrix} F(n-1) + F(n-2)\\ F(n-1)\\ \end{matrix} \right]= \left[ \begin{matrix} F(n-1) * 1 + F(n-2) * 1\\ F(n-1) * 1 + F(n-2) * 0\\ \end{matrix} \right]= \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right] \left[ \begin{matrix} F(n-1)\\ F(n-2)\\ \end{matrix} \right] \]
即
- \[ \left[ \begin{
- matrix
- } F(n)\\ F(n-1)\\ \end{
- matrix
- } \right] = \left[ \begin{
- matrix
- } 1 & 1\\ 1 & 0\\ \end{
- matrix
- } \right] \left[ \begin{
- matrix
- } F(n-1)\\ F(n-2)\\ \end{
- matrix
- } \right] \]
- \[ \left[ \begin{
- matrix
- } F(n-1)\\ F(n-2)\\ \end{
- matrix
- } \right] = \left[ \begin{
- matrix
- } 1 & 1\\ 1 & 0\\ \end{
- matrix
- } \right] \left[ \begin{
- matrix
- } F(n-2)\\ F(n-3)\\ \end{
- matrix
- } \right] \]
- \[ \left[ \begin{
- matrix
- } F(n)\\ F(n-1)\\ \end{
- matrix
- } \right] = \left[ \begin{
- matrix
- } 1 & 1\\ 1 & 0\\ \end{
- matrix
- } \right] ^2 \left[ \begin{
- matrix
- } F(n-2)\\ F(n-3)\\ \end{
- matrix
- } \right] \]
以此类推
\[ \left[ \begin{matrix} F(n)\\ F(n-1)\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right] ^{n-1} \left[ \begin{matrix} F(1)\\ F(0)\\ \end{matrix} \right] \]
所以要求斐波那契的第 n 项, 我们只需要求得 F1 和 F0 构成的矩阵与特定矩阵的 n-1 次方相乘后的矩阵, 然后取该矩阵的第一行第一列的元素值就是 Fn
现在引入了一个新的问题, 怎样求特定矩阵的 n-1 次方, 即矩阵的快速幂
矩阵的快速幂
在了解矩阵的快速幂之前, 我们先看普通整数的快速幂
求解整数 m 的 n 次方, 一般是 m^n^ = m * m * m ....., 连乘 n 次, 算法复杂度是 O(n), 这样的算法效率太低, 我们可以通过减少相乘的次数来提高算法效率, 即快速幂
对于 n 我们可以用二进制表示, 以 14 为例, 14 = 1110
- \[ m^{
- 14
- } = m^{
- 1110
- } = m^{
- 2^{
- 3
- } * 1 + 2^{
- 2
- } * 1 + 2^{
- 1
- } * 1 + 2^{
- 0
- } * 1
- } = m^{
- 2^{
- 3
- } * 1
- } * m^{
- 2^{
- 2
- } * 1
- } * m^{
- 2^{
- 1
- } * 1
- } * m^{
- 2^{
- 0
- } * 0
- } \]
- \[ = m^{
- 8
- } * m^{
- 4
- } * m^{
- 2
- } * m^{
- 0
- } = m^{
- 8
- } * m^{
- 4
- } * m^{
- 2
- } * 1 \]
可以发现这样的规律, 指数 n 的二进制从低位到高位依次对应底数 m 的 1 次方, 2 次方, 4 次方, 8 次方..., 当该二进制位是 1 的时候, 则乘以底数对应的次方数, 如果该二进制位是 0, 则表示乘以 1. 使用快速幂后, 原本需要 14 次连乘, 现在只需要 4 次连乘.
那么怎样得到一个整数的二进制位呢, 又怎样判断该二进制位是 0 还是 1 呢
可以使用与运算和右移运算, 例如对于 14 = 1110
和 1 按位与得到 0, 即第一个二进制位是 0
1110 右移一位, 得到 0111, 和 1 按位与得到 1, 即第二个二进制位是 1
0111 右移一位, 得到 0011, 和 1 按位与得到 1, 即第三个二进制位是 1
0011 右移一位, 得到 0001, 和 1 按位与得到 1, 即第四个二进制位是 1
0001 右移一位, 得到 0000, 等于 0 则, 算法结束
对应的代码如下
- public int pow(int m, int n)
- {
- int ret = 1;
- while(n> 0)
- {
- if ((n & 1)> 0)
- {
- ret = ret * m;
- }
- m *= m;
- n>>= 1;
- }
- return ret;
- }
对应矩阵的快速幂就是
- // 简单实现了 2*2 矩阵的乘法
- public int[,] matrixMul(int[,] m, int[,] n)
- {
- int[,] ret = {
- { m[0,0] * n[0,0] + m[0,1] * n[1,0], m[0,0] * n[0,1] + m[0,1] * n[1,1]} ,
- { m[1,0] * n[0,0] + m[1,1] * n[1,0], m[1,0] * n[0,1] + m[1,1] * n[1,1]}
- };
- return ret;
- }
- // 矩阵的快速幂
- public int[,] matrixPow(int[,] m, int n)
- {
- // 单位矩阵, 作用相当于整数乘法中的 1
- int[,] ret = { { 1, 0 }, { 0, 1 } };
- while(n> 0)
- {
- if ((n & 1)> 0)
- {
- ret = matrixMul(m, ret);
- }
- m = matrixMul(m, m);
- n>>= 1;
- }
- return ret;
- }
实现代码
在已经知道矩阵的快速幂之后, 求解 Fn 就可以直接代入公式
\[ \left[ \begin{matrix} F(n)\\ F(n-1)\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right] ^{n-1} \left[ \begin{matrix} F(1)\\ F(0)\\ \end{matrix} \right] \]
实现代码如下
- public int FibonacciOptimize4(int n)
- {
- if (n == 0)
- {
- return 0;
- }
- int[,] matrix = { { 1, 1 }, { 1, 0 } };
- // 这里的 F1 和 F0 矩阵多加了一列 0,0, 不会影响最终结果, 是因为 matrixMul 只实现了 2*2 矩阵的乘法
- int[,] unit = { { 1, 0 }, { 0, 0 } };
- // 调用前面代码的矩阵乘法和矩阵快速幂
- int[,] ret = matrixMul(matrixPow(matrix, n - 1), unit);
- return ret[0, 0];
- }
来源: https://www.cnblogs.com/iwiniwin/p/10798884.html