155. 电容电路计数(Counting Capacitor Circuits)

一个电路仅使用电容值相同、均为 $C$ 的相同电容器。电容器可以串联或并联形成子单元，这些子单元随后又可以与其他电容器或其他子单元串联或并联，形成更大的子单元，如此继续，直到得到最终电路。

使用这个简单过程和最多 $n$ 个相同电容器，我们可以构造出具有一系列不同总电容值的电路。例如，使用最多 $n=3$ 个电容值均为 $60\ \mu F$ 的电容器，可以得到以下 $7$ 个不同的总电容值：$20\ \mu F$、$30\ \mu F$、$40\ \mu F$、$60\ \mu F$、$90\ \mu F$、$120\ \mu F$、$180\ \mu F$。

若用 $D(n)$ 表示通过上述简单过程、使用最多 $n$ 个相同电容器时可以得到的不同总电容值的数量，则有：$D(1)=1$，$D(2)=3$，$D(3)=7$，$\dots$

求 $D(18)$。

提醒：当电容器 $C_1, C_2$ 等并联时，总电容为 $C_T = C_1 + C_2 + \cdots$；而当它们串联时，总电容满足：$\dfrac{1}{C_T} = \dfrac{1}{C_1} + \dfrac{1}{C_2} + \cdots$。

一、题意概述

所有电容器的电容值相同，因此可以把单个电容的值归一化为 $1$。任意子电路的总电容都是一个正有理数。题目要求统计最多使用 $18$ 个电容器时，所有可构造电路对应的不同有理数电容值数量。

一个最终电路可以看作由两个更小的子电路组合而成，组合方式只有两种：

并联：电容值相加
串联：倒数相加后再取倒数

因此本题自然适合用动态规划按电容器数量逐层生成可达电容值集合。

二、数学背景

设两个子电路的归一化电容值分别为：

$$ a=\frac{p_1}{q_1},\qquad b=\frac{p_2}{q_2} $$

并联时：

$$ a+b=\frac{p_1q_2+p_2q_1}{q_1q_2} $$

串联时：

$$ \frac{1}{c}=\frac{1}{a}+\frac{1}{b} =\frac{q_1}{p_1}+\frac{q_2}{p_2} =\frac{q_1p_2+q_2p_1}{p_1p_2} $$

所以：

$$ c=\frac{p_1p_2}{p_1q_2+p_2q_1} $$

每次生成新值后都用最大公约数约分，把同一个有理数统一表示为互素整数对 $(p,q)$。这样集合去重就是普通的元组去重，不需要浮点数，也不会产生精度误差。

三、算法分析

候选算法一：直接使用 `Fraction`

Python 的 fractions.Fraction 可以自动约分并支持加法、除法等运算。写法最短，逻辑也最直观。但本题最终会产生数百万个不同电容值，Fraction 对象的构造和运算开销较大，容易把运行时间浪费在对象封装上。

候选算法二：使用约分整数对

用 (numerator, denominator) 表示归一化电容值，手写并联、串联公式并调用 math.gcd 约分。这与 Fraction 的数学含义完全一致，但对象更轻，运算路径更短。

实际实现选择第二种方案。

最小电容器数量剪枝

令 $S_k$ 表示最少需要 $k$ 个电容器才能构造出的新电容值集合，known 表示之前所有层已经出现过的电容值。初始：

$$ S_1=\left\{\frac{1}{1}\right\} $$

计算第 $n$ 层时，把 $i$ 个电容器的值和 $n-i$ 个电容器的值组合：

$$ 1 \le i \le \left\lfloor\frac{n}{2}\right\rfloor $$

只遍历到一半是因为并联和串联都满足交换律，$(i,n-i)$ 与 $(n-i,i)$ 会产生同一批组合。

生成候选集合后执行：

$$ S_n \leftarrow S_n \setminus known $$

这个剪枝是正确的：如果某个子电路电容值已经可以用更少电容器构造，那么在任何更大电路中都可以把该子电路替换为更小的等效子电路，最终总电容不变、使用电容器数量更少。因此，一个首次在第 $n$ 层出现的新电容值，不需要依赖任何非最小表示的子电路。

