算法——Fibonacci（斐波纳契）序列问题

 

问题的由来：

 

13世纪的意大利数学家斐波纳契（Fibonacci）写了一本商用的算术和代数手册<<Liber abaci>>。在这本书里，他提出了这么一个有趣的问题：假定一对兔子在它们出生整整两个月以后可以生一对小兔子，其后每隔一个月又可以再生一对小兔子。假定现在在一个笼子里有一对刚生下来的小兔子，请问一年以后笼子里应该有几对兔子?

让我们仔细地算一下。第一、第二个月，小兔子长成大兔子，但还没成熟不能生小兔子，所以总共只有一对。第三个月，原有的一对大兔子生了一对小兔子，现在一共有二对了。第四个月，大兔子又生了一对小兔子，但是第二代的那对小兔子还没成熟，还不能生小兔子，所以总共有三对。第五个月，第一、二两代的两对兔子各生了一对小兔子，连同四月份原有的三对，现在一共有五对了。第六个月，在四月份已经有的三对兔子各生一对小兔了，连同五月份原有的五对兔子，现在一共有八对了。依此类推，每个月份所有的兔子对数应该等于其上一个月所有的兔子对数（也就是原有的兔子对数）及其上上个月所有的兔子对数（这些兔子各生了一对小兔子）的总和。所以每个月的兔子对数应该是1、1、2、3、5、8、13、21、34、55、89、144、233……，每一项都是前两项之和。因此，一年后笼子里应该有233对兔子了。

 

这些兔子的数目我们称之为斐波纳契数字（Fibonacci numbers）。为方便起见，我们用 F_n表示第 n 代兔子的数目。

我们观察到：

F₁=F₂=1

而当n≧3时，F_n=F_n-1+F_n-2

F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13
1	1	2	3	5	8	13	21	34	55	89	144	233

 

那么如何计算这个斐波纳契序列呢？

 

 

下面给出三种方法。

 

1、递归

最简单的方法就是递归实现，也是最慢的，算法时间复杂度O(n^2)

  

 

     /**
     * 计算：
     * f(n) = 0 (n = 0)
     * f(n) = １ (n = 1)?
     * f(n) = f[n-1] + f[n-2] (n >= 2)
     *
     * @param n
     * Fibonacci 序列
     * @return
     */
    public long fibonacciRecursion( int n )
    {
        if ( 0 == n )
        {
            return 0;
        } else if ( 1 == n )
        {
            return 1;
        } else
        {
            return fibonacciRecursion( n - 1 ) + fibonacciRecursion( n - 2 );
        }
    }

这个算法很容易懂，却最慢，大约在n=40以上，就明显难以忍受的慢了

2、递推

由f0,f1=>f2,继而由f2,f3=>f4,...,以此类推，可以求出fn

算法时间复杂度O(n)

    /**
     * 计算：
     * f(n) = 0                 (n = 0)
     * f(n) = １                 (n = 1)
     * f(n) = f[n-1] + f[n-2]     (n >= 2)
     *
     * @param n
     * Fibonacci 序列
     * @return
     */
    public long fibonacciAdd2N( int n )
    {
        if ( 0 == n )
        {
            return 0;
        } else if ( 1 == n )
        {
            return 1;
        } else
        {
            long n0 = 0;
            long n1 = 1;
            long fn = 0;
            for ( int i = 2; i <= n; i++ )
            {
                fn = n1 + n0;
                n0 = n1;
                n1 = fn;
                
            }    
            return fn;
        }
    }

这个算法比上面的要快得多，性能提高不少。基本上已经得到了比较满意的性能了。

3、数学优化后的迭代算法

  方法，通过矩阵运算，可以得到最优的算法复杂度，O(log2(n))

经过数学运算，发现以下规律：
    |f(n)  | = |1 1 | |f(n-1)|= |1 1 | |1 1 | |f(n-2)|.....
    |f(n-1)| = |1 0 | |f(n-2)|= |1 0 | |1 0 | |f(n-3)|.....

