斐波那契数列重写

未分类

• 实现
• 分析比较时间复杂度
  通过矩阵乘法实现求斐波那契的第n项

#include<stdio.h>
#include<stdlib.h>
int matrix(int n);
int main(){
    int n=0;
    while(1){
        printf("Input n:");
        scanf("%d",&n);
        if(n==0)
            break;
        n=matrix(n);
        printf("%d\n",n);
    }
    return 0;
}
int matrix(int n){
    int a[2][2]={//矩阵
                 {1,1},
                 {1,0}
                      };
    int i[2]={1,0};//第一对数
    int res[2]={0};
    for(int j=0;j<n;j++){
        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];
}

在此输入正文