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

Counting fractions in a range 题号:73 难度: 15 中英对照

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

Solution

求在$\frac{a}{b}$和$\frac{c}{d}$之间满足条件的分数的个数,这里用到了数论中 **[Stern-Brocot tree](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree)** 的知识, 即如果有 $b\cdot c - a\cdot d = 1$ ,那么分母满足条件的中间数是 $$ m = \frac{e}{f} = \frac{a+c}{b+d}, 如果 f \leq N $$ 如果 $b+d > N$ ,则在两者之间没有满足条件的中间数。 在$\frac{a}{b}$和$\frac{c}{d}$之间,我们插入$\frac{a+c}{b+d}$,判断其分母$b+d$是否大于12000,如果不大于则继续上述步骤,并对答案贡献1个符合条件的分数,否则停止。

Code


public final class p73 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
	/* 
	 * The Stern-Brocot tree is an infinite binary search tree of all positive rational numbers,
	 * where each number appears only once and is in lowest terms.
	 * It is formed by starting with the two sentinels 0/1 and 1/1. Iterating infinitely in any order,
	 * between any two currently adjacent fractions Ln/Ld and Rn/Rd, insert a new fraction (Ln+Rn)/(Ld+Rd).
	 * See MathWorld for a visualization: http://mathworld.wolfram.com/Stern-BrocotTree.html
	 * 
	 * This algorithm uses a lot of stack space (about 12000 frames). You probably need to use a JVM option like "-Xss4M".
	 */
    static public String run(){
		return Integer.toString(sternBrocotCount(1, 3, 1, 2));

    }
	// Counts the number of reduced fractions n/d such that leftN/leftD < n/d < rightN/rightD and d <= 12000.
	// leftN/leftD and rightN/rightD must be adjacent in the Stern-Brocot tree at some point in the generation process.
	private static int sternBrocotCount(int leftN, int leftD, int rightN, int rightD) {
		int n = leftN + rightN;
		int d = leftD + rightD;
		if (d > 12000)
			return 0;
		else
			return 1 + sternBrocotCount(leftN, leftD, n, d) + sternBrocotCount(n, d, rightN, rightD);
	}
}
7295372
154ms