本文共 1975 字，大约阅读时间需要 6 分钟。
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.} 转载地址：http://jtyyo.baihongyu.com/