從sicily Fibonacci 問題出發解決矩陣快速冪求解斐波那契額問題

2019-11-06 06:43:32

字體：大中小

來源：轉載

供稿：網友

/*********************************************************************************************************************************/

寫在前面：

一直不敢打代碼，生怕各種WA會暴露我的智商；

但是已經大二了，轉眼就要面臨升學還是工作的神圣選擇；

非常虛，于是開了個博客慢慢回顧一下這些年來學的一些或易或難的算法

最好能寫成一部勵志史詩吧hhhh。

/*********************************************************************************************************************************/

題目描述（Description）

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Given an integer n, your goal is to compute the last Fn mod (10^9 + 7).輸入要求（Input）

The input test file will contain a single line containing n (n ≤ 2^31-1).

There are multiple test cases!

輸出要求（Output）For each test case, PRint the Fn mod (10^9 + 7).樣例Sample Input

Copy sample input to clipboard

     9Sample Output     34提示（hint）  You may need to use "long long".
/*********************************************************************************************************************************/
題意分析：
對下標為n的斐波那契數列元素進行取模；
在這里有幾點注意：
1.遞歸代碼雖然簡潔，但是占用空間過多，容易造成內存泄漏；
2.鑒于n的取值實在是大的突破天際，采用簡單的遞推方法肯定會出現超時；
比較之下，應該采用一種新方法——矩陣快速冪
矩陣快速冪
什么是快速冪？
       快速冪是一種快速求解矩陣高次方的方法，能夠將樸素的O(n)的復雜度降到O(log(n))
  
什么是斐波那契數列
斐波那契數列的定義：An = An-1 + An-2, a0 = 0, a1 = 1;
  斐波那契數列進行矩陣變換
/**********************************************************************************************************************************/
代碼實現：
#include <iostream>using namespace std;#define Maxinum  1000000007struct Matrix{	long long mat[2][2];};Matrix mul(Matrix a, Matrix b){	Matrix res;	for(int i = 0; i < 2; i++)	{		for(int j = 0; j < 2; j++)		{			res.mat[i][j] = 0;			for(int k = 0; k < 2; k++)			{				res.mat[i][j] += a.mat[i][k] * b.mat[k][j];				res.mat[i][j] %= Maxinum;			}					}	}	return res;}Matrix quickpower(Matrix a, Matrix b, long long n){	while(n)	{		if(n & 1) b = mul(b, a);        //按位與操作符，用來判斷是不是 		//if(n % 2 == 1) b = mul(b,a); 		a = mul(a, a);		n >>= 1;		//移位，表示其除以二 			}	return b;}int main(){	Matrix a = {1,1,1,0};	long long n;	while(cin >> n)	{		Matrix b = {1,0,0,1};		if(n == 0) 			cout << 0 << endl;		else 		{			Matrix temp = quickpower(a, b, n - 1);			cout << temp.mat[0][0] << endl;		}	}	return 0;}