从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;}