[关闭]
@chawuciren 2018-11-15T15:28:17.000000Z 字数 740 阅读 564

分治法求矩阵的次幂

未分类


失败的

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. void multiplication(int a[2][2],int b[2][2]);//计算两个矩阵的乘积
  4. void power(int a[2][2],int n);//计算矩阵的次幂
  5. int Fibonacci(int n);
  6. int main(){
  7. int n;
  8. scanf("%d",&n);
  9. n=Fibonacci(n);
  10. printf("%d",n);
  11. return 0;
  12. }
  13. void multiplication(int a[2][2],int b[2][2]){
  14. int c[2][2];
  15. for(int i=0;i<2;i++){ // 两个矩阵相乘
  16. for(int j=0;j<2;j++){
  17. for(int k=0;k<2;k++){
  18. c[i][j]=a[i][k]*b[k][j];
  19. }
  20. }
  21. }
  22. a=c;
  23. }
  24. void power(int a[2][2],int n){
  25. int b=n;
  26. int in[2][2]={//矩阵
  27. {1,1},
  28. {1,0}
  29. };
  30. do{
  31. multiplication(a,a);//偶数
  32. n/=2;
  33. }while(n!=1);
  34. if(b&1){//考虑奇数
  35. multiplication(a,in);
  36. }
  37. return;
  38. }
  39. int Fibonacci(int n){
  40. int a[2][2]={//矩阵
  41. {1,1},
  42. {1,0}
  43. };
  44. int i[2]={1,0};//第一对数
  45. int res[2]={0};
  46. power(a,n);
  47. res[0]=i[0]*a[0][0]+i[1]*a[0][1];//矩阵乘法
  48. res[1]=i[0]*a[1][0]+i[1]*a[1][1];
  49. i[0]=res[0];
  50. i[1]=res[1];
  51. return i[1];
  52. }

在此输入正文

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注