/**
     *
     * 方法，通过矩阵运算，可以得到最优的算法复杂度，O(log2(n))
     *        |f(n) | = |1    1 | |f(n-1)|= |1    1 | |1    1 | |f(n-2)|.....
     *        |f(n-1)| = |1    0 |    |f(n-2)|= |1    0 | |1    0 |    |f(n-3)|.....
     * @param n
     * @return
     */
    public long fibonacciMatrix( int n )
    {
        if ( 1 == n || 2 == n )
        {
            return 1;
        }

        long[][] a = { { 1, 1 }, { 1, 0 } };
        long[][] r = new long[2][2];


        //计算矩阵a的n-2次幂
        r = calcMatrixNPower( a, n - 2 );

        /*
         * 最后结果：
         *
         *         |f(n) | = |r00    r01 ||f(1)|    = r00 + r01
         *         |f(n-1)| = |r10    r11 ||f(2)| = r10 + r11
         *
         */
        return r[0][0] + r[0][1];//最后result与

    }

该算法相比较第二个算法性能提高了不少，但没有第二个算法相对于第一个提高的多，由n^2=>n=>logn很明显可以看出其中的原因，另外矩阵运算也比加法运算要多做几次乘、加法运算。总的来说，这个算法是最优的算法。

 

下面给出完整的算法源码：

 

package zieckey.datastructure.study.recursion;

import java.math.BigInteger;
import java.util.Date;


public class Fibonacci {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        
        int n = 120000;
        Fibonacci r = new Fibonacci( );
        
        long begin, done;
        begin = new Date( ).getTime( );
        System.out.println( r.funLastLiuBing( n ) );
        done = new Date( ).getTime( );

        System.out.println( "funLastLiuBing:花费时间：" + ( done - begin ) + "ms" );

        

