For each nonnegative integer \(k\), define
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
The task is to choose a nondecreasing quadruple
$$0\le a\le b\le c\le d$$
so that
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
is as small as possible. Once such a quadruple is found, the required output is
$$g(n)=a^2+b^2+c^2+d^2.$$
A direct four-loop search is far too expensive for the target input, so the implementation turns the problem into a structured closest-sum search on pair sums.
The C++, Python, and Java implementations all use the same numerical strategy. They work with a small tolerance
$$\delta=10^{-3}$$
to build candidate regions around \(\pi\), then perform an exact closest search inside those regions.
The sequence \(f_n(k)=e^{k/n}-1\) is strictly increasing, so larger indices always produce larger terms. The implementation therefore samples only
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$$
This gives a finite array of candidate values in the relevant numerical window for the search. For the checkpoint \(n=200\), this bound is
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
The algorithm does not search arbitrary four-tuples beyond that working range; instead it relies on the monotonic growth of \(f_n\) together with the pruning rules below.
If we split the quadruple into two ordered pairs, then we may write
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
The original objective becomes
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$$
This is the standard meet-in-the-middle idea: instead of scanning all quadruples, build two collections of pair sums and then search for one value from each collection whose total is closest to \(\pi\).
Conceptually, one collection stores pair sums from the lower side of the target and the other stores pair sums from the upper side. After sorting both collections, the four-dimensional search collapses to a one-pass closest-pair sweep.
For the smaller pair sums the implementation enumerates pairs with \(a\le b\) and keeps only combinations that can still belong to a quadruple near \(\pi\). Two monotone inequalities drive the pruning:
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
The first inequality says that if even the quadruple \((a,a,a,a)\) already exceeds the admissible band, then every larger \(a\) is hopeless and the outer loop can stop.
The second inequality says that once \(a\) is fixed, if replacing the two missing entries by the largest currently allowed term \(f_n(b)\) already pushes the total above \(\pi+\delta\), then every larger \(b\) is also impossible. Because \(f_n\) is increasing, this justifies an early break in the inner loop.
The second collection is generated from the top down, using pairs with \(c\le d\). Here the implementation keeps only sums that lie in the opposite feasible band:
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
The middle inequality means that if even four copies of the current largest term stay below \(\pi-\delta\), then every smaller \(d\) will also stay too small, so the downward scan may stop.
The last inequality handles the inner loop: once \(d\) is fixed, if even the most optimistic completion with three copies of \(f_n(c)\) cannot reach the lower edge of the band, then decreasing \(c\) further only makes things worse, so the loop can break.
These inequalities do not solve the problem by themselves, but they dramatically shrink the lists before sorting.
After sorting both pair-sum lists in ascending order, the implementation performs a monotone sweep. One pointer moves through the lower list from left to right, while the other starts at the right end of the upper list and moves only leftward.
For each lower-side value \(x\), the algorithm adjusts the upper pointer until the sum crosses \(\pi\). At that crossing, only two neighboring candidates can matter: the last one below the target and the first one above it. Comparing those two possibilities is enough to update the best error
$$\left|x+y-\pi\right|.$$
Because neither pointer ever reverses direction, this stage is linear once the sorting is finished.
The pair-sum lists store only floating-point sums, not the contributing index pairs. That keeps memory usage manageable, but it means the indices must be reconstructed after the best two sums are found.
To do that, the implementation runs the same closest-two-sum procedure again on the base value array \(\{f_n(0),f_n(1),\dots,f_n(B)\}\): once with target equal to the selected lower pair sum, and once with target equal to the selected upper pair sum. This yields one ordered pair for each chosen sum.
The four recovered indices are then sorted, and the final quantity
$$g(n)=a^2+b^2+c^2+d^2$$
is computed directly.
For \(n=200\), the implementation uses the bound \(B=235\). The closest quadruple found by the algorithm is
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
The corresponding function values are approximately
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
Grouping them into two pairs gives
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
Their total is
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
which differs from \(\pi\) by about
$$9.06\times 10^{-9}.$$
Therefore
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
matching the checkpoint used by the implementations.
The C++, Python, and Java implementations follow the same pipeline.
First they precompute the monotone array \(f_n(0),f_n(1),\dots,f_n(B)\). Next they build two lists of pair sums: a lower-side list created by increasing indices from the left, and an upper-side list created by decreasing indices from the right. In both cases, monotonicity lets the loops stop early as soon as the pruning inequalities fail.
After sorting the two lists, the implementation performs a closest-sum sweep to find one value from each list whose total is nearest to \(\pi\). Because the lists contain only sums, the code then reconstructs the actual pairs by solving two additional closest-two-sum problems on the original one-dimensional value array. Finally it sorts the four recovered indices and returns the sum of their squares.
The entire method is numerical but tightly controlled: the same tolerance band is used while building candidate sums and while reconstructing the chosen pairs, and the checkpoint \(g(200)=64658\) verifies that the three language versions agree.
Let
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
and let \(P_-\) and \(P_+\) be the numbers of retained lower-side and upper-side pair sums. Computing the base array costs \(O(B)\) time and \(O(B)\) memory.
The pair-generation loops have a worst-case \(O(B^2)\) envelope, but the monotone breaks ensure that only the numerically relevant region is materialized. The dominant explicit work after pruning is sorting, which costs
$$O(P_-\log P_- + P_+\log P_+).$$
The closest-sum sweep is linear in the two list sizes, and the final index reconstruction adds only \(O(B)\) work. Hence the practical memory usage is
$$O(B+P_-+P_+),$$
and the dominant practical running time is the construction and sorting of the retained pair sums rather than an infeasible \(O(B^4)\) quadruple search.
Für jede nichtnegative ganze Zahl \(k\) sei
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
Gesucht ist ein nichtabsteigendes Tupel
$$0\le a\le b\le c\le d,$$
für das
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
minimal ist. Danach wird
$$g(n)=a^2+b^2+c^2+d^2$$
berechnet. Eine direkte Vierfachsuche ist für die Zielgröße zu teuer, daher formt die Lösung das Problem in eine strukturierte Suche über Paar-Summen um.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe numerische Strategie. Dabei wird mit der kleinen Toleranz
$$\delta=10^{-3}$$
ein enger Suchstreifen um \(\pi\) definiert, in dem alle Kandidaten erzeugt und geprüft werden.
Die Folge \(f_n(k)=e^{k/n}-1\) ist streng monoton wachsend. Daher erzeugt die Implementierung nur Werte im Bereich
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$$
Damit entsteht ein endliches Wertearray im numerisch relevanten Fenster der Suche. Für den Kontrollfall \(n=200\) gilt
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
Jenseits dieses Fensters wird nicht weiter gesucht; stattdessen kombiniert das Verfahren Monotonie mit den folgenden Abschneideregeln.
Teilt man das Tupel in zwei geordnete Paare, so setzt man
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
Das Optimierungsziel wird dadurch zu
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$$
Das ist der klassische Meet-in-the-middle-Gedanke: Statt alle Vierer-Tupel zu prüfen, baut man zwei Mengen von Paar-Summen auf und sucht anschließend ein Paar aus diesen Mengen, dessen Gesamtwert \(\pi\) möglichst nahe kommt.
Eine Liste repräsentiert die kleineren Teilbeträge, die andere die größeren. Nach dem Sortieren reduziert sich die vierdimensionale Suche auf einen einzigen linearen Sweep.
Für die kleinere Liste werden Paare mit \(a\le b\) erzeugt. Behalten werden nur Kombinationen, die noch zu einer Vierer-Summe nahe \(\pi\) ergänzt werden können. Die entscheidenden Ungleichungen sind
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
Die erste Bedingung bedeutet: Überschreitet bereits \((a,a,a,a)\) den erlaubten Streifen, dann sind alle größeren \(a\) ebenfalls unmöglich und die äußere Schleife kann abbrechen.
Die zweite Bedingung bedeutet: Ist \(a\) fest und würde schon die günstigste Fortsetzung mit drei Exemplaren von \(f_n(b)\) den Wert \(\pi+\delta\) überschreiten, dann sind alle größeren \(b\) ebenso ausgeschlossen. Wegen der Monotonie ist also ein früher Abbruch der inneren Schleife korrekt.
Die zweite Liste wird von oben nach unten mit Paaren \(c\le d\) aufgebaut. Dabei gelten die Gegenbedingungen
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
Die mittlere Ungleichung sagt: Liegt selbst \((d,d,d,d)\) noch unter \(\pi-\delta\), dann kann kein kleineres \(d\) die obere Kandidatenliste mehr erreichen, also darf die absteigende Schleife stoppen.
Die letzte Bedingung steuert die innere Schleife. Ist \(d\) fest und erreicht nicht einmal die optimistischste Ergänzung mit drei Kopien von \(f_n(c)\) die Unterkante des Suchstreifens, dann verschlechtern kleinere \(c\) die Lage nur weiter. Auch hier ist ein Abbruch gerechtfertigt.
Diese Regeln lösen das Problem nicht direkt, verkleinern aber die zu sortierenden Listen drastisch.
Nach dem Sortieren beider Paar-Summen-Listen verwendet die Implementierung einen monotonen Sweep. Ein Zeiger läuft die kleinere Liste von links nach rechts durch, ein zweiter beginnt am rechten Ende der größeren Liste und bewegt sich nur nach links.
Für jeden unteren Wert \(x\) wird der obere Zeiger so weit verschoben, bis die Summe den Wert \(\pi\) kreuzt. In diesem Moment können nur zwei Nachbarn relevant sein: der letzte Wert unterhalb des Ziels und der erste Wert oberhalb des Ziels. Der bessere dieser beiden Kandidaten aktualisiert den Fehler
$$\left|x+y-\pi\right|.$$
Da keiner der Zeiger seine Richtung wechselt, ist dieser Schritt nach dem Sortieren linear.
In den Paar-Listen werden nur Fließkomma-Summen gespeichert, nicht die zugehörigen Indexpärchen. Das spart Speicher, erfordert aber eine Rekonstruktion am Ende.
Dazu wendet die Implementierung dieselbe Zwei-Summen-Suche noch zweimal auf das eindimensionale Grundarray \(\{f_n(0),f_n(1),\dots,f_n(B)\}\) an: einmal mit dem Zielwert der gewählten unteren Paar-Summe und einmal mit dem Zielwert der gewählten oberen Paar-Summe. So erhält man für jede ausgewählte Summe ein geordnetes Indexpaar.
Diese vier Indizes werden sortiert, und anschließend wird
$$g(n)=a^2+b^2+c^2+d^2$$
direkt berechnet.
Für \(n=200\) verwendet die Implementierung die Schranke \(B=235\). Das gefundene beste Tupel ist
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
Die zugehörigen Funktionswerte sind näherungsweise
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
Als Paar-Summen ergibt das
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
Insgesamt erhält man
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
also einen Abstand von nur
$$9.06\times 10^{-9}$$
zu \(\pi\). Daher folgt
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
genau der Kontrollwert aus allen drei Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Verarbeitungskette.
Zuerst wird das monotone Feld \(f_n(0),f_n(1),\dots,f_n(B)\) vorab berechnet. Danach entstehen zwei Listen von Paar-Summen: eine untere Liste durch ansteigende Indizes von links und eine obere Liste durch absteigende Indizes von rechts. In beiden Fällen sorgen Monotonie und Ungleichungen dafür, dass Schleifen früh abbrechen können.
Nach dem Sortieren der beiden Listen führt die Implementierung einen Closest-Sum-Sweep aus und wählt einen Wert aus jeder Liste, deren Summe \(\pi\) am nächsten kommt. Weil die Listen nur Summen und keine Indizes enthalten, werden die beiden zugehörigen Paare anschließend durch zwei zusätzliche Zwei-Summen-Suchen im ursprünglichen Wertefeld rekonstruiert. Abschließend werden die vier Indizes sortiert und ihre Quadrate addiert.
Das Verfahren bleibt numerisch konsistent, weil dieselbe Toleranz sowohl beim Erzeugen der Kandidaten als auch bei der Rekonstruktion der ausgewählten Paare verwendet wird. Der Kontrollwert \(g(200)=64658\) bestätigt die Übereinstimmung der drei Sprachfassungen.
Sei
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
und seien \(P_-\) und \(P_+\) die Zahlen der behaltenen unteren bzw. oberen Paar-Summen. Das Vorberechnen des Grundarrays kostet \(O(B)\) Zeit und \(O(B)\) Speicher.
Die verschachtelten Schleifen zur Paarerzeugung haben im Worst Case die Hülle \(O(B^2)\), doch wegen der monotone Abschneideregeln wird nur der numerisch relevante Bereich materialisiert. Der dominierende explizite Aufwand nach dem Abschneiden ist das Sortieren mit
$$O(P_-\log P_- + P_+\log P_+).$$
Der anschließende Sweep ist linear in den Listengrößen, und die Rekonstruktion der vier Indizes benötigt nur noch \(O(B)\). Der praktische Speicherverbrauch ist also
$$O(B+P_-+P_+),$$
während die Laufzeit von Erzeugung und Sortierung der relevanten Paar-Summen dominiert wird und nicht von einer unpraktischen \(O(B^4)\)-Vollerzeugung aller Vierer-Tupel.
Her negatif olmayan tam sayı \(k\) için
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}$$
tanımlanır. Amaç,
$$0\le a\le b\le c\le d$$
olacak şekilde bir dörtlü seçip
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
ifadesini en küçük yapmaktır. Böyle bir dörtlü bulunduktan sonra istenen çıktı
$$g(n)=a^2+b^2+c^2+d^2$$
olur. Dört iç içe döngüyle doğrudan arama hedef giriş için çok pahalı olduğundan, uygulama problemi çift-toplamlar üzerinden çözülen daha düzenli bir en-yakın-toplam aramasına dönüştürür.
C++, Python ve Java uygulamaları aynı sayısal stratejiyi kullanır. Önce
$$\delta=10^{-3}$$
toleransı ile \(\pi\) çevresinde dar bir bant tanımlanır; adaylar bu bant etrafında üretilir ve en iyi yaklaşım daha sonra seçilir.
\(f_n(k)=e^{k/n}-1\) dizisi sıkı biçimde artandır. Bu nedenle uygulama yalnızca
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor$$
aralığındaki değerleri önceden hesaplar. Böylece arama için sayısal olarak anlamlı pencere sonlu hale gelir. Kontrol noktası olan \(n=200\) için
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235$$
elde edilir. Algoritma bu sınırın ötesindeki tüm dörtlüleri denemez; bunun yerine artanlık ile aşağıdaki budama eşitsizliklerini birlikte kullanır.
Dörtlüyü iki sıralı çifte ayırırsak
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d)$$
yazabiliriz. O zaman hedef
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min$$
şeklini alır. Bu, klasik meet-in-the-middle fikridir: tüm dörtlüleri taramak yerine iki ayrı çift-toplam kümesi oluşturulur ve bu iki kümeden \(\pi\)'ye en yakın toplamı veren birer eleman seçilir.
Bir liste hedefin alt tarafındaki çift-toplamları, diğeri üst tarafa yakın olanları temsil eder. İki liste sıralandıktan sonra dört boyutlu arama tek geçişli bir taramaya dönüşür.
Küçük çift-toplamlar için \(a\le b\) koşuluyla çiftler üretilir. Yalnızca \(\pi\)'ye yakın bir dörtlünün parçası olabilecek adaylar tutulur. Bunun için kullanılan temel eşitsizlikler şunlardır:
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
İlk eşitsizlik, \((a,a,a,a)\) dörtlüsünün bile izin verilen bandı aştığı anda daha büyük her \(a\)'nın da imkansız olduğunu söyler; bu yüzden dış döngü durabilir.
İkinci eşitsizlik ise sabit bir \(a\) için, eksik iki terimi de \(f_n(b)\) ile doldursak bile toplam \(\pi+\delta\)'yı aşıyorsa daha büyük her \(b\)'nin de işe yaramayacağını söyler. \(f_n\) artan olduğundan iç döngü burada güvenle kesilebilir.
İkinci liste, \(c\le d\) olacak şekilde büyükten küçüğe taranarak üretilir. Bu tarafta kullanılan koşullar şunlardır:
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
Ortadaki eşitsizlik, \((d,d,d,d)\) toplamı bile \(\pi-\delta\)'nın altında kalıyorsa daha küçük hiçbir \(d\)'nin üst aday listesine katkı veremeyeceğini gösterir; dolayısıyla aşağı yöndeki tarama durur.
Son eşitsizlik iç döngüyü kontrol eder. \(d\) sabitken en iyimser tamamlama olan \(f_n(d)+3f_n(c)\) bile alt sınır bandına ulaşamıyorsa daha küçük \(c\) değerleri yalnızca durumu kötüleştirir. Bu nedenle iç döngü burada kesilir.
Bu budamalar tek başına çözüm değildir, fakat sıralanmadan önce aday listelerini dramatik biçimde küçültür.
İki çift-toplam listesi artan sıraya göre sıralandıktan sonra uygulama monoton bir tarama yapar. Bir işaretçi küçük listede soldan sağa ilerler, diğeri büyük listenin sağ ucundan başlayıp yalnızca sola hareket eder.
Her alt-liste değeri \(x\) için, üst-liste işaretçisi toplam \(\pi\)'yi geçiş noktasına gelene kadar ayarlanır. Bu geçişte yalnızca iki komşu aday önemlidir: hedefin hemen altındaki son değer ile hemen üstündeki ilk değer. Bunlardan hangisi daha iyiyse
$$\left|x+y-\pi\right|$$
hatası onunla güncellenir. İşaretçiler geri dönmediği için bu aşama sıralamadan sonra doğrusal zamandadır.
Çift-toplam listelerinde yalnızca kayan noktalı toplamlar tutulur; bu toplamları üreten indis çiftleri saklanmaz. Bu, belleği makul tutar ama seçilen toplamlar için indislerin sonradan geri kurulmasını gerektirir.
Bunun için uygulama aynı iki-toplam en-yakın aramasını bu kez temel değer dizisi \(\{f_n(0),f_n(1),\dots,f_n(B)\}\) üzerinde iki kez daha çalıştırır: bir kez seçilen alt çift-toplamı hedef alarak, bir kez de seçilen üst çift-toplamı hedef alarak. Böylece her seçili toplam için bir sıralı indis çifti elde edilir.
Sonra dört indis sıralanır ve
$$g(n)=a^2+b^2+c^2+d^2$$
doğrudan hesaplanır.
\(n=200\) için uygulama \(B=235\) sınırını kullanır. Algoritmanın bulduğu en iyi dörtlü
$$\left(a,b,c,d\right)=\left(6,75,89,226\right)$$
olur. Buna karşılık gelen fonksiyon değerleri yaklaşık olarak
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
İki çift halinde toplarsak
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596$$
elde edilir. Bu iki toplamın birleşimi
$$0.48544594857+2.65614669596\approx 3.14159264453$$
olup \(\pi\)'den farkı yaklaşık
$$9.06\times 10^{-9}$$
kadardır. Dolayısıyla
$$g(200)=6^2+75^2+89^2+226^2=64658$$
çıkar; bu da uygulamaların doğruladığı kontrol değeridir.
C++, Python ve Java uygulamaları aynı işlem hattını izler.
Önce tek boyutlu ve artan değer dizisi \(f_n(0),f_n(1),\dots,f_n(B)\) hesaplanır. Ardından iki çift-toplam listesi üretilir: biri soldan sağa artan indislerle kurulan alt liste, diğeri sağdan sola azalan indislerle kurulan üst liste. Her iki üretim aşamasında da artanlık sayesinde eşitsizlikler bozulduğunda döngüler erken biter.
İki liste sıralandıktan sonra uygulama, her listeden bir eleman seçip toplamı \(\pi\)'ye en yakın yapan tek geçişli bir tarama yürütür. Listelerde yalnızca toplamlar bulunduğu için, seçilen iki toplamı oluşturan gerçek indis çiftleri daha sonra temel değer dizisi üzerinde iki ek iki-toplam araması ile geri kurulur. Son olarak dört indis sıralanır ve kareleri toplanır.
Yöntem tamamen sayısaldır ama kontrolsüz değildir: aynı tolerans bandı hem aday üretiminde hem de geri kurulumda kullanılır. \(g(200)=64658\) kontrolü de üç dildeki sürümlerin aynı sonucu verdiğini doğrular.
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor$$
olsun; ayrıca tutulan alt ve üst çift-toplam sayıları sırasıyla \(P_-\) ve \(P_+\) olsun. Temel değer dizisini oluşturmak \(O(B)\) zaman ve \(O(B)\) bellek gerektirir.
Çift üretim döngülerinin en kötü durum zarfı \(O(B^2)\)'dir; fakat monoton budamalar yalnızca sayısal olarak ilgili bandı gerçekten belleğe taşır. Budamadan sonraki baskın açık maliyet sıralamadır:
$$O(P_-\log P_- + P_+\log P_+).$$
En yakın-toplam taraması liste boyutlarında doğrusal çalışır, son indis geri kurulumunun ek yükü ise yalnızca \(O(B)\)'dir. Bu nedenle pratik bellek maliyeti
$$O(B+P_-+P_+)$$
olur; pratik zaman maliyetini belirleyen şey de erişilebilir çift-toplamların üretilmesi ve sıralanmasıdır, yoksa uygulanamaz büyüklükte bir \(O(B^4)\) dörtlü araması değil.
Para cada entero no negativo \(k\), se define
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
Debemos elegir una cuádrupla no decreciente
$$0\le a\le b\le c\le d$$
tal que
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
sea mínima. Una vez encontrada, la salida pedida es
$$g(n)=a^2+b^2+c^2+d^2.$$
Un barrido directo con cuatro bucles resulta inviable para el valor objetivo, así que la implementación reformula el problema como una búsqueda de suma más cercana sobre sumas de pares.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia numérica. Trabajan con la tolerancia
$$\delta=10^{-3}$$
para construir una banda estrecha alrededor de \(\pi\), y dentro de esa banda buscan la mejor combinación.
La sucesión \(f_n(k)=e^{k/n}-1\) es estrictamente creciente. Por eso la implementación solo precalcula valores para
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$$
Así se obtiene una ventana numérica finita y manejable. En el punto de control \(n=200\), esta cota vale
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
El algoritmo no explora arbitrariamente más allá de ese rango; en cambio combina la monotonía de \(f_n\) con las desigualdades de poda descritas a continuación.
Si dividimos la cuádrupla en dos pares ordenados, podemos escribir
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
Entonces el objetivo pasa a ser
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$$
Ésta es la idea clásica de meet-in-the-middle: en vez de examinar todas las cuádruplas, se generan dos colecciones de sumas de pares y luego se busca un elemento de cada colección cuya suma total quede lo más cerca posible de \(\pi\).
Una colección representa pares del lado bajo del objetivo y la otra pares del lado alto. Tras ordenar ambas, la búsqueda en cuatro dimensiones se reduce a un barrido lineal.
Para la lista de sumas pequeñas, la implementación recorre pares con \(a\le b\) y conserva solo las combinaciones que aún pueden pertenecer a una cuádrupla cercana a \(\pi\). Las desigualdades decisivas son
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
La primera dice que, si incluso la cuádrupla \((a,a,a,a)\) ya rebasa la banda admisible, entonces cualquier índice mayor que \(a\) también será inútil; por eso el bucle exterior puede detenerse.
La segunda dice que, con \(a\) fijo, si ni siquiera reemplazando los dos términos faltantes por el valor actual \(f_n(b)\) se mantiene la suma dentro de \(\pi+\delta\), entonces ningún \(b\) mayor podrá servir. Como \(f_n\) crece con \(k\), el corte temprano del bucle interior es correcto.
La segunda colección se genera de mayor a menor, con \(c\le d\). En ese barrido se imponen las condiciones
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
La desigualdad central significa que, si ni siquiera cuatro copias del término mayor actual alcanzan la banda inferior, entonces ningún valor menor de \(d\) podrá hacerlo, y el recorrido descendente puede terminar.
La última desigualdad controla el bucle interior. Con \(d\) fijo, si ni la continuación más optimista con tres copias de \(f_n(c)\) llega a \(\pi-\delta\), entonces disminuir \(c\) solo empeora la situación. Por tanto, también aquí se justifica un corte temprano.
Estas podas no resuelven el problema por sí solas, pero sí reducen de forma importante el tamaño de las listas antes de ordenarlas.
Una vez ordenadas ambas listas de sumas de pares en orden creciente, la implementación realiza un barrido monótono. Un puntero avanza por la lista inferior de izquierda a derecha, mientras el otro comienza al final de la lista superior y solo se mueve hacia la izquierda.
Para cada valor inferior \(x\), el segundo puntero se ajusta hasta el punto en que la suma cruza \(\pi\). En ese cruce solo pueden importar dos candidatos vecinos: el último que queda por debajo del objetivo y el primero que queda por encima. Comparando ambos se actualiza el error
$$\left|x+y-\pi\right|.$$
Como ninguno de los punteros retrocede, este paso es lineal una vez hecha la ordenación.
Las listas de pares almacenan únicamente sumas en coma flotante, no los pares de índices que las producen. Eso reduce memoria, pero obliga a reconstruir los índices al final.
Para lograrlo, la implementación aplica de nuevo el mismo procedimiento de suma más cercana, ahora sobre el arreglo base \(\{f_n(0),f_n(1),\dots,f_n(B)\}\): una vez con la suma inferior elegida como objetivo, y otra con la suma superior elegida como objetivo. Así se recupera un par ordenado para cada una de las dos sumas seleccionadas.
Después se ordenan los cuatro índices y se calcula
$$g(n)=a^2+b^2+c^2+d^2.$$
Para \(n=200\), la implementación usa la cota \(B=235\). La mejor cuádrupla encontrada es
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
Los valores correspondientes son aproximadamente
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
Al agruparlos en dos pares se obtiene
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
La suma total es
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
con un error de solo
$$9.06\times 10^{-9}$$
respecto de \(\pi\). Por tanto,
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
que coincide exactamente con el punto de verificación usado por las implementaciones.
Las implementaciones en C++, Python y Java comparten la misma tubería de cálculo.
Primero precalculan el arreglo monótono \(f_n(0),f_n(1),\dots,f_n(B)\). Luego construyen dos listas de sumas de pares: una lista inferior generada con índices crecientes desde la izquierda y una lista superior generada con índices decrecientes desde la derecha. En ambos casos, la monotonía permite cortar bucles en cuanto fallan las desigualdades de poda.
Después de ordenar ambas listas, la implementación ejecuta un barrido de suma más cercana para elegir un valor de cada lista cuya suma se aproxime lo máximo posible a \(\pi\). Como las listas contienen solo sumas y no índices, los dos pares reales se reconstruyen al final resolviendo dos problemas adicionales de suma más cercana sobre el arreglo original de valores individuales. Finalmente se ordenan los cuatro índices y se suma el cuadrado de cada uno.
El método es numérico, pero está controlado: la misma banda de tolerancia se usa al generar candidatos y al reconstruir los pares elegidos, y la comprobación \(g(200)=64658\) confirma que las tres versiones llegan al mismo resultado.
Sea
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
y sean \(P_-\) y \(P_+\) los tamaños de las listas inferior y superior después de la poda. Calcular el arreglo base cuesta \(O(B)\) tiempo y \(O(B)\) memoria.
Los bucles anidados que generan pares tienen una envolvente de peor caso \(O(B^2)\), pero los cortes monótonos hacen que solo se materialice la región numéricamente útil. Tras la poda, el coste dominante explícito es la ordenación:
$$O(P_-\log P_- + P_+\log P_+).$$
El barrido final es lineal en los tamaños de ambas listas, y la reconstrucción de índices añade solo \(O(B)\). En consecuencia, la memoria práctica es
$$O(B+P_-+P_+),$$
y el tiempo práctico está dominado por construir y ordenar las sumas de pares retenidas, no por una enumeración imposible de \(O(B^4)\) sobre todas las cuádruplas.
对每个非负整数 \(k\)，定义
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
题目要求选出一个非降四元组
$$0\le a\le b\le c\le d,$$
使得
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
尽可能小。找到这样的四个下标后，再计算
$$g(n)=a^2+b^2+c^2+d^2.$$
如果直接写四重枚举，目标规模下完全不可行，所以实现采用的是“先做配对求和，再做最近值搜索”的 meet-in-the-middle 方案。
C++、Python 和 Java 三个实现版本使用的是同一套数值思路。它们先在 \(\pi\) 附近建立一个很窄的候选带，然后只在这条带附近保留有希望的配对和。实现中使用的固定容差是
$$\delta=10^{-3}.$$
接下来的所有剪枝条件和重建步骤都围绕这个容差展开。
因为
$$f_n(k)=e^{k/n}-1$$
随着 \(k\) 严格递增，所以越大的下标只会产生越大的函数值。实现不会无限向外搜索，而是只预计算
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor$$
这一段区间中的所有值。这样可以把后续搜索放进一个有限而稳定的数值窗口。
以校验点 \(n=200\) 为例，有
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
也就是说，实现只会先建立从 \(f_{200}(0)\) 到 \(f_{200}(235)\) 的单调数组，然后利用下面的单调剪枝在这段区间内筛选真正值得保留的候选。
把四元组拆成两个有序的二元组，可以写成
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
那么原问题就变成了
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$$
这一步是整个算法的核心。原来要在四维空间中寻找最接近 \(\pi\) 的和，现在变成“从一组配对和里取一个，再从另一组配对和里取一个，使两者之和最接近 \(\pi\)”的问题。
也就是说，原来的四重搜索被压缩成了两个阶段：
先生成所有有希望的配对和，再在两个有序列表之间做一次最近值匹配。
这就是典型的 meet-in-the-middle 思想。
对于较小一侧的列表，实现按 \(a\le b\) 枚举二元组，并且只保留那些仍然可能属于“接近 \(\pi\)”四元组的候选。这里用到的关键不等式是
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
第一条的含义很直接：如果连四个完全相同的 \(a\) 都已经让总和超过 \(\pi+\delta\)，那么任何更大的 \(a\) 都不可能再出现在较小一侧的候选中，因此外层循环可以立即停止。
第二条的含义是：当 \(a\) 固定时，如果把剩余三个位置尽量乐观地都用当前的 \(b\) 去补，得到的总和仍然已经超过 \(\pi+\delta\)，那么再增大 \(b\) 只会更糟，所以内层循环也可以提前结束。
由于 \(f_n\) 单调递增，这种“超界即停”的写法是完全合理的，并且能显著减少需要压入列表的配对数量。
另一份列表从大下标向小下标扫描，用的是 \(c\le d\) 的配对，并配合以下条件：
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
其中第二条表示：如果连四个当前最大的 \(d\) 相加都达不到 \(\pi-\delta\)，那么任何更小的 \(d\) 更不可能进入靠近目标的上侧候选区间，因此这一层的向下扫描可以终止。
第三条则负责控制内层循环：当 \(d\) 固定时，如果连“一个 \(d\) 加上三个当前的 \(c\)”都还达不到 \(\pi-\delta\)，那么继续减小 \(c\) 只会让总和更小，于是同样可以提前停止。
这两组上下对称的剪枝规则，使得保留下来的两个配对列表都集中在真正有机会靠近 \(\pi\) 的区域，而不是把整个平方级搜索空间都塞进内存。
当较小一侧和较大一侧的配对和都按升序排好后，实现会执行一次单调扫描。一个指针从较小列表的左端向右移动，另一个指针从较大列表的右端开始，只向左移动。
对每个较小列表中的值 \(x\)，算法会把另一个指针调到“刚好穿过 \(\pi\)”的位置。到达这个位置时，真正需要比较的候选只有两个：一个是仍然让总和不超过 \(\pi\) 的最后一个值，另一个是刚刚让总和超过 \(\pi\) 的第一个值。
比较这两个候选，就能更新当前最优误差
$$\left|x+y-\pi\right|.$$
由于两个指针都不会回头，所以这一步在排序完成后只需要线性时间，而不需要对每个元素都做独立的二分查找。
为了节省内存，配对列表里存储的只是浮点数形式的配对和，而不是产生这些和的下标对。这意味着在挑出“最佳的两个配对和”之后，还必须把对应的下标重新找回来。
实现采用的方法很直接：在原始的一维值数组
$$\{f_n(0),f_n(1),\dots,f_n(B)\}$$
上再次运行同样的“最近二项和”搜索。先用选中的较小配对和作为目标恢复一个有序下标对，再用选中的较大配对和作为目标恢复另一个有序下标对。
这样就得到了四个真实下标。最后把它们排序，并计算
$$g(n)=a^2+b^2+c^2+d^2.$$
在 \(n=200\) 时，工作上界是 \(B=235\)。实现最终找到的最优四元组是
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
对应的函数值近似为
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
如果按算法的思路把它们分成两组，就得到
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
两者相加得到
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
与 \(\pi\) 的差只有
$$9.06\times 10^{-9}.$$
因此最后的平方和是
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
这正是三个实现共同使用的校验结果。
C++、Python 和 Java 实现的流程完全一致。
第一步先预计算单调数组 \(f_n(0),f_n(1),\dots,f_n(B)\)。第二步分别生成两份配对和列表：一份从较小索引端向上生成，另一份从较大索引端向下生成。由于 \(f_n\) 具有单调性，所以一旦剪枝不等式失败，相应循环就能立即停止，不必继续做无意义的枚举。
第三步把两份列表排序。第四步在两个有序列表之间执行一次最近值扫描，找出“来自左侧的一项”和“来自右侧的一项”，使它们的和最接近 \(\pi\)。第五步再回到原始的一维值数组上，分别恢复出这两个配对和对应的真实下标对。最后把四个下标排序并求平方和。
整个实现虽然是浮点数算法，但逻辑是收敛的：候选构造、最近值匹配和下标重建都围绕同一容差窗口进行，而 \(g(200)=64658\) 的检查说明三个语言版本在这个流程上是一致的。
记
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
并记剪枝后保留下来的两份配对列表大小分别为 \(P_-\) 和 \(P_+\)。预计算基础数组需要 \(O(B)\) 时间和 \(O(B)\) 空间。
生成配对时，从语法结构上看仍是嵌套循环，所以最坏外壳可以写成 \(O(B^2)\)。但由于大量使用了基于单调性的提前终止，真正进入列表并参与排序的只是靠近目标带的那一部分候选。接下来最显式、也最主要的代价是排序：
$$O(P_-\log P_- + P_+\log P_+).$$
双列表扫描本身是线性的，最后两次下标重建只再增加 \(O(B)\) 的工作量。因此实际内存占用可以写成
$$O(B+P_-+P_+),$$
而实际运行时间主要由“构造并排序保留下来的配对和”决定，而不是由完全不可接受的 \(O(B^4)\) 四元组暴力枚举决定。
Для каждого неотрицательного целого \(k\) задаётся функция
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
Нужно выбрать неубывающую четвёрку индексов
$$0\le a\le b\le c\le d,$$
для которой величина
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
минимальна. После этого вычисляется
$$g(n)=a^2+b^2+c^2+d^2.$$
Полный перебор с четырьмя вложенными циклами слишком дорог, поэтому реализация сводит задачу к поиску ближайшей суммы по заранее построенным суммам пар.
Во всех трёх реализациях используется одна и та же численная схема. Сначала задаётся узкая полоса вокруг \(\pi\) с допуском
$$\delta=10^{-3},$$
после чего строятся только те кандидаты, которые ещё могут попасть в эту полосу.
Последовательность \(f_n(k)=e^{k/n}-1\) строго возрастает, поэтому большие индексы всегда дают большие значения. Реализация заранее вычисляет массив только на отрезке
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$$
Это делает рабочую область конечной и управляемой. Для контрольного случая \(n=200\) получается
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
Дальше алгоритм опирается не на бесконечный перебор, а на монотонность функции и на правила отсечения, описанные ниже.
Если разбить четвёрку на две упорядоченные пары, то можно ввести обозначения
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
Тогда целевая величина принимает вид
$$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$$
Это и есть приём meet-in-the-middle: вместо полного перебора всех четвёрок строятся две коллекции парных сумм, а затем ищется одна сумма из первой коллекции и одна из второй, чья общая сумма максимально близка к \(\pi\).
Одна коллекция содержит более малые пары, другая более крупные. После сортировки обеих коллекций исходный четырёхмерный поиск превращается в линейный проход по двум упорядоченным спискам.
Для нижнего списка рассматриваются пары с \(a\le b\). Оставляются только те комбинации, которые ещё могут входить в четвёрку, лежащую близко к \(\pi\). Ключевые условия таковы:
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
Первое условие означает: если даже четвёрка \((a,a,a,a)\) уже превышает верхнюю границу полосы, то все большие \(a\) тем более бесполезны, и внешний цикл можно завершить.
Второе условие означает: при фиксированном \(a\), если даже максимально благоприятное дополнение тремя копиями текущего \(f_n(b)\) уже превышает \(\pi+\delta\), то все большие \(b\) тоже невозможны. Из-за монотонности это позволяет корректно делать ранний выход из внутреннего цикла.
Верхний список строится в обратном направлении, для пар \(c\le d\). Здесь используются условия
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
Среднее неравенство говорит, что если даже четыре копии текущего наибольшего значения \(d\) не дотягивают до \(\pi-\delta\), то никакое меньшее \(d\) уже не сможет попасть в верхнюю допустимую область, и внешний нисходящий цикл можно остановить.
Последнее неравенство управляет внутренним циклом. При фиксированном \(d\), если даже наиболее оптимистичное дополнение тремя копиями \(f_n(c)\) не достигает нижней границы полосы, то уменьшение \(c\) только ухудшит ситуацию. Значит, здесь тоже допустим ранний выход.
Эти отсечения не дают ответ напрямую, но радикально уменьшают объём данных, который потом нужно сортировать.
После сортировки обоих списков реализация выполняет монотонный проход. Один указатель идёт по нижнему списку слева направо, а второй начинает с правого конца верхнего списка и движется только влево.
Для каждого значения \(x\) из нижнего списка второй указатель сдвигается до точки, где сумма пересекает \(\pi\). В этой точке нужно сравнить только двух соседей: последний вариант ниже цели и первый вариант выше цели. Лучший из них обновляет ошибку
$$\left|x+y-\pi\right|.$$
Так как ни один указатель не меняет направление, этот этап после сортировки работает за линейное время.
В списках парных сумм хранятся только численные суммы, а не пары индексов, которые их породили. Это экономит память, но требует отдельного шага восстановления.
Для восстановления реализация ещё дважды применяет тот же поиск ближайшей суммы уже к базовому массиву \(\{f_n(0),f_n(1),\dots,f_n(B)\}\): один раз с целью, равной выбранной нижней парной сумме, и один раз с целью, равной выбранной верхней парной сумме. Так получаются две упорядоченные пары индексов.
Затем все четыре индекса сортируются, и напрямую вычисляется
$$g(n)=a^2+b^2+c^2+d^2.$$
При \(n=200\) рабочая граница равна \(B=235\). Лучший найденный набор индексов таков:
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
Соответствующие значения функции приблизительно равны
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
Если сгруппировать их по парам, получаем
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
Их суммарное значение равно
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
то есть отличается от \(\pi\) всего на
$$9.06\times 10^{-9}.$$
Следовательно,
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
что в точности совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java проходят одну и ту же последовательность шагов.
Сначала они предвычисляют монотонный массив \(f_n(0),f_n(1),\dots,f_n(B)\). Затем формируются два списка парных сумм: нижний список строится при движении индексов слева направо, а верхний при движении справа налево. Во всех вложенных циклах используются ранние остановки, потому что неравенства отсечения нарушаются монотонно.
После сортировки обоих списков выполняется один проход, который находит пару сумм с наименьшим отклонением от \(\pi\). Поскольку в списках сохранены только суммы, а не исходные индексы, затем выполняются ещё два поиска ближайшей двухсуммы на исходном массиве одиночных значений, чтобы восстановить реальные пары индексов. Наконец четыре индекса сортируются, и возвращается сумма их квадратов.
Метод полностью численный, но внутренне согласованный: одна и та же полоса допуска используется и при генерации кандидатов, и при восстановлении выбранных пар. Контроль \(g(200)=64658\) подтверждает, что все три языковые реализации работают одинаково.
Пусть
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
а \(P_-\) и \(P_+\) обозначают размеры нижнего и верхнего списков после отсечения. Построение базового массива требует \(O(B)\) времени и \(O(B)\) памяти.
Вложенные циклы генерации пар в худшем случае имеют оболочку \(O(B^2)\), но благодаря монотонным остановкам реально материализуется только численно важная область. После отсечения главный явный расход времени связан с сортировкой:
$$O(P_-\log P_- + P_+\log P_+).$$
Сам проход по двум спискам линеен, а восстановление индексов добавляет лишь \(O(B)\). Поэтому практическая память имеет порядок
$$O(B+P_-+P_+),$$
а практическое время определяется построением и сортировкой сохранённых парных сумм, а не невозможным полным перебором всех четвёрок за \(O(B^4)\).
لكل عدد صحيح غير سالب \(k\) نعرّف
$$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$$
المطلوب اختيار رباعية مرتبة ترتيبًا غير تنازلي
$$0\le a\le b\le c\le d$$
بحيث تكون الكمية
$$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$$
أصغر ما يمكن. بعد العثور على هذه الرباعية نحسب
$$g(n)=a^2+b^2+c^2+d^2.$$
التعداد المباشر لكل الرباعيات غير عملي إطلاقًا عند القيمة المستهدفة، لذلك تعتمد الخوارزمية على تحويل المسألة إلى بحث عن مجموعين زوجيين يكون مجموعهما الأقرب إلى \(\pi\).
تتبع تطبيقات ++C وPython وJava الخطة العددية نفسها. أولاً تُبنى حزمة ضيقة حول \(\pi\) باستعمال السماحية
$$\delta=10^{-3},$$
ثم لا تُحفَظ إلا الأزواج التي ما زال من الممكن أن تشارك في حل قريب من هذه الحزمة.
بما أن الدالة
$$f_n(k)=e^{k/n}-1$$
متزايدة زيادة صارمة مع \(k\)، فإن زيادة الفهرس لا يمكن أن تُنتج إلا قيمة أكبر. لذلك لا تبني الخوارزمية القيم لكل \(k\) الممكنة، بل تكتفي بالمجال
$$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$$
هذا يجعل نافذة البحث منتهية ومناسبة عمليًا. وعند نقطة الفحص \(n=200\) نحصل على
$$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$$
بعد ذلك لا تعتمد الطريقة على الاستمرار في التعداد خارج هذا النطاق، بل تستفيد من الرتابة مع قواعد تقليم مبكرة تقلل عدد المرشحين كثيرًا.
إذا قسمنا الرباعية إلى زوجين مرتبَين فيمكن كتابة
$$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$$
وعندها يصبح الهدف هو تصغير
$$\left|s_{a,b}+t_{c,d}-\pi\right|.$$
هذه هي فكرة meet-in-the-middle بالضبط: بدل المرور على جميع الرباعيات، نكوّن قائمتين من مجاميع الأزواج، ثم نبحث عن عنصر من كل قائمة يكون مجموعهما أقرب ما يمكن إلى \(\pi\).
إحدى القائمتين تمثل المجاميع الأصغر من جهة الهدف، والأخرى تمثل المجاميع الأكبر. وبعد ترتيب القائمتين تختزل المسألة من بحث رباعي الأبعاد إلى مسح خطي بين قائمتين مرتبتين.
في القائمة الأولى تُولَّد الأزواج بحيث \(a\le b\)، ولكن لا يُحتفَظ إلا بالأزواج التي ما زال من الممكن إكمالها إلى رباعية قريبة من \(\pi\). وتعتمد عملية التقليم على المتراجحتين
$$4f_n(a)\le \pi+\delta,$$
$$f_n(a)+3f_n(b)\le \pi+\delta.$$
المتراجحة الأولى تقول: إذا كانت الرباعية \((a,a,a,a)\) نفسها قد تجاوزت الحافة العليا للحزمة، فإن أي \(a\) أكبر منها سيكون أسوأ، ولذلك يمكن إيقاف الحلقة الخارجية فورًا.
أما المتراجحة الثانية فتعني أنه عند تثبيت \(a\)، إذا كان التعويض عن الحدود الثلاثة الباقية بثلاث نسخ من القيمة الحالية \(f_n(b)\) يجعل المجموع يتجاوز \(\pi+\delta\)، فإن أي \(b\) أكبر لن يفيد. وبسبب رتابة \(f_n\) يصبح الإيقاف المبكر للحلقة الداخلية صحيحًا.
القائمة الثانية تُبنى من الأعلى إلى الأسفل مع أزواج تحقق \(c\le d\). وفي هذه الجهة تُستخدم الشروط
$$f_n(c)+f_n(d)\le \pi+\delta,$$
$$4f_n(d)\ge \pi-\delta,$$
$$f_n(d)+3f_n(c)\ge \pi-\delta.$$
المتراجحة الوسطى تعني أنه إذا كانت أربع نسخ من أكبر حد حالي \(d\) لا تزال أقل من \(\pi-\delta\)، فإن أي قيمة أصغر من \(d\) ستبقى بعيدة أكثر، ولذلك يجوز إنهاء المسح الهابط عند تلك النقطة.
والمتراجحة الأخيرة تتحكم في الحلقة الداخلية: إذا كان \(d\) ثابتًا، وحتى أكثر إكمال متفائل وهو \(f_n(d)+3f_n(c)\) لا يصل إلى الحافة الدنيا للحزمة، فإن تصغير \(c\) أكثر لن يفعل إلا إبعاد المجموع. ولهذا يمكن كسر الحلقة هنا أيضًا.
بهذا الأسلوب لا تحاول الخوارزمية فرز جميع الأزواج الممكنة، بل تحتفظ فقط بالشريط العددي القريب فعلًا من الهدف.
بعد ترتيب القائمتين تصاعديًا، تنفذ الخوارزمية مسحًا رتيبًا. يتحرك مؤشر في قائمة المجاميع الصغيرة من اليسار إلى اليمين، بينما يبدأ المؤشر الآخر من آخر قائمة المجاميع الكبيرة ويتحرك فقط نحو اليسار.
لكل قيمة \(x\) في القائمة الصغيرة يُحرَّك المؤشر الثاني حتى نقطة عبور المجموع للقيمة \(\pi\). وعند هذه النقطة لا يلزم فحص إلا احتمالين متجاورين: آخر مجموع يجعل \(x+y\) أقل من \(\pi\)، وأول مجموع يجعلها أكبر من \(\pi\).
بمقارنة هذين الاحتمالين فقط يمكن تحديث أصغر خطأ معروف
$$\left|x+y-\pi\right|.$$
ولأن كلا المؤشرين لا يعود إلى الخلف، فإن هذه المرحلة تصبح خطية بعد اكتمال الترتيب.
لأسباب تتعلق بالذاكرة، لا تخزن القائمتان أزواج الفهارس نفسها، بل تخزنان فقط المجاميع العشرية الناتجة عنها. لذلك لا بد بعد اختيار أفضل مجموعين من استرجاع الزوجين الحقيقيين اللذين ولّدا هاتين القيمتين.
ولهذا تعيد الخوارزمية استعمال إجراء أقرب مجموع ثنائي على المصفوفة الأساسية
$$\{f_n(0),f_n(1),\dots,f_n(B)\}$$
مرتين: مرة بهدف يساوي المجموع الصغير المختار، ومرة بهدف يساوي المجموع الكبير المختار. وبهذا نحصل على زوجين مرتبَين من الفهارس.
ثم تُرتَّب الفهارس الأربعة معًا، ويُحسب بعدها مباشرة
$$g(n)=a^2+b^2+c^2+d^2.$$
عند \(n=200\) يكون حد العمل هو \(B=235\). الرباعية التي تصل إليها الخوارزمية هي
$$\left(a,b,c,d\right)=\left(6,75,89,226\right).$$
وقيم الدالة الموافقة تقريبًا هي
$$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$$
$$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$$
وعند جمعها على شكل زوجين نحصل على
$$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$$
$$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$$
إذن المجموع الكلي يساوي تقريبًا
$$0.48544594857+2.65614669596\approx 3.14159264453,$$
أي أن الفارق عن \(\pi\) لا يتجاوز
$$9.06\times 10^{-9}.$$
ومن ثم يكون
$$g(200)=6^2+75^2+89^2+226^2=64658,$$
وهو بالضبط مقدار التحقق المستخدم في جميع التطبيقات.
تسير تطبيقات ++C وPython وJava عبر المراحل نفسها.
أولاً تُحسب مسبقًا المصفوفة الأحادية المرتبة \(f_n(0),f_n(1),\dots,f_n(B)\). بعد ذلك تُنشأ قائمتان من مجاميع الأزواج: قائمة دنيا تُبنى بزيادة الفهارس من اليسار، وقائمة عليا تُبنى بإنقاص الفهارس من اليمين. في المرحلتين معًا تسمح الرتابة بإيقاف الحلقات مبكرًا بمجرد فشل شروط التقليم.
ثم تُرتَّب القائمتان، وتُجرى عملية مسح واحدة لاختيار قيمة من كل قائمة يكون مجموعهما أقرب ما يمكن إلى \(\pi\). وبما أن القائمتين لا تحتويان إلا على المجاميع، فإن الخوارزمية تعود بعد ذلك إلى المصفوفة الأصلية للقيم المفردة لاسترجاع الزوجين الحقيقيين بواسطة بحثين إضافيين عن أقرب مجموع ثنائي. وفي النهاية تُرتَّب الفهارس الأربعة ويُعاد مجموع مربعاتها.
الطريقة عددية لكنها منضبطة: نفس هامش السماحية يُستخدم عند توليد المرشحين وعند استرجاع الأزواج المختارة، كما أن فحص \(g(200)=64658\) يؤكد تطابق النتائج بين اللغات الثلاث.
لنكتب
$$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$$
ولنرمز إلى حجمي القائمتين بعد التقليم بـ \(P_-\) و\(P_+\). بناء المصفوفة الأساسية يحتاج إلى \(O(B)\) زمنًا و\(O(B)\) ذاكرة.
أما حلقات توليد الأزواج فلها غلاف أسوأ حالة من الرتبة \(O(B^2)\)، لكن التوقفات المبكرة المبنية على الرتابة تعني أن الجزء الذي يُخزَّن ويُفرَز فعليًا هو فقط الشريط العددي المفيد. وبعد التقليم تصبح الكلفة الصريحة الأكبر هي كلفة الفرز:
$$O(P_-\log P_- + P_+\log P_+).$$
المسح النهائي بين القائمتين خطي، كما أن استرجاع الفهارس يضيف فقط \(O(B)\) عملًا إضافيًا. لذلك يمكن كتابة استهلاك الذاكرة العملي على الصورة
$$O(B+P_-+P_+),$$
بينما تهيمن على زمن التنفيذ عمليًا مرحلتا بناء مجاميع الأزواج المحتفَظ بها وفرزها، لا تعدادٌ كامل غير مقبول من الرتبة \(O(B^4)\).