求斐波拉契数列的第n项
写一个函数，输入n，求斐波拉契数列的第n项，斐波拉契数列的定义如下：
一般解法
long long Fibonacci(unsigned int n)
{
if (n<=0)
return 0;
if (n==1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
这是我们常用的递归函数，但是上述递归的解法存在很严重的效率问题
分析
我们以求解f(10)为例来分析递归的求解过程。想求得f(10)，需要先求得f(9)和f(8)，想求得f(9)，需要先求得f(8)和f(7)。。。我们可以用树形结构来表示这种依赖关系，如下图
可以发现这棵树有很多节点是重复的，而且重复的节点数会随着n的增大而急剧增加，这意味着计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。
实用解法
上述代码之所以慢，是因为重复的计算太多，我们只要想办法避免重复计算就好。比如，我们可以把已经得到的数列中间项保存起来，在下次需要的时候我们先查找一下，如果前面已经计算过就不再重复计算了。
更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)。。。以此类推就可以算出第n项。这种思路的时间复杂度为O(n)，实现如下：
long long Fibonacci(unsigned int n)
{
int result[2] = {0,1};
if (n<2)
return result[n];
long long fibNMinusOne = 0;
long long fibNMinusTwo = 1;
long long fibN = 0;
for (unsigned int i = 2; i <= n; i++) {
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusOne = fibNMinusTwo;
fibNMinusTwo = fibN;
}
return fibN;
}
使用矩阵
先看一个数学公式
有了这个公式，我们只需要求得矩阵的n-1次方
就可以得f(n)。现在的问题转换为如何求矩阵
乘方。如果简单地从0开始循环，n次方将需要n次运算，并不比前面的方法要快。
但我们可以考虑乘方的如下性质：
由公司可知，要求得n次方，我们先求得n/2次方，再把n/2的结果平方一下即可，这可以利用递归实现
完整的实现
#include <cassert>
struct Matrix2By2
{
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)
{
assert(n > 0);
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;
}
long long Fibonacci(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
return PowerNMinus2.m_00;
}
解法比较
用不同的方法求解斐波拉契数列的时间效率大不相同，第一种基于递归的解法，虽然直接但时间效率很低，在实际的软件开发中不会用这种方法。
第二种方法把递归的算法用循环实现，极大地提高了时间效率。
第三种方法把求斐波那契数列转换成求矩阵的乘方，是一种很有创意的算法。虽然我们可以用O(logn)求的矩阵的n次方，但由于隐含的时间常熟较大，很少会有软件采用这种算法。
相关问题
青蛙跳台阶
一只青蛙一次可以跳上一级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析
首先我们考虑最简单的情况。如果只是1级台阶，那显示只有一种条法。如果有2级台阶，那就有两种条法；一种是分两次跳，每次跳1级；另一种就是一次跳2级。
我们把n级台阶时的跳法看成n的函数f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次跳一级，此时跳法数目等于后面剩下的n-1级台阶跳法的数目，即f(n-1)，二是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)，其实就是斐波拉契数列，如下面表达式所示
递归实现
long long Fibonacci(unsigned int n)
{
if (n<=0)
return 0;
if (n==1)
return 1;
if (n==2)
return 2;
return Fibonacci(n-1) + Fibonacci(n-2);
}
循环实现
long long Fibonacci(unsigned int n)
{
if (n<0)
return 0;
int result[3] = {0,1,2};
if (n<3)
return result[n];
long long fibNMinusOne = 1;
long long fibNMinusTwo = 2;
long long fibN = 0;
for (unsigned int i = 3; i <= n; i++) {
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusOne = fibNMinusTwo;
fibNMinusTwo = fibN;
}
return fibN;
}
矩形覆盖问题
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。问用8个2x1的小矩阵无重叠地覆盖一个2x8的大矩阵，共有多少种方法？
分析：
我们将2x8的覆盖方法记为f(8)。用第一个小矩形覆盖大矩形最左边的时候，有两种选择：竖着放置或者横着放置。
竖着放置的时候，右边还剩下2x7的区域，记为f(7)；
横着放置的时候，左上角放置一个，则对应的左下角必须还有一个小矩阵，则右边还剩下2x6的区域，记为f(6)；
因此，f(8)=f(7)+f(6)，可以看出，这仍然是斐波那契数列。
long long Fibonacci(unsigned int n)
{
if (n<=0)
return 0;
if (n==1)
return 1;
if (n==2)
return 2;
return Fibonacci(n-1) + Fibonacci(n-2);
}
参考
《剑指offer》
