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

Counting Capacitor Circuits 题号:155 难度: 60 中英对照

An electric circuit uses exclusively identical capacitors of the same value C.
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to n=3 capacitors of 60 F each, we can obtain the following 7 distinct total capacitance values:

If we denote by D(n) the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors and the simple procedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...

Find D(18).

Reminder : When connecting capacitors C1, C2 etc in parallel, the total capacitance is CT = C1 + C2 +...,
whereas when connecting them in series, the overall capacitance is given by:


Solution

考虑数量恰好为$n$的电容可以组成$f(n)$种不同的结果。 那么$f(n+1)=get\left( \sum_{1\leq i,j\leq n\quad i+j=n+1}f(n) \right)$,其中$get$表示去重操作。 考虑去重操作是针对$double$型的去重,不能直接比较,需要用$eps$比较,即$abs(a-b)/b< eps$则表示它们的相对误差不超过$eps$。 如此在添加元素时需要不断对当前数组进行排序、对相邻两个数的相对误差不超过$00000001$的情况删去其中一个数。 这个操作在代码中为函数trim。 此时只需要数组开得较大即可,选取了5200000,已经足够用了。

Code

import java.util.*;

public final class p155 {
    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" );
    }
    
    static public String run() {
		double[][] mem = new double[19][];
		mem[1] = new double[1];
		mem[1][0] = 1;
		double[] temp = new double[5200009];
		int len = 0;
		for (int i = 2; i <= 18; i++) {
			len = 0;
			for (int j = 1; j <= i / 2; j++) {
				int k = i - j;
				for (double d1 : mem[j]) {
					for (double d2 : mem[k]) {
						temp[len++] = d1 + d2;
						temp[len++] = 1 / (1 / d1 + 1 / d2);
						if (len > 5200000) {
							len = trim(temp, 0, len);
						}
					}
				}
			}
			len = trim(temp, 0, len);
			if (i < 18) {
				mem[i] = new double[len];
				for (int j = 0; j < len; j++) {
					mem[i][j] = temp[j];
				}
			}
		}
		for (int i = 1; i <= 17; i++) {
			for (double d : mem[i]) {
				temp[len++] = d;
				if (len > 5200000) {
					len = trim(temp, 0, len);
				}
			}
		}
		len = trim(temp, 0, len);
		return len+"";
	}
	public static int trim(double[] array, int fromIndex, int toIndex) {
		Arrays.sort(array, fromIndex, toIndex);
		int lastIndex = fromIndex - 1;
		double last = 0;
		for (int j = fromIndex; j < toIndex; j++) {
			if (Math.abs((array[j] - last) / array[j]) > 0.00000001) {
				array[++lastIndex] = array[j];
				last = array[j];
			}
		}
		return lastIndex + 1;
	}
	
}
3857447
6138ms