分治法求矩阵的次幂

未分类

失败的

#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];
}

在此输入正文