题目155：计算电容电路

欧拉计划

Counting Capacitor Circuits

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 C₁, C₂ etc in parallel, the total capacitance is C_T = C₁ + C₂ +...,
whereas when connecting them in series, the overall capacitance is given by:

题目：

在电路中，使用大小为 C 的电容若干只。

这些电容能并联或串联地形成子单元，一个子单元又可以和别的电容或子单元，以并联或串联地形成更大的子单元，如此反复进而形成整个电路。

以这个方式来连接 n 个相同的电容，我们能使整个电路拥有不同的电容值，这些电容值会有个大小范围。比如，使用 3 个 60F 的电容，我们可以组成下面七种总电容不同的电路：

如果我们定义 D(n) 为总电容值的个数，那么使用 n 个相同的电容，以不同的方式组成电路的话，我们可以计算出：D(1)=1, D(2)=3, D(3)=7 ...

请给出 D(18) 的值。

提示，电容并联的话，总电容为 C_T = C₁ + C₂ +...，串联的话，则为

迷雾少年

这越来越难了吧。。

guosl

/*
答案：3857447
*/
#include <iostream>
#include <set>
using namespace std;

int gcd(int a, int b)
{
  int c;
  while (a != 0)
  {
    c = a;
    a = b % a;
    b = c;
  }
  return b;
}

struct Rational
{
  int num;
  int den;
  Rational(int n = 0, int d = 1)
  {
    int g = gcd(n, d);
    num = n / g;
    den = d / g;
  }
  bool operator<(const Rational& r) const
  {
    return (num * r.den < r.num* den);
  }
};

const int n = 18;//电容的总数
set<Rational> caps[n + 1];//caps[i]为由i个电容通过各种联法得到的所有电容值
set<Rational> uniq;//合并电容值

int main(void)
{
  caps[1].insert(Rational(1, 1));
  uniq.insert(Rational(1, 1));
  for (int i = 2; i <= n; ++i)
  {
    set<Rational>& c = caps[i];
    for (int j = 1; j <= i / 2; ++j)
    {
      set<Rational>& a = caps[j];
      set<Rational>& b = caps[i - j];
      for (set<Rational>::const_iterator ia = a.begin(); ia != a.end(); ++ia)
      {
        for (set<Rational>::const_iterator ib = b.begin(); ib != b.end(); ++ib)
        {
          int z = ia->num * ib->den + ia->den * ib->num;
          c.insert(Rational(ia->num * ib->num, z));//串联
          c.insert(Rational(z, ia->den * ib->den));//并联
        }
      }
    }
    for (set<Rational>::const_iterator ic = c.begin(); ic != c.end(); ++ic)
      uniq.insert(*ic);
  }
  cout << "D(" << n << ")=" << uniq.size() << endl;
  return 0;
}

gunjang

from math import gcd
def parallel(a,b): #串联
#a=a[0]/a[1];b=b[0]/b[1];return a+b
    a0 = a[1]*b[0]+a[0]*b[1]
    a1 = a[1]*b[1]
    g = gcd(a0, a1)
    return (a0//g, a1//g)

def series(a,b): #并联
#a/c, b/d => c/a+d/b => cb+ad/ab = ab/(cb+ad)
#1/(a[1]/a[0] + b[1]/b[0]) = 1/(a[1]*b[0]+a[0]*b[1] /a[0]*b[0]) = a[0]*b[0] / a[1]*b[0]+a[0]*b[1]
    a0 = a[0]*b[0]
    a1 = a[1]*b[0]+a[0]*b[1]
    g = gcd(a0, a1)
    return (a0//g, a1//g)

print(parallel((60,1),(60,1))) #120
print(series((60,1),(60,1))) #30

maxn = 18
Cn = [set([]) for i in range(19)]
Cn[1] = {(60,1)}
for n in range(2, maxn+1):
    r = set()
    for i in range(1, (n//2) +1):
        for a in Cn[i]:
            for b in Cn[n-i]:
                r.add(parallel(a,b))
                r.add(series(a,b))
    Cn[n] = r

r = set()
for c in Cn:
    r = r.union(c)
print(18, len(r)) #3857447
#算法没有优化，花费了大概1分钟。。。