Problem25

1.package com.yao.Algorithms;  
2.  
3.import java.math.BigInteger;  
4.  
5./** 
6. *  
7. * @author shuimuqinghua77 @date 2012-4-26下午02:33:04 
8. * 
9. */  
10.public class Problem25 {  
11.public static void main(String[] args) {  
12.  
13.    /** 
14.     * 下面是运用数学上的方式来破解这个1000位数的难题 
15.     * 只需要1ms 
16.     */  
17.    /** 
18.     * 但是Fibonacci sequence还有一个重要的性质就是 
19.     * an=1/√5 [（1/2+√5/2)^ n-(1/2-√5/2)^n] 
20.     * 
21.     *  
22.     *  还有一个黄金比例的法则 
23.     *  即在较高的序列，两个连续的“斐波纳契数”的序列相互分割 
24.　       将接近黄金比例（1.618:1或1:0.618）。 
25.        即 an=1.618*1/√5 [（1/2+√5/2)^ (n-1)-(1/2-√5/2)^(n-1)] 
26.        可以推出 
27.        [√5-(1-√5)/2*√5/1.618]an=(1/2+√5)^(n-1)(√5) 
28.        2边同时取以10为底的对数 
29.        lg(an)=(n-1)lg((1/2+√5))+lg√5-lg√5-(1-√5)/2*√5/1.618] 
30.        当lg(an)>=999时候 也就是an突破1000位的时候 
31.     */  
32.    long  start1=System.currentTimeMillis();  
33.    double five=Math.sqrt(5);  
34.    double   factor1=five-(1-five)/2*five/1.618;  
35.    double  factor2=five;  
36.    double factor3=0.5+five/2;  
37.    double factor4=Math.log10(factor2)-Math.log10(factor1);  
38.    for(int i=2;;i++){  
39.        double lg_an=Math.log10(factor3)*(i-1)+factor4;  
40.        if(lg_an>=999)  
41.        {  
42.            System.out.println("结果是："+i);  
43.            break;  
44.        }  
45.              
46.    }  
47.    long  end1=System.currentTimeMillis();  
48.    System.out.println(end1-start1+"ms");  
49.      
50.    /** 
51.     * 还有一种比较挫的做法就是使用计算机使用暴力破解  785ms 
52.     */  
53.    long  start=System.currentTimeMillis();  
54.    BigInteger fn=new BigInteger("0");  
55.    BigInteger fn_1=new BigInteger("1");  
56.    BigInteger fn_2=new BigInteger("1");  
57.    int count=2;  
58.      
59.    while(fn.toString().length()!=1000){  
60.        fn=fn_1.add(fn_2);  
61.        fn_2=fn_1;  
62.        fn_1=fn;  
63.        count++;  
64.    }  
65.    System.out.println(count);  
66.    long  end=System.currentTimeMillis();  
67.    System.out.println(end-start+"ms");  
68.}  
69.  
70.}