斐波那契数列
斐波那契数列的三种求法：
第一种：暴力求解
#include<iostream>
using namespace std;
long Fibonacci(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
long pre = 0;
long lat = 1;
long fib = 0;
intcnt = 1;
while(cnt < n)
{
fib = pre + lat;
pre = lat;
lat = fib;
++cnt;
}
return fib;
}
int main()
{
cout << "请输入数列的长度:";
intn;
cin>> n;
cout << Fibonacci(n) << endl;
return 0;
}
（2）第二种是递归法：
F（n） = 0 n=0
1 n=1
F(n-1) + F(n-2) n>=2
#include<iostream>
using namespace std;
long Fibonacci(int n)
{
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
int main()
{
cout << "请输入数列长度:";
intn = 0;
cin>> n ;
cout << Fibonacci(n) << endl;
return 0;
}
（3）第三种是最高效的O（nlgn）的算法
看到这么一个a^n的式子，我们应该都很熟悉，可以直接用分治的方法来提高效率！
具体的我们可以用数学归纳法证明（此处省略证明，直接上代码）
#include<iostream>
#include<string>
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(constMatrix2by2& 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(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
Matrix2by2 fibMatrix = MatrixPower(n-1);
return fibMatrix.m00;
}
int main()
{
cout << "请输入数列的长度:" << endl;
intn;
cin>> n;
cout << Fibonacci(n) << endl;
return 0;
}
转载出处http://www.cnblogs.com/python27/
