The problem asks for \(D(18)\), the number of distinct equivalent capacitances that can be built from at most 18 identical capacitors using only series and parallel connections. Because every capacitor has the same base capacitance \(C\), the absolute unit is irrelevant for counting: dividing every circuit value by \(C\) turns the problem into one about unit capacitors of value \(1\).
So the real task is not to count circuit shapes, but to count distinct rational numbers obtainable from repeated series/parallel composition. Different wiring trees can lead to the same final value, so exact deduplication is the central issue.
The implementations solve the problem with dynamic programming over the number of capacitors, while storing each capacitance exactly as a reduced fraction.
If two subcircuits have normalized capacitances \(x\) and \(y\), then the two physical combination rules are
$$P(x,y)=x+y \qquad \text{(parallel)},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{(series)}.$$
Starting from the single value \(1\), these rules always produce positive rational numbers. That is why the implementations never use floating-point arithmetic: every reachable capacitance can be stored exactly as a reduced fraction \(\frac{p}{q}\).
Let \(E_n\) be the set of normalized capacitances obtainable with exactly \(n\) capacitors, and let
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
The base case is immediate:
$$E_1=\{1\}.$$
Now consider any circuit that uses exactly \(n\ge 2\) capacitors. Its topmost connection is either series or parallel, so it splits the circuit into two smaller subcircuits using \(a\) and \(b\) capacitors with
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
Therefore every value in \(E_n\) must arise by combining some \(x\in E_a\) and \(y\in E_b\). This gives a complete recursive description of the search space.
The key invariant used by all three implementations is reciprocal closure. For unit capacitors, exchanging series and parallel everywhere in a circuit changes its value from \(x\) to \(\frac1x\). So if a value belongs to \(E_n\), its reciprocal also belongs to \(E_n\).
This means the algorithm does not need to generate \(P(x,y)\) and \(S(x,y)\) separately. It is enough to generate the parallel sum
$$p=x+y$$
and also insert its reciprocal \(\frac1p\). Why does that cover the series case? Because if \(x\in E_a\) and \(y\in E_b\), then by reciprocal closure \(\frac1x\in E_a\) and \(\frac1y\in E_b\) as well, and
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
So the implemented recurrence can be written as
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
where \(\operatorname{red}\) means reducing every fraction to lowest terms and deleting duplicates.
The first layers already show all of the important ideas.
With one capacitor,
$$E_1=\{1\}.$$
For \(n=2\), the only split is \(1+1\). Combining \(1\) with \(1\) gives
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
so
$$E_2=\left\{2,\frac12\right\}.$$
For \(n=3\), the only relevant split is \(1+2\). Combining \(1\) with the two values in \(E_2\) gives
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac{2}{3}.$$
Hence
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
Taking the union up to 3 capacitors,
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
so
$$D(3)=7.$$
This small case is exactly the same recurrence that is used all the way up to \(n=18\).
The C++, Python, and Java implementations represent every capacitance as a numerator-denominator pair in lowest terms. If \(x=\frac{u}{v}\) and \(y=\frac{r}{s}\), then the parallel combination is
$$x+y=\frac{us+rv}{vs},$$
after which the result is reduced by dividing both numerator and denominator by their greatest common divisor. This canonical representation guarantees that equal capacitances compare equal even when they come from different circuit trees.
The implementation builds \(E_1,E_2,\dots,E_{18}\) in order. For a fixed \(n\), it enumerates splits \(a+b=n\) only with \(a\le b\), because swapping the left and right subcircuits does not create a new capacitance. For each pair of exact layers, it combines every value from the first with every value from the second, inserts \(x+y\), and also inserts its reciprocal unless the value is \(1\) and would duplicate itself.
When the split is symmetric, \(a=b\), there is an additional mirror symmetry inside that layer pair. One implementation skips those mirrored pairs during generation; the others let the set-based deduplication remove them later. The mathematical result is the same in every language.
After generating all candidates for exactly \(n\) capacitors, the implementation removes duplicates inside that layer and then merges the layer into a global union. The final answer is not \(|E_{18}|\), but
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
because the problem asks for all distinct capacitances obtainable with up to 18 capacitors.
Let \(m_n=|E_n|\). For a fixed \(n\), the dominant work is the number of cross-layer pairs examined:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
Each such pair produces one reduced sum and, in general, one reciprocal. After that, duplicates must be removed. In the sort-based version this costs \(O(T_n\log T_n)\) for the layer; in the hash-set versions insertion is expected near-linear in the number of generated candidates, with the same mathematical set size at the end.
Total memory is \(O\!\left(\sum_{k=1}^{18} m_k\right)\), because all exact layers must remain available for later splits, and the global union must also be stored. The growth is combinatorial, but for \(n=18\) the recurrence is still practical precisely because the code exploits symmetry, reciprocal closure, and exact deduplication.
Gesucht ist \(D(18)\), also die Anzahl verschiedener Ersatzkapazitäten, die sich mit höchstens 18 identischen Kondensatoren durch Reihen- und Parallelschaltungen erzeugen lassen. Da alle Bauteile denselben Grundwert \(C\) haben, spielt die absolute Einheit für die Zählung keine Rolle: Teilt man jede Gesamtkapazität durch \(C\), arbeitet man nur noch mit Einheitskondensatoren vom Wert \(1\).
Man zählt also nicht Schaltpläne als solche, sondern verschiedene rationale Werte. Unterschiedliche Schaltungsbäume können denselben Endwert liefern; genau deshalb sind exakte Bruchdarstellung und konsequente Deduplikation der Kern der Lösung.
Die Implementierungen verwenden dynamische Programmierung über die Anzahl der Kondensatoren und speichern jede erreichbare Kapazität als vollständig gekürzten Bruch.
Haben zwei Teilschaltungen die normierten Kapazitäten \(x\) und \(y\), dann gelten die beiden physikalischen Verknüpfungen
$$P(x,y)=x+y \qquad \text{(parallel)},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{(in Reihe)}.$$
Ausgehend vom Startwert \(1\) entstehen dadurch immer positive rationale Zahlen. Darum arbeiten die Programme mit exakter Ganzzahlarithmetik statt mit Gleitkommazahlen: Jeder erreichbare Wert wird als reduzierter Bruch \(\frac{p}{q}\) gespeichert.
Sei \(E_n\) die Menge aller normierten Kapazitäten, die mit genau \(n\) Kondensatoren erreichbar sind. Außerdem sei
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
Der Anfang ist trivial:
$$E_1=\{1\}.$$
Verwendet eine Schaltung genau \(n\ge 2\) Kondensatoren, dann ist ihre oberste Verbindung entweder eine Reihen- oder eine Parallelschaltung. Damit zerfällt die Schaltung in zwei kleinere Teilschaltungen mit \(a\) bzw. \(b\) Kondensatoren und
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
Also muss jeder Wert aus \(E_n\) aus einer Kombination von \(x\in E_a\) und \(y\in E_b\) hervorgehen. Genau diese Zerlegung bildet die dynamische Programmierung ab.
Der entscheidende Invariant ist die Abgeschlossenheit unter dem Kehrwert. Bei Einheitskondensatoren führt das Vertauschen von Reihen- und Parallelschaltung an jedem inneren Knoten dazu, dass sich ein Wert \(x\) in \(\frac1x\) verwandelt. Also gilt: Liegt \(x\) in \(E_n\), dann liegt auch \(\frac1x\) in \(E_n\).
Darum müssen die Programme die beiden Formeln \(P(x,y)\) und \(S(x,y)\) nicht getrennt erzeugen. Es genügt, zunächst
$$p=x+y$$
zu berechnen und zusätzlich den Kehrwert \(\frac1p\) einzufügen. Dass dadurch auch der Reihenfall vollständig erfasst wird, sieht man an
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
Da wegen der Reziprozitäts-Abgeschlossenheit auch \(\frac1x\in E_a\) und \(\frac1y\in E_b\) vorhanden sind, reicht die implementierte Rekursion
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
wobei \(\operatorname{red}\) das Kürzen aller Brüche und das Entfernen von Duplikaten bezeichnet.
Schon die ersten Ebenen zeigen die gesamte Struktur.
Mit einem Kondensator gilt
$$E_1=\{1\}.$$
Für \(n=2\) existiert nur die Zerlegung \(1+1\). Aus \(1\) und \(1\) entstehen
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
also
$$E_2=\left\{2,\frac12\right\}.$$
Für \(n=3\) bleibt nur die Zerlegung \(1+2\). Kombiniert man \(1\) mit den beiden Werten aus \(E_2\), erhält man
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23.$$
Damit
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
Die Vereinigung bis 3 ist also
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
und folglich
$$D(3)=7.$$
Genau diese Rekursion wird anschließend unverändert bis \(n=18\) fortgesetzt.
Die C++-, Python- und Java-Implementierungen speichern jede Kapazität als Zähler-Nenner-Paar in vollständig gekürzter Form. Sind \(x=\frac{u}{v}\) und \(y=\frac{r}{s}\), dann ist die Parallelschaltung
$$x+y=\frac{us+rv}{vs},$$
wobei anschließend mit dem größten gemeinsamen Teiler gekürzt wird. So werden gleiche Kapazitäten unabhängig von ihrer Entstehung als exakt derselbe Zustand erkannt.
Die Implementierung erzeugt nacheinander \(E_1,E_2,\dots,E_{18}\). Für festes \(n\) werden nur Zerlegungen \(a+b=n\) mit \(a\le b\) betrachtet, denn das Vertauschen der beiden Teilbäume liefert keine neue Kapazität. Für jedes Wertepaar aus den beiden Ebenen werden \(x+y\) und zusätzlich dessen Kehrwert eingefügt; nur beim Wert \(1\) wäre der Kehrwert identisch und damit überflüssig.
Im symmetrischen Fall \(a=b\) gibt es innerhalb dieser Paarung nochmals Spiegelduplikate. Eine Implementierung überspringt sie schon während der Erzeugung, die anderen verlassen sich auf die Mengendarstellung zur späteren Deduplikation. Inhaltlich berechnen alle drei Varianten dieselbe Menge.
Nachdem alle Kandidaten für genau \(n\) Kondensatoren erzeugt sind, werden Duplikate innerhalb dieser Ebene entfernt und die verbleibenden Werte in eine globale Vereinigungsmenge übernommen. Die gesuchte Antwort ist also nicht \(|E_{18}|\), sondern
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
weil die Aufgabe alle Ersatzkapazitäten mit bis zu 18 Kondensatoren verlangt.
Bezeichne \(m_n=|E_n|\). Für ein festes \(n\) dominiert die Anzahl der betrachteten Ebenenpaare:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
Jedes solche Paar liefert eine reduzierte Summe und im Allgemeinen zusätzlich deren Kehrwert. Danach müssen Duplikate entfernt werden. In der sortierbasierten Variante kostet das auf dieser Ebene \(O(T_n\log T_n)\); in den hashbasierten Varianten sind die Einfügungen erwartungsgemäß näherungsweise linear in der Zahl der erzeugten Kandidaten.
Der Speicherbedarf beträgt \(O\!\left(\sum_{k=1}^{18} m_k\right)\), weil alle exakten Ebenen für spätere Zerlegungen erhalten bleiben müssen und zusätzlich die globale Vereinigung gespeichert wird. Das Wachstum ist kombinatorisch, bleibt für \(n=18\) aber handhabbar, weil Symmetrien, Reziprozitäts-Abgeschlossenheit und exakte Deduplikation konsequent genutzt werden.
Soruda \(D(18)\) istenir: yalnızca seri ve paralel bağlar kullanılarak, en fazla 18 özdeş kapasitörden elde edilebilen farklı eşdeğer kapasitans sayısı. Tüm kapasitörler aynı temel değere \(C\) sahip olduğundan, sayım açısından mutlak birim önemsizdir; bütün devreleri \(C\)'ye bölerek problemi değeri \(1\) olan birim kapasitörler üzerinde çözebiliriz.
Dolayısıyla asıl amaç devre topolojilerini değil, ortaya çıkabilen farklı rasyonel değerleri saymaktır. Farklı seri/paralel ağaçları aynı sonuca ulaşabildiği için, çözümün kalbi tam sayı aritmetiğiyle yapılan kesin tekilleştirmedir.
Uygulamalar, kapasitör sayısı üzerinde dinamik programlama kuruyor ve her eşdeğer kapasitansı sadeleştirilmiş bir kesir olarak saklıyor.
Normalize edilmiş değerleri \(x\) ve \(y\) olan iki alt devre için iki temel birleşim kuralı şudur:
$$P(x,y)=x+y \qquad \text{(paralel)},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{(seri)}.$$
Başlangıç değeri \(1\) olduğunda bu işlemler daima pozitif rasyonel sayılar üretir. Bu yüzden çözümler kayan nokta kullanmaz; erişilen her değer tam olarak \(\frac{p}{q}\) biçiminde, en sade haliyle tutulur.
\(E_n\), tam \(n\) kapasitör kullanılarak elde edilebilen normalize kapasitanslar kümesi olsun. Ayrıca
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|$$
tanımını yapalım. Başlangıç durumu
$$E_1=\{1\}$$
olur. Şimdi tam \(n\ge 2\) kapasitör içeren herhangi bir seri/paralel devreyi düşünelim. En üstteki son birleşim ya seridir ya da paraleldir; dolayısıyla devre, sırasıyla \(a\) ve \(b\) kapasitör kullanan iki alt devreye ayrılır ve
$$a+b=n,\qquad a\ge 1,\ b\ge 1$$
sağlanır. Bu yüzden \(E_n\) içindeki her değer, mutlaka bazı \(x\in E_a\) ve \(y\in E_b\) değerlerinin birleşiminden gelir. Dinamik programlama tam olarak bu ayrışımı dolaşır.
Üç çözümün de kullandığı temel değişmez, kümelerin tersine göre kapalı olmasıdır. Birim kapasitörlerden kurulu bir devrede, bütün iç düğümlerde seri ile paraleli yer değiştirirseniz eşdeğer değer \(x\)'ten \(\frac1x\)'e dönüşür. Yani \(x\in E_n\) ise \(\frac1x\in E_n\) de vardır.
Bu gözlem sayesinde kod, paralel ve seri formüllerini ayrı ayrı üretmek zorunda kalmaz. Sadece
$$p=x+y$$
hesaplanır ve ardından \(\frac1p\) de eklenir. Bunun seri durumu neden kapsadığını görmek için
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y)$$
eşitliğine bakmak yeterlidir. Çünkü tersine kapanıştan dolayı \(\frac1x\in E_a\) ve \(\frac1y\in E_b\) zaten mevcuttur. Böylece uygulanan yineleme
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right)$$
şekline indirgenir. Burada \(\operatorname{red}\), bütün kesirleri sadeleştirip tekrar edenleri atmaktır.
İlk birkaç katman bütün mantığı açıkça gösterir.
Bir kapasitör için
$$E_1=\{1\}.$$
\(n=2\) için tek ayrışım \(1+1\)'dir. \(1\) ile \(1\)'i birleştirince
$$1+1=2,\qquad \frac1{1+1}=\frac12$$
elde edilir; dolayısıyla
$$E_2=\left\{2,\frac12\right\}.$$
\(n=3\) için ilgili tek ayrışım \(1+2\)'dir. \(1\) değeri, \(E_2\)'deki iki değerle birleştirilince
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23$$
çıkar. Yani
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
O halde
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\}$$
ve sonuç olarak
$$D(3)=7$$
olur. Kodun 18'e kadar yaptığı iş bunun aynı kuralının daha büyük katmanlara uygulanmasıdır.
C++, Python ve Java uygulamaları her kapasitansı pay-payda çifti olarak ve en sade halinde tutar. Eğer \(x=\frac{u}{v}\) ve \(y=\frac{r}{s}\) ise paralel birleşim
$$x+y=\frac{us+rv}{vs}$$
olur; ardından pay ve payda en büyük ortak bölenle sadeleştirilir. Böylece farklı devre ağaçlarından gelse bile eşit kapasitanslar aynı kanonik gösterime düşer.
Uygulama \(E_1,E_2,\dots,E_{18}\) kümelerini sırayla kurar. Sabit bir \(n\) için yalnızca \(a+b=n\) ve \(a\le b\) olan ayrışımlar dolaşılır; çünkü sol ve sağ alt devreleri yer değiştirmek yeni bir değer üretmez. Her çift katman için tüm değer çiftleri denenir, \(x+y\) eklenir ve bu değer \(1\) değilse tersi de eklenir.
\(a=b\) olduğunda bu kez aynı katman içinde ayna simetrisi ortaya çıkar. Bir uygulama bu yansımış çiftleri üretim sırasında atlar; diğerleri set tekilleştirmesine bırakır. Matematiksel çıktı üç dilde de aynıdır.
Tam \(n\) kapasitörle üretilen adaylar hazırlandıktan sonra, önce bu katman içindeki tekrarlar temizlenir, sonra kalan değerler küresel birleşime eklenir. Yani aranan sonuç \(|E_{18}|\) değil,
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|$$
değeridir; çünkü soru 18'e kadar bütün kapasitör sayılarıyla elde edilen farklı kapasitansları sayar.
\(m_n=|E_n|\) olsun. Sabit bir \(n\) katmanı için baskın iş, katman çiftlerinin çarpımıdır:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
Her böyle çift tipik olarak bir sadeleştirilmiş toplam ve bir de ters değer üretir. Sonrasında tekrarlar temizlenir. Sıralama-temelli sürümde bu katman için maliyet \(O(T_n\log T_n)\) olur; hash-set temelli sürümlerde ise ekleme maliyeti beklenen olarak üretilen aday sayısına yakın doğrusal kalır.
Bellek kullanımı \(O\!\left(\sum_{k=1}^{18} m_k\right)\) düzeyindedir; çünkü daha sonraki ayrışımlar için bütün tam-katman kümeleri ve ayrıca küresel birleşim tutulur. Büyüme kombinatoriktir, ama simetri, tersine kapanış ve kesin tekilleştirme sayesinde \(n=18\) için pratiktir.
Se pide \(D(18)\), el número de capacitancias equivalentes distintas que pueden construirse con como máximo 18 condensadores idénticos usando solo conexiones en serie y en paralelo. Como todos los componentes tienen la misma capacitancia básica \(C\), la escala absoluta no afecta al conteo: al dividir todos los valores por \(C\), el problema se convierte en trabajar con condensadores unitarios de valor \(1\).
Por tanto, no se están contando topologías de circuitos, sino valores racionales distintos. Dos árboles de combinación diferentes pueden producir la misma capacitancia final, así que la deduplicación exacta es la parte esencial del método.
Las implementaciones usan programación dinámica sobre el número de condensadores y guardan cada valor alcanzable como una fracción reducida.
Si dos subcircuitos tienen capacitancias normalizadas \(x\) y \(y\), las dos reglas físicas de combinación son
$$P(x,y)=x+y \qquad \text{(paralelo)},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{(serie)}.$$
Partiendo del valor inicial \(1\), estas operaciones siempre producen números racionales positivos. Por eso el código evita la aritmética en coma flotante y representa cada capacitancia alcanzable exactamente como \(\frac{p}{q}\) en términos mínimos.
Sea \(E_n\) el conjunto de capacitancias normalizadas que se pueden obtener con exactamente \(n\) condensadores. Definimos además
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
El caso base es
$$E_1=\{1\}.$$
Ahora bien, cualquier circuito serie/paralelo que use exactamente \(n\ge 2\) condensadores tiene una combinación final en la raíz: o serie o paralelo. Esa última operación divide el circuito completo en dos subcircuitos más pequeños con \(a\) y \(b\) condensadores, donde
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
Por tanto, todo valor de \(E_n\) debe surgir al combinar algún \(x\in E_a\) con algún \(y\in E_b\). Esa descomposición es lo que recorre la programación dinámica.
El invariante clave usado por las tres implementaciones es el cierre por recíproco. Con condensadores unitarios, si en un circuito se intercambian todas las conexiones en serie por conexiones en paralelo y viceversa, un valor \(x\) se transforma en \(\frac1x\). Así, si \(x\in E_n\), entonces \(\frac1x\in E_n\) también.
Gracias a eso, el algoritmo no necesita generar por separado \(P(x,y)\) y \(S(x,y)\). Basta calcular
$$p=x+y$$
e insertar también \(\frac1p\). El caso en serie queda cubierto porque
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
Como el cierre recíproco garantiza que \(\frac1x\in E_a\) y \(\frac1y\in E_b\), la recurrencia que realmente implementa el código es
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
donde \(\operatorname{red}\) significa reducir todas las fracciones y eliminar duplicados.
Las primeras capas ya contienen toda la idea.
Con un condensador,
$$E_1=\{1\}.$$
Para \(n=2\), la única partición es \(1+1\). Al combinar \(1\) con \(1\) se obtiene
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
y por tanto
$$E_2=\left\{2,\frac12\right\}.$$
Para \(n=3\), la única partición relevante es \(1+2\). Al combinar \(1\) con los dos valores de \(E_2\), aparecen
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23.$$
Así,
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
La unión hasta 3 es
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
de modo que
$$D(3)=7.$$
El cálculo para \(18\) repite exactamente esta misma construcción capa por capa.
Las implementaciones en C++, Python y Java guardan cada capacitancia como un par numerador-denominador en forma irreducible. Si \(x=\frac{u}{v}\) y \(y=\frac{r}{s}\), entonces la combinación en paralelo es
$$x+y=\frac{us+rv}{vs},$$
y después se divide por el máximo común divisor. Esa forma canónica permite reconocer como iguales valores obtenidos por árboles de circuito distintos.
La implementación construye \(E_1,E_2,\dots,E_{18}\) en orden. Para un \(n\) fijo, solo recorre particiones \(a+b=n\) con \(a\le b\), porque intercambiar el subcircuito izquierdo y el derecho no crea una nueva capacitancia. Para cada par de capas exactas, prueba todas las parejas de valores, inserta \(x+y\) e inserta también su recíproco salvo cuando el valor ya coincide consigo mismo.
Cuando la partición es simétrica, \(a=b\), aparece una simetría adicional entre parejas reflejadas. Una implementación evita esas repeticiones durante la generación; las otras dejan que la estructura de conjunto elimine los duplicados después. El conjunto matemático final es el mismo.
Una vez generados todos los candidatos para exactamente \(n\) condensadores, se eliminan los repetidos dentro de esa capa y luego se incorporan a una unión global. Por eso la respuesta buscada no es \(|E_{18}|\), sino
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
ya que el enunciado pide todas las capacitancias distintas obtenibles con hasta 18 condensadores.
Sea \(m_n=|E_n|\). Para una capa fija \(n\), el trabajo dominante es el número de parejas entre capas exactas:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
Cada una de esas parejas genera una suma reducida y, en general, también un recíproco. Después hay que deduplicar. En la versión basada en ordenación eso cuesta \(O(T_n\log T_n)\) en esa capa; en las versiones con tablas hash, la inserción es aproximadamente lineal en el número de candidatos generados en promedio.
La memoria total es \(O\!\left(\sum_{k=1}^{18} m_k\right)\), porque todas las capas exactas deben conservarse para futuras particiones y además se mantiene la unión global. El crecimiento es combinatorio, pero para \(n=18\) sigue siendo viable gracias a la simetría, al cierre por recíproco y a la deduplicación exacta.
题目要求计算 \(D(18)\)：只使用串联和并联，两两递归组合，最多用 18 个完全相同的电容器时，究竟能得到多少种不同的等效电容。由于每个电容器的原始电容都是同一个常数 \(C\)，所以在“计数不同结果”这件事上，绝对单位并不重要；把所有结果都除以 \(C\) 之后，就可以把问题等价地改写成“单位电容为 \(1\) 的情形”。
因此我们真正要数的不是电路形状，而是能够出现的不同有理数值。不同的串并联树形结构可能对应同一个最终电容，这也是为什么实现必须使用精确分数表示，而不能靠浮点数近似。
三份实现都采用了按电容个数分层的动态规划，并把每一个可达值都保存为既约分数。
若两个子电路的归一化电容分别为 \(x\) 和 \(y\)，那么两种基本组合公式是
$$P(x,y)=x+y \qquad \text{（并联）},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{（串联）}.$$
从初始值 \(1\) 出发，反复应用这两个公式，只会得到正有理数。所以实现中完全没有必要使用浮点数；所有电容值都可以精确写成 \(\frac{p}{q}\) 的形式，并在存储前约成最简分数。
记 \(E_n\) 为恰好使用 \(n\) 个单位电容可以得到的所有归一化等效电容集合，再记
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
显然初始层是
$$E_1=\{1\}.$$
接下来考虑任意一个恰好使用 \(n\ge 2\) 个电容的串并联电路。它在最顶层一定有最后一次组合，这个根节点不是串联就是并联。于是整个电路必然可以拆成两个更小的子电路，分别用了 \(a\) 个和 \(b\) 个电容，并满足
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
这说明 \(E_n\) 中的任何值，都来自某个 \(x\in E_a\) 与某个 \(y\in E_b\) 的组合。也就是说，分层动态规划并不是一种近似，而是对所有合法电路的完整枚举方式。
这道题最关键的数学性质，是“倒数闭包”。对由单位电容构成的串并联电路，如果把整棵组合树里的“串联”和“并联”全部互换，那么原来的值 \(x\) 会变成 \(\frac1x\)。因此只要 \(x\in E_n\)，就一定也有 \(\frac1x\in E_n\)。
有了这个性质，代码就不必分别显式生成并联公式 \(P(x,y)\) 和串联公式 \(S(x,y)\)。它只需要先算
$$p=x+y$$
然后把 \(\frac1p\) 也加入集合即可。为什么这样已经覆盖串联？因为
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
既然 \(E_a\) 和 \(E_b\) 都对倒数封闭，那么 \(\frac1x\in E_a\)、\(\frac1y\in E_b\) 也都存在，串联结果就会以“某个并联和的倒数”的形式自动出现。所以代码实际实现的递推可以写成
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
其中 \(\operatorname{red}\) 表示把所有分数约到最简并删除重复项。
前几层已经能完整展示递推的样子。
当只有一个电容时，
$$E_1=\{1\}.$$
当 \(n=2\) 时，唯一拆分是 \(1+1\)。用两个 \(1\) 组合得到
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
因此
$$E_2=\left\{2,\frac12\right\}.$$
当 \(n=3\) 时，只需要看拆分 \(1+2\)。把 \(1\) 分别与 \(E_2\) 中的两个值组合，就会得到
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23.$$
所以
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
再把前三层并起来：
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
于是
$$D(3)=7.$$
这就是程序在更大 \(n\) 上反复执行的同一套规则；真正困难的地方不在公式，而在于把所有重复值准确地合并掉。
C++、Python 和 Java 实现都会把每个电容值记成“分子、分母”二元组，并始终保持最简。如果 \(x=\frac{u}{v}\)、\(y=\frac{r}{s}\)，那么并联后是
$$x+y=\frac{us+rv}{vs},$$
随后再用最大公因数约分。这样一来，只要两个电路的等效电容真的相等，它们就会被压缩成完全相同的规范表示。
实现会从小到大逐层构造 \(E_n\)。对固定的 \(n\)，只枚举 \(a+b=n\) 且 \(a\le b\) 的拆分，因为左右子电路互换不会产生新的电容值。对于每个拆分，再枚举 \(E_a\) 与 \(E_b\) 中的所有值对，加入 \(x+y\)，并在一般情况下再加入它的倒数。
当 \(a=b\) 时，还会出现同层内部的镜像重复：选到 \((x,y)\) 与 \((y,x)\) 实际上没有区别。一份实现会在生成阶段直接跳过这些镜像；另外两份实现则交给集合去重。虽然去重时机不同，但数学上得到的是同一个集合。
每一层 \(E_n\) 生成完之后，都会先消除层内重复，再并入一个全局集合。最终返回的并不是 \(|E_{18}|\)，而是
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
因为题目要求的是“最多 18 个电容”时所有不同的等效电容数量。
设 \(m_n=|E_n|\)。那么在固定的第 \(n\) 层，主要工作量来自不同层之间的值对枚举：
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
每个值对通常会生成一个约分后的和以及一个倒数，之后还要去重。若采用“先收集再排序去重”的做法，这一层的代价是 \(O(T_n\log T_n)\)；若采用哈希集合，则平均插入代价接近按候选数线性增长。
总内存为 \(O\!\left(\sum_{k=1}^{18} m_k\right)\)，因为后续层仍然要访问所有较小的 \(E_k\)，同时全局并集也必须保留。虽然集合大小是组合式增长的，但 \(n=18\) 仍然可行，正是因为实现利用了左右对称性、倒数闭包以及精确分数去重。
Нужно найти \(D(18)\): сколько различных эквивалентных емкостей можно получить, используя не более 18 одинаковых конденсаторов и соединяя их только последовательно или параллельно. Поскольку все конденсаторы имеют одну и ту же базовую емкость \(C\), абсолютный масштаб для подсчета не важен: если разделить все значения на \(C\), задача сводится к работе с единичными конденсаторами со значением \(1\).
Тем самым мы считаем не схемные деревья сами по себе, а различные рациональные значения. Разные структуры соединения могут давать одну и ту же итоговую емкость, поэтому точное представление дробей и надежное удаление повторов здесь принципиальны.
Во всех трех реализациях используется динамическое программирование по числу конденсаторов, а каждая достижимая емкость хранится как несократимая дробь.
Если два подконтура имеют нормированные емкости \(x\) и \(y\), то физические формулы соединения таковы:
$$P(x,y)=x+y \qquad \text{(параллельно)},$$
$$S(x,y)=\frac{xy}{x+y} \qquad \text{(последовательно)}.$$
Начиная с единственного значения \(1\), эти операции всегда приводят к положительным рациональным числам. Поэтому реализации не используют числа с плавающей точкой: каждое достижимое значение точно представляется в виде сокращенной дроби \(\frac{p}{q}\).
Обозначим через \(E_n\) множество всех нормированных емкостей, достижимых ровно с \(n\) конденсаторами. Также введем
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
Базовый слой равен
$$E_1=\{1\}.$$
Теперь рассмотрим любой последовательный-параллельный контур, использующий ровно \(n\ge 2\) конденсаторов. На верхнем уровне у него есть последняя операция объединения: либо последовательная, либо параллельная. Значит, вся схема распадается на два меньших подконтура, использующих \(a\) и \(b\) конденсаторов, где
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
Следовательно, любой элемент \(E_n\) обязан возникать из некоторой пары \(x\in E_a\) и \(y\in E_b\). Это и дает полную рекуррентную структуру задачи.
Ключевой инвариант, который используют все реализации, состоит в замкнутости по обратной величине. Для схем из единичных конденсаторов, если во всем дереве заменить последовательные соединения параллельными и наоборот, значение \(x\) превратится в \(\frac1x\). Значит, из \(x\in E_n\) следует \(\frac1x\in E_n\).
Поэтому алгоритму не нужно независимо порождать и \(P(x,y)\), и \(S(x,y)\). Достаточно вычислить
$$p=x+y$$
и дополнительно добавить \(\frac1p\). Почему это покрывает последовательный случай? Потому что
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
А раз множества замкнуты относительно взятия обратного, то \(\frac1x\in E_a\) и \(\frac1y\in E_b\) уже присутствуют. Тем самым используемая в коде рекурсия имеет вид
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
где \(\operatorname{red}\) означает сокращение дробей и удаление дубликатов.
Первые уровни уже показывают всю механику метода.
Для одного конденсатора
$$E_1=\{1\}.$$
Для \(n=2\) есть только разбиение \(1+1\). Из \(1\) и \(1\) получаем
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
значит
$$E_2=\left\{2,\frac12\right\}.$$
Для \(n=3\) нужно рассмотреть только разбиение \(1+2\). Комбинируя \(1\) с двумя значениями из \(E_2\), получаем
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23.$$
Следовательно,
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
Тогда
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
и потому
$$D(3)=7.$$
Именно эта же рекурсия затем продолжается до \(n=18\).
Реализации на C++, Python и Java представляют каждую емкость парой «числитель-знаменатель» в несократимом виде. Если \(x=\frac{u}{v}\) и \(y=\frac{r}{s}\), то параллельное соединение равно
$$x+y=\frac{us+rv}{vs},$$
после чего дробь сокращается по наибольшему общему делителю. Благодаря этому одинаковые емкости, возникшие из разных деревьев схемы, совпадают буквально как одинаковые пары целых чисел.
Код последовательно строит множества \(E_1,E_2,\dots,E_{18}\). Для фиксированного \(n\) рассматриваются только разбиения \(a+b=n\) с условием \(a\le b\), поскольку перестановка левого и правого подконтура не дает нового значения. Для каждой пары слоев перебираются все пары элементов, добавляется \(x+y\), а затем обычно и его обратная величина.
Когда \(a=b\), возникает дополнительная зеркальная симметрия внутри одной и той же пары слоев: пары \((x,y)\) и \((y,x)\) эквивалентны. Одна реализация отбрасывает такие отраженные пары сразу, две другие удаляют дубликаты позже с помощью структур множеств. Итоговое математическое множество во всех случаях одинаково.
После генерации всех кандидатов для ровно \(n\) конденсаторов повторы внутри этого слоя удаляются, а затем слой объединяется с глобальным множеством. Поэтому искомый ответ — не \(|E_{18}|\), а
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
поскольку по условию нужно учитывать все емкости, достижимые с количеством конденсаторов от 1 до 18.
Обозначим \(m_n=|E_n|\). Тогда для фиксированного \(n\) основной объем работы определяется числом пар между слоями:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
Каждая такая пара обычно порождает одну сокращенную сумму и один обратный элемент, после чего требуется дедупликация. В варианте с сортировкой это стоит \(O(T_n\log T_n)\) на слой; в вариантах на хеш-множествах ожидаемое время вставок близко к линейному по числу сгенерированных кандидатов.
Полная память равна \(O\!\left(\sum_{k=1}^{18} m_k\right)\), потому что все предыдущие слои нужны для будущих разбиений, а глобальное объединение тоже должно храниться. Рост комбинаторный, но для \(n=18\) он остается практичным именно благодаря использованию симметрии, замкнутости по обратному значению и точного удаления повторов.
المطلوب هو حساب \(D(18)\)، أي عدد قيم السعة المكافئة المختلفة التي يمكن بناؤها باستخدام ما لا يزيد على 18 مكثفًا متماثلًا، مع السماح فقط بالتوصيل على التوالي أو على التوازي. وبما أن جميع المكثفات تملك السعة الأساسية نفسها \(C\)، فإن القيمة المطلقة للوحدة لا تؤثر في العد؛ فإذا قسمنا كل سعة ناتجة على \(C\)، أصبحت المسألة مكافئة للعمل على مكثفات وحدوية قيمتها \(1\).
لذلك فنحن لا نعد أشكال الدارات بحد ذاتها، بل نعد القيم الكسرية المختلفة التي يمكن الوصول إليها. وقد تؤدي أشجار توصيل مختلفة إلى السعة النهائية نفسها، ولهذا كان التمثيل الدقيق بالكسور والتخلص الصارم من التكرارات هو جوهر الحل.
تعتمد التطبيقات على برمجة ديناميكية بحسب عدد المكثفات، مع تخزين كل سعة قابلة للوصول على صورة كسر مختزل.
إذا كانت سعتا دائرتين فرعيتين بعد التطبيع هما \(x\) و\(y\)، فإن صيغة التوازي هي
$$P(x,y)=x+y,$$
أما صيغة التوالي فهي
$$S(x,y)=\frac{xy}{x+y}.$$
وبالانطلاق من القيمة الابتدائية \(1\)، فإن هاتين العمليتين تنتجان دائمًا أعدادًا نسبية موجبة. لهذا السبب لا تستخدم الشيفرة أعداد الفاصلة العائمة؛ فكل سعة يمكن تمثيلها بدقة على هيئة \(\frac{p}{q}\) في أبسط صورة.
لنرمز بـ \(E_n\) إلى مجموعة السعات المطبعة التي يمكن الحصول عليها باستعمال \(n\) مكثفات بالضبط، ولنعرّف أيضًا
$$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$$
حالة البداية مباشرة:
$$E_1=\{1\}.$$
والآن خذ أي دارة توالٍ/توازٍ تستعمل \(n\ge 2\) مكثفات. آخر عملية دمج عند الجذر لا بد أن تكون إما تواليًا وإما توازيًا، ولذلك تنقسم الدارة كلها إلى دائرتين فرعيتين أصغر تستعملان \(a\) و\(b\) مكثفات بحيث
$$a+b=n,\qquad a\ge 1,\ b\ge 1.$$
إذن كل عنصر في \(E_n\) لا بد أن ينتج من دمج قيمة \(x\in E_a\) مع قيمة \(y\in E_b\). هذه الملاحظة تعطي الوصف التكراري الكامل لجميع الدارات الممكنة.
الثابت الرياضي الأهم الذي تستغله الحلول الثلاثة هو الانغلاق تحت أخذ المقلوب. ففي الدارات المبنية من مكثفات وحدوية، إذا بدّلنا كل توصيل على التوالي إلى توازي، وكل توازي إلى توالٍ، فإن القيمة \(x\) تتحول إلى \(\frac1x\). لذلك إذا كان \(x\in E_n\)، فإن \(\frac1x\in E_n\) أيضًا.
بفضل هذه الحقيقة، لا تحتاج الخوارزمية إلى توليد \(P(x,y)\) و\(S(x,y)\) كل على حدة. يكفي أن تحسب
$$p=x+y$$
ثم تضيف أيضًا \(\frac1p\). ولماذا يغطي ذلك حالة التوالي؟ لأن
$$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$$
وبما أن الانغلاق تحت المقلوب يضمن وجود \(\frac1x\in E_a\) و\(\frac1y\in E_b\)، فإن سعة التوالي تظهر تلقائيًا بوصفها مقلوب مجموع مناسب. وهكذا تصبح العلاقة المستخدمة فعليًا في الشيفرة
$$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$$
حيث تشير \(\operatorname{red}\) إلى اختزال الكسور وحذف القيم المكررة.
تُظهر الطبقات الأولى الفكرة كاملة.
عند وجود مكثف واحد فقط،
$$E_1=\{1\}.$$
وعند \(n=2\)، لا يوجد إلا التقسيم \(1+1\). من دمج \(1\) مع \(1\) نحصل على
$$1+1=2,\qquad \frac1{1+1}=\frac12,$$
ومن ثم
$$E_2=\left\{2,\frac12\right\}.$$
وعند \(n=3\)، التقسيم الوحيد ذي الصلة هو \(1+2\). وبدمج \(1\) مع القيمتين الموجودتين في \(E_2\)، نحصل على
$$1+2=3,\qquad \frac13,$$
$$1+\frac12=\frac32,\qquad \frac23.$$
إذًا
$$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$$
وبأخذ الاتحاد حتى 3 مكثفات:
$$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$$
فنحصل على
$$D(3)=7.$$
والخوارزمية تكرر القاعدة نفسها حتى الوصول إلى \(18\) مكثفًا.
تمثل تطبيقات C++ وPython وJava كل سعة بزوج من البسط والمقام في أبسط صورة. فإذا كان \(x=\frac{u}{v}\) و\(y=\frac{r}{s}\)، فإن دمج التوازي يساوي
$$x+y=\frac{us+rv}{vs},$$
ثم يُختزل الناتج بالقاسم المشترك الأكبر. وبهذا تصبح القيم المتساوية الناتجة من أشجار دارات مختلفة متطابقة تمامًا في التمثيل.
تبني الشيفرة المجموعات \(E_1,E_2,\dots,E_{18}\) بالتدرج. وعند قيمة ثابتة لـ \(n\)، لا تُفحَص إلا التقسيمات \(a+b=n\) التي تحقق \(a\le b\)، لأن تبديل الدائرتين الفرعيتين لا ينتج قيمة جديدة. ولكل زوج من الطبقات الدقيقة تُجرَّب جميع أزواج القيم، ثم يُضاف \(x+y\) ويُضاف عادةً مقلوبه أيضًا.
وعندما يكون \(a=b\)، تظهر تماثلات معكوسة داخل الطبقة نفسها: الزوج \((x,y)\) لا يختلف عن \((y,x)\). إحدى التطبيقات تتجنب هذه الأزواج المتماثلة أثناء التوليد، بينما تتركها التطبيقات الأخرى لآلية إزالة التكرار داخل المجموعات. النتيجة الرياضية النهائية واحدة في جميع الأحوال.
بعد توليد جميع المرشحات الخاصة بالطبقة \(n\)، تُزال التكرارات داخل هذه الطبقة، ثم تُدمج القيم الباقية في اتحاد عالمي. ولهذا فإن الجواب المطلوب ليس \(|E_{18}|\)، بل
$$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$$
لأن نص المسألة يطلب كل السعات المختلفة التي يمكن الوصول إليها باستعمال حتى 18 مكثفًا.
إذا رمزنا إلى \(m_n=|E_n|\)، فإن العبء الأساسي في الطبقة \(n\) يأتي من عدد الأزواج بين الطبقات:
$$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$$
وكل زوج من هذا النوع يولد عادة مجموعًا مختزلًا ومقلوبًا له، ثم تأتي مرحلة إزالة التكرار. في النسخة المعتمدة على الفرز تكون كلفة الطبقة \(O(T_n\log T_n)\)، أما في النسخ المعتمدة على المجموعات المبنية على التجزئة فتكون الإضافة في المتوسط قريبة من الخطية في عدد المرشحات المتولدة.
أما الذاكرة فتساوي \(O\!\left(\sum_{k=1}^{18} m_k\right)\)، لأن جميع الطبقات السابقة يجب أن تبقى متاحة للانقسامات اللاحقة، كما يجب الاحتفاظ بالاتحاد العالمي أيضًا. النمو تركيبي، لكنه يظل عمليًا عند \(n=18\) لأن الشيفرة تستغل التماثل والانغلاق تحت المقلوب وإزالة التكرار الدقيقة.