Problem25

package com.yao.Algorithms;

import java.math.BigInteger;

/**
 * 
 * @author shuimuqinghua77 @date 2012-4-26下午02:33:04
 *
 */
public class Problem25 {
public static void main(String[] args) {

	/**
	 * 下面是运用数学上的方式来破解这个1000位数的难题
	 * 只需要1ms
	 */
	/**
	 * 但是Fibonacci sequence还有一个重要的性质就是
	 * an=1/√5 [（1/2+√5/2)^ n-(1/2-√5/2)^n]
	 *
	 * 
	 *  还有一个黄金比例的法则
	 *  即在较高的序列，两个连续的“斐波纳契数”的序列相互分割
　		将接近黄金比例（1.618:1或1:0.618）。
 		即 an=1.618*1/√5 [（1/2+√5/2)^ (n-1)-(1/2-√5/2)^(n-1)]
		可以推出
		[√5-(1-√5)/2*√5/1.618]an=(1/2+√5)^(n-1)(√5)
		2边同时取以10为底的对数
		lg(an)=(n-1)lg((1/2+√5))+lg√5-lg√5-(1-√5)/2*√5/1.618]
		当lg(an)>=999时候 也就是an突破1000位的时候
	 */
	long  start1=System.currentTimeMillis();
	double five=Math.sqrt(5);
	double   factor1=five-(1-five)/2*five/1.618;
	double  factor2=five;
	double factor3=0.5+five/2;
	double factor4=Math.log10(factor2)-Math.log10(factor1);
	for(int i=2;;i++){
		double lg_an=Math.log10(factor3)*(i-1)+factor4;
		if(lg_an>=999)
		{
			System.out.println("结果是："+i);
			break;
		}
			
	}
	long  end1=System.currentTimeMillis();
	System.out.println(end1-start1+"ms");
	
	/**
	 * 还有一种比较挫的做法就是使用计算机使用暴力破解  785ms
	 */
	long  start=System.currentTimeMillis();
	BigInteger fn=new BigInteger("0");
	BigInteger fn_1=new BigInteger("1");
	BigInteger fn_2=new BigInteger("1");
	int count=2;
	
	while(fn.toString().length()!=1000){
		fn=fn_1.add(fn_2);
		fn_2=fn_1;
		fn_1=fn;
		count++;
	}
	System.out.println(count);
	long  end=System.currentTimeMillis();
	System.out.println(end-start+"ms");
}

}