O(logN)算法中
public int Fibonacci(int n){
if(n<1)
return 0;
if(n==1||n==2)
return 1;
int base[][]={{1,1},{1,0}};
int res[][]=matrixPower(base,n-2);
return res[0][0]+res[1][0]; //这里为什么是这样,为什么取res数组的第一列，
在计算矩阵时，计算的结果还是矩阵（二维数组），为什么就取数组的第一列。
//（
}
代码如下：
package 实验;
/*
-
矩阵的n次方
*/
public class Matrix {
public int[][]muilmatrix(int[][]m1,int[][]m2){
int res[][]=new int[m1.length][m2[0].length];
for(int i=0;i<m2[0].length;i++){
for(int j=0;j<m1.length;j++){
for(int k=0;k<m2.length ;k++){
res[i][j]+=(m1[i][k]*m2[k][j]);} }}
return res;
}
//计算p次方
public int[][] matrixPower(int [][]m1,int p){
int res[][]=new int[m1.length][m1[0].length];
for(int i=0;i res[i][i]=1;
}
int [][]temp=m1;
for(;p!=0;p>>=1){
if((p&1)!=0){
res=muilmatrix(res,temp);
}
temp=muilmatrix(temp,temp);
}
return res;
}
public int Fibonacci(int n){
if(n<1)
return 0;
if(n==1||n==2)
return 1;
int base[][]={{1,1},{1,0}};
int res[][]=matrixPower(base,n-2);
return res[0][0]+res[1][0]; //这里为什么是这样，
}
public static void main(String args[]){
Matrix matrix=new Matrix();
int a[][]={{1,1},{1,0}};
int b[][]= matrix.matrixPower(a, 2);
int c=9;
System.out.println(matrix.Fibonacci(c));
//输出}
}
