|
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]<
| 