基础算法题——斐波那契（快速求幂、斐波那契特性、矩阵）

浅浅的花香味﹌ 2023-07-07 03:39 32阅读 0赞

# 基础算法题——斐波那契 #

## 做题心得 ##

这道算法题花了我几乎一天的时间才弄懂，不得不说我还是太菜了…  
该算法题主要考查了对斐波那契数列的理解、矩阵与斐波那契结合、快速求幂。在看了数篇博客后我才慢慢对矩阵、快速求幂有所了解，由于是初步接触这类题型，如果有不正确的地方，欢迎大家来交流讨论。

## 斐波那契题目 ##

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
[牛客网题目链接][Link 1]

## 题目分析 ##

题目很短，乍一看很简单，不就是将每一个斐波那契数列算出来然后再把每一项的平方和累加起来，如果遇到了过大的数就求余，然后将答案再求余防止过大，这不就是简简单单的一道送分题嘛。但是我们仔细观察就会发现n的取值范围居然是1<=n<=1e18，这也太大了。如果n=1e18，按我们算法复杂度O（n），这我们就要让程序将1~1e18项的斐波那契数列全部相加，很显然肯定会超时！！那我们还能用那种普通思维去对待这道看似简单的题目吗？不行，我们需要学习新的东西，才能够解决这道题给我们留的坑。

### 斐波那契数列 ###

斐波那契数列又称黄金分割数列、兔子数列。  
指的是这样一个数列：1、1、2、3、5、8、13、21…在数学上，斐波那契数列以如下被递推的方法定义：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)其中的n>=3。  
为了能够更简便地将前n项平方和计算出结果，我们将引入一种全新的计算方式（当然这种全新是对我来说）。  
题目中我们要求1~n项斐波那契数列的平方和sum。  
**sum=a12\+a22 \+ …+an2=an\*an+1**  
具体证明请参照大佬讲解：[斐波那契数列平方和计算公式][Link 2]

### 快速求幂 ###

什么是快速求幂？  
21000000对1e9+7取余，我们会如何计算呢？用一个循环将答案算出？这种方案效率太低，这时我们可以用快速求幂的方法将结果算出。  
如果对该算法不理解的同学，我力荐他点击下面那篇博客，博客中对快速求幂算法将得清晰无比！把昨天在泥潭中的我拉上了岸，在此感谢博主的精彩解析！博客中我认为最为精华的一句话：**最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。**  
[快速幂算法][Link 3]

//若看完上面的博客，对快速求幂有了一定的理解
    //你可以尝试下能否看懂这篇代码
    //如果可以说明你已经基本理解了何为快速求幂
    #include<stdio.h>
    long long quick(long long base, long long power); 
    const int MOD=1e9+7;
    int main()
    { 
    	long long base, power;
    	printf("求x为底数，y为指数的值对1e9+7取余：\nx y:");
    	scanf("%lld%lld", &base, &power);
    	printf("%lld", quick(base, power));
    	
    	return 0;
    }
    
    long long quick(long long base, long long power)
    { 
    	long long result=1;
    	while(power)
    	{ 
    		if(power&1)//只有奇数才乘以底数
    			result=result*base%MOD;
    		base=base*base%MOD;
    		power=power>>1;
    	}
    	if(base==0){ 
    		result=0;
    	}
    	return result%MOD;
    }

若看不懂上面的代码，说明对快速求幂理解不够，需要再点击上方“快速求幂算法”链接加深理解。

### 矩阵与斐波那契数列结合 ###

矩阵怎么就和斐波那契数列扯上了关系？这个问题昨天一直在我脑海里“挥之不去”，终于我又遇到了一篇微信上的文章，它讲解了矩阵与斐波那契数列的关系。  
![关系][20200220162309631.png]  
简简单单一张图，将矩阵与斐波那契数列完美地结合在了一起！  
能够了解到这种联系，说实在的，心里莫名激动！  
[矩阵与斐波那契数列结合][Link 4]

## 代码讲解 ##

