求斐波拉契数列的第n项
写一个函数,输入n,求斐波拉契数列的第n项,斐波拉契数列的定义如下:
4010043-81a3f4f218d43009.png一般解法
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)。。。我们可以用树形结构来表示这种依赖关系,如下图
2.png可以发现这棵树有很多节点是重复的,而且重复的节点数会随着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;
}
使用矩阵
先看一个数学公式
799b1417445527.jpg有了这个公式,我们只需要求得矩阵的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),其实就是斐波拉契数列,如下面表达式所示
20160924125857556.png递归实现
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的大矩阵,共有多少种方法?
1.jpg分析:
我们将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》
网友评论