斐波那契问题最后的返回值为什么是数组的第一列
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));
//输出}
}
m1-------------
1 1
1 0
m2-------------
1 1
1 0
---------------
2 1
1 1
m1-------------
1 0
0 1
m2-------------
2 1
1 1
---------------
2 1
1 1
m1-------------
2 1
1 1
m2-------------
2 1
1 1
---------------
5 3
3 2
m1-------------
1 0
0 1
m2-------------
1 1
1 0
---------------
1 1
1 0
m1-------------
1 1
1 0
m2-------------
1 1
1 0
---------------
2 1
1 1
m1-------------
1 1
1 0
m2-------------
2 1
1 1
---------------
3 2
2 1
m1-------------
2 1
1 1
m2-------------
2 1
1 1
---------------
5 3
3 2
m1-------------
3 2
2 1
m2-------------
5 3
3 2
---------------
21 13
13 8
m1-------------
5 3
3 2
m2-------------
5 3
3 2
---------------
34 21
21 13
对应的公式推导
加点调试信息 https://ideone.com/G7TDKT
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is 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]);
}
}
}
System.out.println("m1-------------");
for (int i = 0; i < m1.length; i++)
{
for (int j = 0; j < m1[i].length; j++)
{
System.out.print(m1[i][j] + " ");
}
System.out.println();
}
System.out.println("m2-------------");
for (int i = 0; i < m2.length; i++)
{
for (int j = 0; j < m2[i].length; j++)
{
System.out.print(m2[i][j] + " ");
}
System.out.println();
}
System.out.println("---------------");
for (int i = 0; i < res.length; i++)
{
for (int j = 0; j < res[i].length; j++)
{
System.out.print(res[i][j] + " ");
}
System.out.println();
}
return res;
}
//计算p次方
public int[][] matrixPower(int [][]m1,int p){
int res[][]=new int[m1.length][m1[0].length];
for(int i=0;i<m1.length;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));
//输出
}
}
m1-------------
1 1
1 0
m2-------------
1 1
1 0
2 1
1 1
m1-------------
1 0
0 1
m2-------------
2 1
1 1
2 1
1 1
m1-------------
2 1
1 1
m2-------------
2 1
1 1
5 3
3 2
m1-------------
1 0
0 1
m2-------------
1 1
1 0
1 1
1 0
m1-------------
1 1
1 0
m2-------------
1 1
1 0
2 1
1 1
m1-------------
1 1
1 0
m2-------------
2 1
1 1
3 2
2 1
m1-------------
2 1
1 1
m2-------------
2 1
1 1
5 3
3 2
m1-------------
3 2
2 1
m2-------------
5 3
3 2
21 13
13 8
m1-------------
5 3
3 2
m2-------------
5 3
3 2
34 21
21 13
34
res[i][j]+=(m1[i][k]*m2[k][j]);
注意看，m1 m2如何得到res的，两者对角线相加放入另一个对角线
从而res每次的结果的最左边两项就是数列的n和n-1