如果你已经理解了上面的全部知识点，也许你也不一定能将其中联系起来完成这道算法题。（我就是这样，也许是我太菜了吧…）  
于是我又看了好多其他人的代码，发现他们喜欢用结构、映射和一些我不常用甚至不理解的表达方式（所以说看别人写的代码真的很难受）。最后我就在矩阵求斐波那契数列的代码上进行修改加入了快速求幂的步骤，写出来“通俗易懂”的代码，相信我这个真的比很多人写的要简单，就是一开始让人摸不着头脑。  
千万不要看着下面整体代码很长很复杂的样子，其实我为了让代码更加让人读懂，加入了很多注释，删去注释也就不到50行的代码。

*整体代码*：

//第一段 整体代码
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MOD=1e9+7;
    
    struct mat
    { 
    	ll a[2][2];
    };
    
    mat mat_mul(mat x,mat y)//计算两矩阵相乘：x * y 
    { 
    	mat res;
    	memset(res.a,0,sizeof(res.a));
    	//将res.a矩阵全部元素设置为0 
    	//将二维数组置零可以换一种写法
    	//for(int i=0; i<2; i++)
    	//for(int j=0; j<2; j++)
    	// res.a[i][j]=0; 
    	
    	//每次创建一个新矩阵，储存第n+1、n、n-1项斐波那契数列 
    	for(int i=0;i<2;i++)
    		for(int j=0;j<2;j++)
    			for(int k=0;k<2;k++)
    			res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
    	//斐波那契矩阵 * c^n矩阵 
    	// res.a= n+1 n 
    	// n n-1
    	return res;	 
    }
    
    ll mat_pow(long long n)
    { 
    	mat c,res;
    	c.a[0][0]=c.a[0][1]=c.a[1][0]=1;	
    	c.a[1][1]=0;
    	//c矩阵：1 1 c^2矩阵: 2 1
    	// 1 0 1 0 
    	memset(res.a,0,sizeof(res.a));
    	
    	for(int i=0;i<2;i++) //得到矩阵(A) 1 0
    	res.a[i][i]=1;		 // 0 1
    	 
    	//主要实现 1 1 ^ n * 1 0 = 1 1 ^ (n-1) * f(2) f(1)
    	// 1 0 0 1 1 0 f(1) f(0) 
    	// [ 构造阶段 ] 
    
    	// ... 1 1 ^ f(n) f(n-1) = f(n+1) f(n) 
    	// 1 0 f(n-1) f(n-2) f(n) f(n-1)
    	
    	//采用快速求幂：优化效率 
    	//幂结果实际上就是在变化过程中所有当指数为奇数时
    	//底数矩阵(c)的乘积
    	while(n)			 //循环[log2n]次 ,n在这里是指数 
    	{ 					 //[x]：取x的整数
    		if(n&1) 			//如果n为奇数
    		res=mat_mul(res,c);	//将矩阵乘以 c 
    		
    		c=mat_mul(c,c);	//c一直在变化 最终：c^log2n
    						//为什么要一直乘以c呢？
    						//因为n一直在变化，底数矩阵指数是不同的 
    									 
    		n=n>>1;			
    		//退一位（n/=2） 符合计算机语言 
    		//二进制法
    		//n=3 二进制：11 
    		//res.a=c * A + c^2 * A;
    		//n=100 二进制：1100100 
    		//res.a= c^7 * (c^6 * (c^3 * A))
    		//若想验证该想法，可以利用第二段验证代码
    	}
    //用来验证n=100的想法，记录res.a矩阵每一项的值，该矩阵记为RES
    // cout << res.a[0][0] << " " << res.a[0][1] << endl;
    // cout << res.a[1][0] << " " << res.a[1][1] << endl <<endl;
    	return (res.a[0][1]*res.a[0][0])%MOD;
    }
    
    int main()
    { 
    	ll n;
    	
    	cin >> n;
    	cout << mat_pow(n);
    	
    	return 0;
    }

*验证代码*：（验证n=100的情况）  
n=100 二进制：1100100  
res.a= c^7 \* (c^6 \* (c^3 \* A))

