分治 斐波那契矩阵快速幂

斐波那契数列通过矩阵快速幂递推关系如下:

斐波那契数列
在这里插入图片描述
不理解可以计算一遍,验证其正确性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;
//定义矩阵结构体,同时定义两个全局变量
struct matrix{
int m[2][2];
}ans,base;
//矩阵的乘法
matrix multi(matrix a,matrix b){
matrix tmp;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
tmp.m[i][j]=0;
for(int k=0;k<2;k++)
tmp.m[i][j] += a.m[i][k] * b.m[k][j];
}
return tmp;
}
int matrix_pow(int n){
// 1 1
// 1 0
// 基矩阵
base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
base.m[1][1] = 0;
ans.m[0][0] = ans.m[1][1] = 1;
ans.m[0][1] = ans.m[1][0] = 0;
while(n){
if(n&1){
ans = multi(ans,base);
}
base = multi(base,base);
n >>= 1;
}
return ans.m[1][0];
}
int main(){
int n;
while(cin>>n){
cout<<"第"<<n<<"个斐波那契数列的值为:"<<matrix_pow(n)<<"\n";
}
return 0;
}

代码正确性验证如下:
在这里插入图片描述


码字不易,觉得写的可以还请麻烦关注一下