最终：

$$ D(n)=\sum_{k=1}^{n}|S_k| $$

四、复杂度分析

设 $m_k=|S_k|$。第 $n$ 层需要组合的子电路对数约为：

$$ \sum_{i=1}^{\lfloor n/2\rfloor} m_i m_{n-i} $$

每个组合只做常数次整数乘法、加法、gcd 和集合插入。由于 $n=18$ 很小，主要成本来自集合规模，而最小电容器数量剪枝能显著减少无用状态。

空间复杂度为 $O(D(n))$，需要保存所有首次出现的有理数值。对于 $n=18$，该规模为数百万级，Python 的集合可以承受。

五、代码实现与说明

"""Project Euler Problem 155: Counting Capacitor Circuits.

Count the distinct total capacitance values obtainable with up to a given
number of identical capacitors.
"""

from __future__ import annotations

import argparse
from math import gcd
from time import perf_counter

Value = tuple[int, int]

开头定义题目说明、导入命令行解析、最大公约数和计时工具。Value 是电容值的统一类型：一个已经约分的正有理数 (numerator, denominator)。

def normalize(numerator: int, denominator: int) -> Value:
    """Return a positive rational number in lowest terms."""
    common = gcd(numerator, denominator)
    return numerator // common, denominator // common

normalize 用最大公约数约分，保证同一个有理数只有一种元组表示。

def add_values(first: Value, second: Value) -> Value:
    """Return the parallel combination of two normalized capacitance values."""
    first_num, first_den = first
    second_num, second_den = second
    return normalize(
        first_num * second_den + second_num * first_den,
        first_den * second_den,
    )


def series_values(first: Value, second: Value) -> Value:
    """Return the series combination of two normalized capacitance values."""
    first_num, first_den = first
    second_num, second_den = second
    denominator = first_num * second_den + second_num * first_den
    return normalize(first_num * second_num, denominator)

add_values 对应并联公式，series_values 对应串联公式。这两个函数也用于小规模测试，确认基础运算没有偏差。

def build_minimal_value_sets(limit: int) -> list[set[Value]]:
    """Build capacitance values by the smallest number of capacitors needed.

    A value that is already obtainable with fewer capacitors is discarded from
    later buckets. Replacing such a sub-circuit by its smaller equivalent never
    changes the total capacitance, so discarded values cannot be needed to form
    a genuinely new value with a larger total.
    """
    if limit < 1:
        return [set()]

    values_by_size: list[set[Value]] = [set() for _ in range(limit + 1)]
    values_by_size[1].add((1, 1))
    known_values: set[Value] = {(1, 1)}