//第二段 验证代码
    #include<bits/stdc++.h>
    #include<time.h>
    using namespace std;
    typedef long long ll;
    const int MOD=1000000007;
    
    struct mat
    { 
    	ll a[2][2];
    };
    
    mat mat_mul(mat x,mat y)//计算两矩阵相乘：x * y 
    { 
    	mat res;
    	memset(res.a,0,sizeof(res.a));
    	for(int i=0;i<2;i++)
    		for(int j=0;j<2;j++)
    			for(int k=0;k<2;k++)
    			res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
    
    	return res;	 
    }
    
    mat mat_pow(long long n)//c^(n+1)最终得到的矩阵
    { 
    	mat c,res;
    	c.a[0][0]=c.a[0][1]=c.a[1][0]=1;
    	c.a[1][1]=0;					
    	memset(res.a,0,sizeof(res.a));
    		 
    	while(n)			
    	{ 		
    		c=mat_mul(c,c);	
    		n--;
    	}
    	return c;
    }
    
    int main()
    { 
    	ll n;
    	mat a, c3, c6, c7, A;
    	
    // cin >> n;
    //计算出c3矩阵、c6矩阵、c7矩阵每一项的值
    // a=mat_pow(n-1); 
    /*记录c3、c6、c7矩阵每一项的值 cout << a.a[0][0] << " " << a.a[0][1] << endl; cout << a.a[1][0] << " " << a.a[1][1] << endl <<endl; cout << c3.a[0][0] << " " << c3.a[0][1] << endl; cout << c3.a[1][0] << " " << c3.a[1][1] << endl << endl; cout << c6.a[0][0] << " " << c6.a[0][1] << endl; cout << c6.a[1][0] << " " << c6.a[1][1] << endl << endl; cout << c7.a[0][0] << " " << c7.a[0][1] << endl; cout << c7.a[1][0] << " " << c7.a[1][1] << endl << endl;*/
    	
    	A.a[0][0]=A.a[1][1]=1;
    	A.a[0][1]=A.a[1][0]=0;
    	c3.a[0][0]=5;c3.a[0][1]=c3.a[1][0]=3;c3.a[1][1]=2;
    	c6.a[0][0]=3524578;c6.a[0][1]=c6.a[1][0]=2178309;
    	c6.a[1][1]=1346269;
    	c7.a[0][0]=680057396;c7.a[0][1]=c7.a[1][0]=209783453;
    	c7.a[1][1]=470273943;
    	a = mat_mul(c7,mat_mul(c6,mat_mul(c3,A)));
    	cout << a.a[0][0] << " " << a.a[0][1] << endl;
    	cout << a.a[1][0] << " " << a.a[1][1] << endl <<endl;
    	//将a.a矩阵每一项的值与RES相比较，可验证二进制法
    	return 0;
    }

## 总结 ##

这道算法题花了我大量精力，昨天查资料到凌晨1点半才有“浮出水面”的感觉。希望这些讲解能有助于我们更好地理解矩阵、快速求幂、斐波那契数列的特性。  
感谢互联网信息给我自学带来了便利，感谢每个知识点对应“干货文”的作者们，他们成为我指路的老师。  
**学习算法，还是要“迎难而上”，切勿“避重就轻** 共勉！  
如果对本题有其他看法的话，欢迎老铁给小郑留言。

### 如果觉得该文章对你有用的话，可以给我一个大大的赞喔！！ ###

#### 老铁的关注是鼓励我写博客的最大动力~ ####

![被代码吃了][20200223150137342.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200220151303608.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[Link 1]: https://ac.nowcoder.com/acm/contest/3282/A
[Link 2]: https://blog.csdn.net/lanchunhui/article/details/51840616
[Link 3]: https://blog.csdn.net/qq_19782019/article/details/85621386?utm_source=distribute.pc_relevant.none-task
[20200220162309631.png]: https://img-blog.csdnimg.cn/20200220162309631.png
[Link 4]: https://mp.weixin.qq.com/s?src=11&timestamp=1582167705&ver=2169&signature=pvtruLeCMj*qttm4rzIHSnYB90J0H6LbDJjL94oFlFdS3xRLyNcL0UgLo1JvnUZUrKlWkjDBRYZv8JLIY7YEFxO0ZQiLiLWq0mYKOtPoKv6VyQsae2Ht-79JvIRXxUph&new=1
[20200223150137342.png]: https://img-blog.csdnimg.cn/20200223150137342.png