Q江小白
2018-05-06 15:21
采纳率: 100%
浏览 709
已采纳

斐波那契问题最后的返回值为什么是数组的第一列

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));
    //输出

    }
    }

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • threenewbee 2018-05-06 15:53
    已采纳
     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  
    

    对应的公式推导图片说明

    已采纳该答案
    打赏 评论
  • threenewbee 2018-05-06 15:46

    加点调试信息 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));
          //输出
    
       }
    }
    
    打赏 评论
  • threenewbee 2018-05-06 15:50

    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

    打赏 评论

相关推荐 更多相似问题