@chawuciren
2018-11-15T15:28:17.000000Z
字数 740
阅读 680
未分类
失败的
#include<stdio.h>
#include<stdlib.h>
void multiplication(int a[2][2],int b[2][2]);//计算两个矩阵的乘积
void power(int a[2][2],int n);//计算矩阵的次幂
int Fibonacci(int n);
int main(){
int n;
scanf("%d",&n);
n=Fibonacci(n);
printf("%d",n);
return 0;
}
void multiplication(int a[2][2],int b[2][2]){
int c[2][2];
for(int i=0;i<2;i++){ // 两个矩阵相乘
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
c[i][j]=a[i][k]*b[k][j];
}
}
}
a=c;
}
void power(int a[2][2],int n){
int b=n;
int in[2][2]={//矩阵
{1,1},
{1,0}
};
do{
multiplication(a,a);//偶数
n/=2;
}while(n!=1);
if(b&1){//考虑奇数
multiplication(a,in);
}
return;
}
int Fibonacci(int n){
int a[2][2]={//矩阵
{1,1},
{1,0}
};
int i[2]={1,0};//第一对数
int res[2]={0};
power(a,n);
res[0]=i[0]*a[0][0]+i[1]*a[0][1];//矩阵乘法
res[1]=i[0]*a[1][0]+i[1]*a[1][1];
i[0]=res[0];
i[1]=res[1];
return i[1];
}
在此输入正文