程序员的算法趣题：Q29 合成电阻的黄金分割比（Java版）

时间：12-29来源：作者：点击数：

题目说明

我们在物理课上都学过“电阻”，通过把电阻串联或者并联可以使电阻值变大或者变小。

电阻值分别为 R1、R2、R3的 3 个电阻串联后，合成电阻的值为R1＋R2＋R3。

同样3个电阻并联时，合成电阻的值则为“倒数之和的倒数”（图 18 ）。

现在假设有 n 个电阻值为 1 Ω 的电阻。组合这些电阻，使总电阻值接近黄金分割比1.6180339887…。

举个例子，当 n ＝ 5 时，如果像图 19 这样组合，则可以使电阻值为 1.6。

思路

1.可以把10个电阻分成两组，这两组可以串联or并联

2.不同组合方式会有不同的电阻值，将它们存入Set集合（自动去重）

3.每一组又可以继续分成两组，串联or并联

4.定义一个递归方法f(n)，目标是求出n个1Ω电阻可以组合出的电阻值集合，并返回该集合

5.遍历f(10)，求出最接近黄金分割比的那个电阻值

代码

// <电阻个数,电阻值>
private static Map<Integer, Set<Double>> hmap = new HashMap<>();
public static void main(String[] args) {
    double goldenRatio = 1.6180339887;  // 黄金分割比
    double minGap = 10;                 // 保存每种组合电阻的电阻值与黄金分割比的差距，以便求出最接近黄金分割比的电阻值
    double nearestR = 0;                // 最接近黄金分割比的电阻值

    Set<Double> set = f(10);            // 10个电阻组合后的各种电阻值

    for (Double r : set) {
        if(Math.abs(r-goldenRatio) < minGap){
            minGap = Math.abs(r-goldenRatio);
            nearestR = r;
        }
    }

    // 仅用于查看不同个数电阻各种组合的电阻值，以便排查错误
    hmap.forEach((k,v) -> {
        System.out.println(k + " ==> " + v);
    });

    System.out.println("nearestR = " + nearestR);

}

// 计算n个电阻各种串联、并联的所有可能，并将电阻值返回。
private static Set<Double> f(int n){
    Set<Double> set = new TreeSet<Double>();

    if(n < 0) return set;

    // 如果已经计算过，则直接返回Set
    if(hmap.get(n) != null){
        return hmap.get(n);
    }

    if(n == 0 || n == 1){
        set.add(n * 1.0);
        hmap.put(n, set);
        return set;
    }

    if(n == 2){
        set.addAll(Arrays.asList(2.0, 0.5));    // 两个1Ω的电阻串联、并联的电阻值
        hmap.put(n, set);
        return set;
    }

    // 串 0  1   2   3      n  ==>  i
    // 并 n n-1 n-2 n-3 ... 0  ==> n-i
    for (int i = 1; i < n; i++) {               // i表示第一组电阻的个数
        set.addAll(c(f(i), f(n-i)));            // 两个电阻组合串联
        set.addAll(b(f(i), f(n-i)));            // 两个电阻组合并联
    }

    hmap.put(n, set);
    return set;
}

// 串联2个电阻组合得到的各种电阻值
private static Set<Double> c(Set<Double> s1, Set<Double> s2){
    Set<Double> set = new TreeSet<Double>();
    for (Double r1 : s1) {
        for (Double r2 : s2) {
            double r = r1 + r2;     // 串联的电阻值
            set.add(r);             // set自动去重
        }
    }
    return set;
}

// 并联2个电阻组合得到的各种电阻值
private static Set<Double> b(Set<Double> s1, Set<Double> s2){
    Set<Double> set = new TreeSet<Double>();
    for (Double r1 : s1) {
        for (Double r2 : s2) {
            double r = 1.0 / ((1.0 / r1) + (1.0 / r2));     // 并联的电阻值
            set.add(r);                                     // set自动去重
        }
    }
    return set;
}