题目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

1. /*
   
2. 答案：3857447
   
3. */
   
4. #include <iostream>
   
5. #include <set>
   
6. using namespace std;
   
7. 
   
8. int gcd(int a, int b)
   
9. {
   
10.   int c;
    
11.   while (a != 0)
    
12.   {
    
13.     c = a;
    
14.     a = b % a;
    
15.     b = c;
    
16.   }
    
17.   return b;
    
18. }
    
19. 
    
20. struct Rational
    
21. {
    
22.   int num;
    
23.   int den;
    
24.   Rational(int n = 0, int d = 1)
    
25.   {
    
26.     int g = gcd(n, d);
    
27.     num = n / g;
    
28.     den = d / g;
    
29.   }
    
30.   bool operator<(const Rational& r) const
    
31.   {
    
32.     return (num * r.den < r.num* den);
    
33.   }
    
34. };
    
35. 
    
36. const int n = 18;//电容的总数
    
37. set<Rational> caps[n + 1];//caps[i]为由i个电容通过各种联法得到的所有电容值
    
38. set<Rational> uniq;//合并电容值
    
39. 
    
40. int main(void)
    
41. {
    
42.   caps[1].insert(Rational(1, 1));
    
43.   uniq.insert(Rational(1, 1));
    
44.   for (int i = 2; i <= n; ++i)
    
45.   {
    
46.     set<Rational>& c = caps[i];
    
47.     for (int j = 1; j <= i / 2; ++j)
    
48.     {
    
49.       set<Rational>& a = caps[j];
    
50.       set<Rational>& b = caps[i - j];
    
51.       for (set<Rational>::const_iterator ia = a.begin(); ia != a.end(); ++ia)
    
52.       {
    
53.         for (set<Rational>::const_iterator ib = b.begin(); ib != b.end(); ++ib)
    
54.         {
    
55.           int z = ia->num * ib->den + ia->den * ib->num;
    
56.           c.insert(Rational(ia->num * ib->num, z));//串联
    
57.           c.insert(Rational(z, ia->den * ib->den));//并联
    
58.         }
    
59.       }
    
60.     }
    
61.     for (set<Rational>::const_iterator ic = c.begin(); ic != c.end(); ++ic)
    
62.       uniq.insert(*ic);
    
63.   }
    
64.   cout << "D(" << n << ")=" << uniq.size() << endl;
    
65.   return 0;
    
66. }
    

复制代码

gunjang

1. from math import gcd
   
2. def parallel(a,b): #串联
   
3. #a=a[0]/a[1];b=b[0]/b[1];return a+b
   
4.     a0 = a[1]*b[0]+a[0]*b[1]
   
5.     a1 = a[1]*b[1]
   
6.     g = gcd(a0, a1)
   
7.     return (a0//g, a1//g)
   
8. 
   
9. def series(a,b): #并联
   
10. #a/c, b/d => c/a+d/b => cb+ad/ab = ab/(cb+ad)
    
11. #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]
    
12.     a0 = a[0]*b[0]
    
13.     a1 = a[1]*b[0]+a[0]*b[1]
    
14.     g = gcd(a0, a1)
    
15.     return (a0//g, a1//g)
    
16. 
    
17. print(parallel((60,1),(60,1))) #120
    
18. print(series((60,1),(60,1))) #30
    
19. 
    
20. maxn = 18
    
21. Cn = [set([]) for i in range(19)]
    
22. Cn[1] = {(60,1)}
    
23. for n in range(2, maxn+1):
    
24.     r = set()
    
25.     for i in range(1, (n//2) +1):
    
26.         for a in Cn[i]:
    
27.             for b in Cn[n-i]:
    
28.                 r.add(parallel(a,b))
    
29.                 r.add(series(a,b))
    
30.     Cn[n] = r
    
31. 
    
32. r = set()
    
33. for c in Cn:
    
34.     r = r.union(c)
    
35. print(18, len(r)) #3857447
    
36. #算法没有优化，花费了大概1分钟。。。

复制代码