        begin = new Date( ).getTime( );
        System.out.println( "fibonacciMatrixBigInteger:         "
                + r.fibonacciMatrixBigInteger( n ) );
        done = new Date( ).getTime( );
        System.out.println( "fibonacciMatrixBigInteger:花费时间：" + ( done - begin )
                + "ms" );
        
        
        begin = new Date( ).getTime( );
        System.out.println( "fibonacciMatrixMultiply2NBigInteger:         "
                + r.fibonacciMatrixBigInteger( n ) );
        done = new Date( ).getTime( );
        System.out.println( "fibonacciMatrixMultiply2NBigInteger:花费时间：" + ( done - begin )
                + "ms" );
        
        


    }


    /**
     * 计算： f(n) = n + １ (n <２)? f(n) = f[n/2] + f[n/4] (n >= 2)
     *
     * @param 传入参数
     * n>0 的正整数
     * @return
     */
    public int func( int n )
    {
        if ( 2 > n )
        {
            return n + 1;
        } else
        {
            return func( (int)n / 2 ) + func( (int)n / 4 );
        }
    }

    /**
     * 计算：
     * f(n) = 0 (n = 0)
     * f(n) = １ (n = 1)?
     * f(n) = f[n-1] + f[n-2] (n >= 2)
     *
     * @param n
     * Fibonacci 序列
     * @return
     */
    public long fibonacciRecursion( int n )
    {
        if ( 0 == n )
        {
            return 0;
        } else if ( 1 == n )
        {
            return 1;
        } else
        {
            return fibonacciRecursion( n - 1 ) + fibonacciRecursion( n - 2 );
        }
    }
    
    /**
     * 计算：
     * f(n) = 0                 (n = 0)
     * f(n) = １                 (n = 1)
     * f(n) = f[n-1] + f[n-2]     (n >= 2)
     *
     * @param n
     * Fibonacci 序列
     * @return
     */
    public long fibonacciAdd2N( int n )
    {
        if ( 0 == n )
        {
            return 0;
        } else if ( 1 == n )
        {
            return 1;
        } else
        {
            long n0 = 0;
            long n1 = 1;
            long fn = 0;
            for ( int i = 2; i <= n; i++ )
            {
                fn = n1 + n0;
                n0 = n1;
                n1 = fn;
                
            }    
            return fn;
        }
    }

    /**
     * 可以计算无限大的数
     * @param n
     * @return
     */
    public BigInteger fibonacciAdd2NBigInteger( int n )
    {
        if ( 0 == n )
        {
            return new BigInteger("0");
        } else if ( 1 == n )
        {
            return new BigInteger("1");
        } else
        {
            BigInteger n0 = BigInteger.ZERO;
            BigInteger n1 = BigInteger.ONE;
            BigInteger fn = BigInteger.ZERO;
            for ( int i = 2; i <= n; i++ )
            {
                fn = n1.add( n0 );
                n0 = n1;
                n1 = fn;
            }    
            return fn;
        }
    }
    
    
    /**
     *
     * 方法，通过矩阵运算，可以得到最优的算法复杂度，O(log2(n))
     *        |f(n) | = |1    1 | |f(n-1)|= |1    1 | |1    1 | |f(n-2)|.....
     *        |f(n-1)| = |1    0 |    |f(n-2)|= |1    0 | |1    0 |    |f(n-3)|.....
     * @param n
     * @return
     */
    public long fibonacciMatrix( int n )
    {
        if ( 1 == n || 2 == n )
        {
            return 1;
        }

        long[][] a = { { 1, 1 }, { 1, 0 } };
        long[][] r = new long[2][2];

        r = calcMatrixNPower( a, n - 2 );

        /*
         * 最后结果：
         *
         *         |f(n) | = |r00    r01 ||f(1)|    = r00 + r01
         *         |f(n-1)| = |r10    r11 ||f(2)| = r10 + r11
         *
         */
        return r[0][0] + r[0][1];//最后result与

    }
    
    
    /**
     * 可以计算无限大的数
     *
     * 方法，通过矩阵运算，可以得到最优的算法复杂度，O(log2(n))
            |f(n) | = |1    1 | |f(n-1)|= |1    1 | |1    1 | |f(n-2)|.....
             |f(n-1)| = |1    0 |    |f(n-2)|= |1    0 | |1    0 |    |f(n-3)|.....
     * @param n
     * @return
     */
    public BigInteger fibonacciMatrixBigInteger( int n )
    {
        if ( 1 == n || 2==n )
        {
            return new BigInteger("1");
        }
        BigInteger temp = new BigInteger("0");
        BigInteger[][] a = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
        BigInteger[][] result = new BigInteger[2][2];
        
        result = calcMatrixNPowerBigInteger( a, n-2 );
        
        temp = result[0][0];
        temp = temp.add( result[0][1] );
        return temp;
    }
    
    
    /**
     * 可以计算无限大的数
     *
     * 方法，通过矩阵运算，可以得到最优的算法复杂度，O(log2(n))
            |f(n) | = |1    1 | |f(n-1)|= |1    1 | |1    1 | |f(n-2)|.....
             |f(n-1)| = |1    0 |    |f(n-2)|= |1    0 | |1    0 |    |f(n-3)|.....
     * @param n
     * @return
     */
    public BigInteger fibonacciMatrixMultiply2NBigInteger( int n )
    {
        if ( 1 == n || 2==n )
        {
            return new BigInteger("1");
        }
        BigInteger temp = new BigInteger("0");
        BigInteger[][] a = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
        BigInteger[][] result = {{BigInteger.ONE,BigInteger.ZERO},{BigInteger.ZERO,BigInteger.ONE}};
        
//        result = calcMatrixNPowerBigInteger( a, n-2 );

        //n-2次循环

        for ( int i = 0; i < n-2; i++ )
        {
            result = calcMatrixMultipleBigInteger( result, a );
        }
        
        temp = result[0][0];
        temp = temp.add( result[0][1] );
        return temp;
    }
    
    /**
     *
     * @param
     * @param b
     * @return 矩阵a与矩阵b相乘的结果
     */
    public long[][] calcMatrixMultiple( long[][] a , long[][] b )
    {
        long[][] result = new long[2][2];
        
        result[0][0] =      a[0][0] * b[0][0]
         + a[0][1] * b[1][0];
        
        result[0][1] =      a[0][0] * b[0][1]
          + a[0][1] * b[1][1];
        
        result[1][0] =      a[1][0] * b[0][0]
          + a[1][1]* b[1][0];
        
        result[1][1] =      a[1][0] * b[0][1]
                  + a[1][1]* b[1][1];
        return result;
    }
    
    /**
     *
     * @param a
     * @param n
     * @return 矩阵a的n次方结果
     */
    public long[][] calcMatrixNPower( long[][] a, int n )
    {
        long[][] result = {{1,0},{0,1}};;//初始化为单位阵

        long[][] temp = new long[2][2];
        int log2n = 0;
        
        /**
         * 例如：n=25
         * 外层for 3次循环
         *         第一次 result = (a^2)^4                        i=25
         *         第二次 result = ((a^2)^4) * ((a^2)^3)            i=9
         *         第三次 result = (((a^2)^4)*((a^2)^3))*a        i=1
         *
         * 例如：n=24
         * 外层for 2次循环
         *         第一次 result = (a^2)^4                        i=24
         *         第二次 result = ((a^2)^4) * ((a^2)^3)            i=8
         */
        for ( int i = n; i >= 1 ; i = i - (int)Math.pow( 2, log2n ) )
        {
            temp = a;//初始化 temp 等于a

            log2n = log2(i); //找到最大的 log2(i)

            for ( int j = 0; j < log2n; j++ )
            {
                temp = calcMatrixMultiple( temp, temp ); //计算(temp的平方)的log2n次方

            }
            result = calcMatrixMultiple( result, temp );
        }
        
        return result;
    }

    
    /**
     *
     * 对方法calcMatrixANPower测试用的
     * @param a
     * @param n
     * @return    a的n次幂
     */
    public long testPower(int a, int n)
    {
        long result = 1;
        int temp = a;
        int log2n = 0;
        
        for ( int i = n; i >= 1 ; i = i - (int)Math.pow( 2, log2n ) )
        {
            temp = a;//初始化 temp 等于a

            log2n = log2(i); //找到最大的 log2(i)

            for ( int j = 0; j < log2n; j++ )//计算(temp的平方)的log2n次方

            {
                temp = temp*temp;
            }
            result = result*temp;
        }
        
        return result;
    }
    

    /**
     *
     * @param a
     * @param b
     * @return 矩阵a与矩阵b相乘的结果
     */
    public BigInteger[][] calcMatrixMultipleBigInteger( BigInteger[][] a, BigInteger[][] b )
    {
        BigInteger[][] result = new BigInteger[2][2];
        BigInteger temp = new BigInteger("0");
        
        
        temp = a[0][0].multiply( b[0][0] ) ;
        result[0][0] =      temp.add( a[0][1].multiply( b[1][0]) ) ;
        

        temp = a[0][0].multiply( b[0][1] ) ;
        result[0][1] =      temp.add( a[0][1].multiply( b[1][1]) ) ;
        
        
        temp = a[1][0].multiply( b[0][0] ) ;
        result[1][0] =      temp.add( a[1][1].multiply( b[1][0]) ) ;
        
        temp = a[1][0].multiply( b[0][1] ) ;
        result[1][1] =      temp.add( a[1][1].multiply( b[1][1]) ) ;
        return result;
    }
    
    /**
     *
     * @param a
     * @param n
     * @return 矩阵a的n次方结果
     */
    public BigInteger[][] calcMatrixNPowerBigInteger( BigInteger[][] a, int n )
    {
        BigInteger[][] result = {{BigInteger.ONE,BigInteger.ZERO},{BigInteger.ZERO,BigInteger.ONE}};
        BigInteger[][] temp = new BigInteger[2][2];
        int log2n = 0;
        
        for ( int i = n; i >= 1 ; i = i - (int)Math.pow( 2, log2n ) )
        {
            temp = a;//初始化 temp 等于a

            log2n = log2(i); //找到最大的 log2(i)

            for ( int j = 0; j < log2n; j++ )
            {
                temp = calcMatrixMultipleBigInteger( temp, temp ); //计算(temp的平方)的log2n次方

            }
            result = calcMatrixMultipleBigInteger( result, temp );
        }
        
        return result;
    }
    
    /**
     *
     * @param n
     * @return 以2为底的log对数
     */
    public int log2( int n )
    {
        int result = 0;
        result = (int) ( Math.log( n ) / Math.log( 2 ) );
        return result;
    }
    
}