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.}
