ResistorCombinations Topcoder



import java.util.ArrayList;
import java.util.HashSet;

public class ResistorCombinations
{
    double t, closest, res;

    ArrayList<ArrayList<Integer>> getSet(ArrayList<Integer> copy, int idx, int n, int size) {
        ArrayList<ArrayList<Integer>> S = new ArrayList<ArrayList<Integer>>();
        for (int i = idx; i < size; i++) {
            ArrayList<Integer> A = new ArrayList<Integer>(copy);
            A.add(i);
            if (n < size/2) S.addAll(getSet(A,i+1,n+1,size));
            S.add(A);
        }

        return S;
    }

    HashSet<Double> getAllCombos(ArrayList<Double> r) {
        if (r.size() <= 1) return new HashSet<Double>(r);

        ArrayList<Double> A, B;
        HashSet<Double> comboA, comboB;
        HashSet<Double> ret = new HashSet<Double>();

        ArrayList<ArrayList<Integer>> S = getSet(new ArrayList<Integer>(),0,1,r.size());

        for (int i = 0; i < S.size(); i++) {
            A = new ArrayList<Double>();
            B = new ArrayList<Double>(r);
            for (int j = S.get(i).size()-1; j >= 0; j--)
                A.add(B.remove((int)S.get(i).get(j)));
            comboA = getAllCombos(A);
            comboB = getAllCombos(B);
            for (double EA : comboA) {
                ret.add(EA);
                for (double EB : comboB) {
                    ret.add(EB);
                    ret.add(EA+EB);
                    ret.add((EA*EB)/(EA+EB));
                }
            }
        }

        return ret;
    }

    public double closestValue(String[] resistances, double target) {
        t = target;
        closest = res = Double.MAX_VALUE;

        ArrayList<Double> r = new ArrayList<Double>();
        for (int i = 0; i < resistances.length; i++)
            r.add(Double.parseDouble(resistances[i]));

        for (double d : getAllCombos(r))
            if (Math.abs(t-d) < closest) {res = d; closest = Math.abs(t-d);}

        return res;
    }
}


Explanation

getSet()
r의 모든 부분 집합을 만든다. 집합 크기의 반만 색인으로 계산하면 나머지 색인은 자동적으로 getAllCombos() 함수를 통해 계산된다. (n < size/2)

getAllCombos()
계산된 병렬 저항값과 다른 (직렬 또는 병렬) 저항값의 병렬 저항값은 그대로 병렬 저항 공식 (EA*EB)/(EA+EB)을 사용하면 된다.


References



1 2 3 4 5 6 7 8 9 10 다음