网站推广方案的构成,私人承接做网站多少钱,公司网站搭建流程,同ip网站做排名seo关于求解斐波那契数列#xff0c;这是一道比较经典的题目#xff0c;本文主要是对斐波那契数列求解方法的小结。 首先#xff0c;定义Fibonacci数列如下#xff1a; 方法1#xff1a; 利用递归求解#xff0c;这是最容易写出的算法#xff0c;代码如下#xff1a; #inc… 关于求解斐波那契数列这是一道比较经典的题目本文主要是对斐波那契数列求解方法的小结。 首先定义Fibonacci数列如下 方法1 利用递归求解这是最容易写出的算法代码如下 #includeiostream
using namespace std;long Fibonacci(int n)
{if (n 0)return 0;else if (n 1)return 1;elsereturn Fibonacci(n - 1) Fibonacci(n-2);
}int main()
{int N;cin N;cout Fibonacci(N) endl;return 0;
}该算法的时间复杂度为O(2^N)。为什么呢因为每一次计算Fibonacci(n)时都需要计算Fibonacci(n-1)和Fibonacci(n-2)共2次相当于计算了n个2相乘的次数。 方法2 不用递归利用迭代的方法计算(理论上讲任何递归方法都能利用迭代方法实现)代码如下 #includeiostream
using namespace std;long Fibonacci(int n)
{if (n 0)return 0;else if (n 1)return 1;int num1 0;//表示F(n-2)int num2 1;//表示F(n-1)for(int i 1; i n; i){num2 num1 num2;num1 num2 - num1;}return num2;
}int main()
{int N;cin N;cout Fibonacci(N) endl;return 0;
}迭代算法的时间复杂度为O(N),此处应注意一点这段代码中只用了两个变量num1和num2来分别代替f(n-2)和f(n-1)。实际上也可以用一个数组来代替整个斐波那契数列只不过空间复杂度会增加。 方法3 利用矩阵乘法的原理斐波那契的递推公式可以表示成如下矩阵形式所以 求Fibonacci(n)就可以转化成求矩阵A的n-1次幂问题了。而对于矩阵幂的问题我们有 利用分治的算法思想可以考虑如下求解一个数A的幂。 从它的求解过程来看这种算法的时间复杂度为O(logN),要比前两种效率都要好,尤其是在N比较大的时候更能体现出这种优势。该算法的实现需要事先定义矩阵以及矩阵相关的计算代码如下 #includeiostream
#includestring
using namespace std;//定义2×2矩阵
struct Matrix2by2
{//构造函数Matrix2by2(long m_00,long m_01,long m_10,long m_11):m00(m_00),m01(m_01),m10(m_10),m11(m_11){}//数据成员long m00;long m01;long m10;long m11;
};//定义2×2矩阵的乘法运算
Matrix2by2 MatrixMultiply(const Matrix2by2 matrix1,const Matrix2by2 matrix2)
{Matrix2by2 matrix12(1,1,1,0);matrix12.m00 matrix1.m00 * matrix2.m00 matrix1.m01 * matrix2.m10;matrix12.m01 matrix1.m00 * matrix2.m01 matrix1.m01 * matrix2.m11;matrix12.m10 matrix1.m10 * matrix2.m00 matrix1.m11 * matrix2.m10;matrix12.m11 matrix1.m10 * matrix2.m01 matrix1.m11 * matrix2.m11;return matrix12;}//定义2×2矩阵的幂运算
Matrix2by2 MatrixPower(unsigned int n)
{Matrix2by2 matrix(1,1,1,0);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;
}
//计算Fibnacci的第n项
long Fibonacci(unsigned int n)
{if(n 0)return 0;if(n 1)return 1;Matrix2by2 fibMatrix MatrixPower(n-1);return fibMatrix.m00;}int main()
{unsigned int number;cinnumber;coutFibonacci(number)endl;return 0;
}参考 1.http://blog.csdn.net/liyuanbhu/article/details/51703018 2.http://www.cnblogs.com/python27/archive/2011/11/25/2261980.html转载于:https://www.cnblogs.com/wangkundentisy/p/8502751.html
