当前位置:首页 » Project Euler » 详细页

Convergents of e 题号:65 难度: 15 中英对照

The square root of 2 can be written as an infinite continued fraction.

√2 = 1 +
1

Solution

此道题目显示有问题,请点击中英对照查看题目。 $e$ 的连分数项$e=[2;1,2,1,1,4,1,1,6,1, … ,1,2k,1,..,]$ 的每一项 $e[i]$ 可表示为 $$ e[i]=2, i=0 $$ $$ e[i]= \lfloor i/3 \rfloor*2+2,i\% 3=2 $$ $$ e[i]=1,其他情况 $$ 通过上述的式子,我们就能得到 $e$ 的第100项以内连分数项的值,接着只要执行相应的逼近运算就能得到e的第100个逼近值的分子。再求和即可。求分子的方法如下: 1.初始化$n=1,d=0$ 2.从第100项开始,$i=100$,$temp=e[i]*n+d,d=n,n=temp$ 3.当处理到第一项时结束,此时的$n$值即为e的第100个逼近值的分子。否则,$i=i-1$,继续执行步骤2

Code

import java.math.BigInteger;

public final class p65 {
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		int result = run();
        long end = System.nanoTime();
		System.out.println( result );
		System.out.println (( end - start )/1000000 +"ms");
	}
	
	
	public static  int run() {
		BigInteger n = BigInteger.ONE;  
		BigInteger d = BigInteger.ZERO; 
		//得到e的第100项以内连分数项的值
		for (int i = 99; i >= 0; i--) {
			BigInteger temp = BigInteger.valueOf(continuedFractionTerm(i)).multiply(n).add(d);
			d = n;  
			n = temp; 
		}
		
		int sum = 0;
		while (!n.equals(BigInteger.ZERO)) {
			BigInteger[] divrem = n.divideAndRemainder(BigInteger.TEN);
			sum += divrem[1].intValue();
			n = divrem[0];
		}
		return sum;
	}
	
	//算出e的连分数项的值e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...]
	private static int continuedFractionTerm(int i) {
		if (i == 0)
			return 2;
		else if (i % 3 == 2)
			return i / 3 * 2 + 2; 
		else
			return 1;
	}
	
}
272
2ms