兔子数列

自然界现象抽象化得到的数列模型——斐波那契数列

1. 初始状态：一对刚出生的兔子
2. 下一步：生长
3. 繁殖得到 一对刚出生的兔子-> 第1步

总结： 当月的兔子数=上月兔子数+当月新生兔子 数列的当前列=前两列之和

递归算法

指数阶算法，效率较低，时间复杂度爆炸增量

    Fib1(int n)
    
    { if(n<1)
    
           return -1;
    
      if(n==1||n==2)
    
            return 1;
    
       return Fib1(n-1)+Fib1(n-2);
    
    }
    

数组记录先两项值

时间复杂度从指数阶降到了多项式阶O(n),空间复杂度O(n)

Fib2(intn)
{
    if(n<1)
        return-1;
    int[] a=new int[n];
    a[1]=1;
    a[2]=1;
    for(int i=3;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
        return a[n];
     }
}
         
    

迭代法

不记录中间结果，只记录中间项，空间复杂度降到O(1)

Fib3(intn)
{
    inti,s1,s2;
    if(n<1)
        return-1;
    if(n==1||n==2)
        return1;
    s1=1;s2=1;
    for(i=3;i<=n;i++)
    {
        s2=s1+s2;//辗转相加法
        s1=s2-s1;//记录前一项
    }
    return s2;
 }
 

矩阵乘法

斐波那契数列(F(n),F(n-1))为(1,1)与{{1,1},{1,0}}的n-2次幂的乘积, 可通过递推求证

   public static int ValueN(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 int[][] matrixPower(int[][] m,int p){
           if(p==0)
               return null;
           if(p==1)
               return m;
           int[][] res=matrixPower(m,p>>1);
           res=muliMatrix(res,res);
           if((p&1)==1){
               res=muliMatrix(res,m);
           }
           return res;
       }
       //求两个矩阵相乘得到一个新的矩阵
       public static int[][] muliMatrix(int[][] m1,int[][] m2){
           int [][] res=new int[m1.length][m2[0].length];
           for(int i=0;i<m1.length;i++){
               for(int j=0;j<m2[0].length;j++){
                   for(int k=0;k<m2.length;k++){
                       res[i][j]+=m1[i][k]*m2[k][j];
                   }
               }
           }
           return res;
       }
   }