题目155：计算电容电路
Counting Capacitor CircuitsAn 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 C1, C2 etc in parallel, the total capacitance is CT = C1 + C2 +...,
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) 的值。
提示，电容并联的话，总电容为 CT = C1 + C2 +...，串联的话，则为
这越来越难了吧。。 本帖最后由 guosl 于 2022-9-21 20:42 编辑
/*
答案：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;//caps为由i个电容通过各种联法得到的所有电容值
set<Rational> uniq;//合并电容值
int main(void)
{
caps.insert(Rational(1, 1));
uniq.insert(Rational(1, 1));
for (int i = 2; i <= n; ++i)
{
set<Rational>& c = caps;
for (int j = 1; j <= i / 2; ++j)
{
set<Rational>& a = caps;
set<Rational>& b = caps;
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;
}
本帖最后由 永恒的蓝色梦想 于 2020-7-15 22:29 编辑
from math import gcd
def parallel(a,b): #串联
#a=a/a;b=b/b;return a+b
a0 = a*b+a*b
a1 = a*b
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/a + b/b) = 1/(a*b+a*b /a*b) = a*b / a*b+a*b
a0 = a*b
a1 = a*b+a*b
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 = ) for i in range(19)]
Cn = {(60,1)}
for n in range(2, maxn+1):
r = set()
for i in range(1, (n//2) +1):
for a in Cn:
for b in Cn:
r.add(parallel(a,b))
r.add(series(a,b))
Cn = r
r = set()
for c in Cn:
r = r.union(c)
print(18, len(r)) #3857447
#算法没有优化，花费了大概1分钟。。。
页:
[1]