build_minimal_value_sets 是主动态规划。values_by_size[k] 保存最少使用 $k$ 个电容器才能得到的值，known_values 保存所有已经出现过的值。limit < 1 时返回空占位；正常情况下第 1 层只有单个电容值 (1, 1)。

    for total_size in range(2, limit + 1):
        current_values: set[Value] = set()

        for left_size in range(1, total_size // 2 + 1):
            right_size = total_size - left_size
            left_values = values_by_size[left_size]
            right_values = values_by_size[right_size]

外层按总电容器数量递推。内层枚举拆分方式 left_size + right_size = total_size，只枚举到一半以利用交换律去重。

            if left_size == right_size:
                left_list = list(left_values)
                for index, first in enumerate(left_list):
                    first_num, first_den = first
                    for second in left_list[index:]:
                        second_num, second_den = second
                        shared_den = first_den * second_den
                        sum_num = first_num * second_den + second_num * first_den
                        common = gcd(sum_num, shared_den)
                        current_values.add((sum_num // common, shared_den // common))

                        prod_num = first_num * second_num
                        common = gcd(prod_num, sum_num)
                        current_values.add((prod_num // common, sum_num // common))

当左右两边使用同样多的电容器时，两个集合相同。代码只遍历 index 之后的元素，避免同一对子电路被反向重复处理。每对子电路分别生成并联值和串联值，并立即约分加入当前层候选集合。

            else:
                for first in left_values:
                    first_num, first_den = first
                    for second in right_values:
                        second_num, second_den = second
                        shared_den = first_den * second_den
                        sum_num = first_num * second_den + second_num * first_den
                        common = gcd(sum_num, shared_den)
                        current_values.add((sum_num // common, shared_den // common))

                        prod_num = first_num * second_num
                        common = gcd(prod_num, sum_num)
                        current_values.add((prod_num // common, sum_num // common))

当左右数量不同，两个集合不同，直接做笛卡尔积组合。公式与前一段一致，只是无需处理同集合内的反向重复。

        current_values.difference_update(known_values)
        values_by_size[total_size] = current_values
        known_values.update(current_values)

    return values_by_size

当前层候选值生成后，删除之前已经可达的值，只保留首次出现的值。随后更新当前层集合和全局已知集合。

def count_distinct_capacitances(limit: int = 18) -> int:
    """Return D(limit), the number of distinct values using up to limit capacitors."""
    values_by_size = build_minimal_value_sets(limit)
    return sum(len(values) for values in values_by_size)


def solve() -> int:
    """Return the answer for the target problem."""
    return count_distinct_capacitances(18)

count_distinct_capacitances 把所有层的首次出现数量相加，即得到 $D(limit)$。solve 固定调用目标规模 $18$。

def run_self_tests() -> None:
    """Run sample and small-scale checks."""
    expected_counts = {
        1: 1,
        2: 3,
        3: 7,
        4: 15,
    }
    for limit, expected in expected_counts.items():
        actual = count_distinct_capacitances(limit)
        if actual != expected:
            raise AssertionError(f"D({limit}) expected {expected}, got {actual}")

    if add_values((1, 1), (1, 2)) != (3, 2):
        raise AssertionError("Parallel operation check failed")
    if series_values((1, 1), (1, 2)) != (1, 3):
        raise AssertionError("Series operation check failed")

run_self_tests 覆盖题面给出的 $D(1)$、$D(2)$、$D(3)$，并加入直接枚举可确认的 $D(4)$。后两条断言检查并联和串联公式的基本运算。

def benchmark(repetitions: int, limit: int) -> None:
    """Run repeated timings and print the average and maximum runtime."""
    timings: list[float] = []
    last_answer = None
    for index in range(1, repetitions + 1):
        start = perf_counter()
        last_answer = count_distinct_capacitances(limit)
        elapsed = perf_counter() - start
        timings.append(elapsed)
        print(f"Run {index}: answer={last_answer} time={elapsed:.3f}s")

    average = sum(timings) / len(timings)
    maximum = max(timings)
    print(f"Average: {average:.3f}s")
    print(f"Maximum: {maximum:.3f}s")

benchmark 用于重复计时，确认目标规模运行时间稳定低于要求。

def parse_args() -> argparse.Namespace:
    """Parse command-line arguments."""
    parser = argparse.ArgumentParser(description="Solve Project Euler 155.")
    parser.add_argument("--limit", type=int, default=18, help="capacitor limit")
    parser.add_argument("--test", action="store_true", help="run self tests")
    parser.add_argument("--benchmark", type=int, default=0, help="number of timed runs")
    return parser.parse_args()


def main() -> None:
    """Run the solver, tests, or benchmark from the command line."""
    args = parse_args()

    if args.test:
        run_self_tests()
        print("Self tests passed")
        return

    if args.benchmark:
        benchmark(args.benchmark, args.limit)
        return

    start = perf_counter()
    answer = count_distinct_capacitances(args.limit)
    elapsed = perf_counter() - start
    print(f"Answer: {answer}")
    print(f"Time: {elapsed:.3f}s")


if __name__ == "__main__":
    main()

命令行入口支持三种模式：默认求解、--test 运行样例和小规模检查、--benchmark 重复计时。默认 --limit 为 $18$，也可以临时传入较小规模用于调试。

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页