第十九题（最快的方法求Fibonacci数列）

本文主要是介绍第十九题（最快的方法求Fibonacci数列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：定义Fibonacci 数列如下：
        /          0                      n=0
f(n)=            1                      n=1
        \    f(n-1)+f(n-2)          n=2

输入n，用最快的方法求该数列的第n 项。

1.采用递归求解，函数的调用过程中，每个函数都都分裂成两个函数，计算的结果没有保存，出现了大量重复计算，算法复杂度O(2^n)

2.采用从下往上的循环结构，时间复杂度O(n)

3.采用矩阵求解，数列中的第n项是矩阵

11

10

n-1次方后所得矩阵的最左上角元素。

因此可以通过矩阵的乘方求解，为了追求更优的时间效率，不采用普通的循环n次乘方的方法，而是采用分治的思想，把n次方换成n/2的平方，以此类推，最终可以达到log(n)的复杂度。

代码：

#include<iostream>
using namespace std;
namespace MS100P_19
{//采用递归的方法，复杂度O(2^n)int Fibonacci_Recursive(int n){if (n == 0)	return 0;if (n == 1)	return 1;else  return Fibonacci_Recursive(n - 1) + Fibonacci_Recursive(n - 2);}//非递归1，时间复杂度 O(n)int Fibonacci_1(int n){long smaller = 0;long bigger = 1;long sum=0;if (n == 0)	return 0;if (n == 1)	return 1;for (int i = 2; i <=n; i++){sum = smaller + bigger;smaller = bigger;bigger = sum;}return bigger;}//非递归，时间复杂度O(logN)struct matrix{long long m00, m01;long long m10, m11;matrix(long long parM00, long long parM01, long long parM10, long long parM11)\:m00(parM00), m01(parM01), m10(parM10), m11(parM11){}matrix() :m00(1), m01(1), m10(1), m11(0){}};matrix matrixMultiply(const matrix& mtx1, const matrix& mtx2){return matrix(mtx1.m00*mtx2.m00 + mtx1.m01*mtx2.m10, mtx1.m00*mtx2.m01 + mtx1.m01*mtx2.m11, \mtx1.m10*mtx2.m00 + mtx1.m11*mtx2.m10, mtx1.m10*mtx2.m01 + mtx1.m11*mtx2.m11);}matrix matrixPower(int power)		//n为指数{matrix temp;if (power == 1)	return temp;if (power % 2 == 0){temp = matrixPower(power / 2);return matrixMultiply(temp, temp);}else{temp = matrixPower(power / 2);temp = matrixMultiply(temp, temp);return matrixMultiply(temp,matrix());}}long long Fibonacci_2(int n){if (n == 0)	return 0;if (n == 1)	return 1;else return matrixPower(n - 1).m00;}void test(){cout << Fibonacci_Recursive(1) << endl;cout << Fibonacci_1(1) << endl;cout << Fibonacci_2(1) << endl;cout << Fibonacci_Recursive(10) << endl;cout << Fibonacci_1(10) << endl;cout << Fibonacci_2(10) << endl;}
}int _tmain(int argc, _TCHAR* argv[])
{MS100P_19::test();return 0;
}

这篇关于第十九题（最快的方法求Fibonacci数列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---