For even \(N\), the implementation models the red region as a symmetric staircase built around the unit circle. By symmetry, the four quadrants contribute the same amount, so it is enough to optimize a single quadrant and multiply by \(4\). If \(m=N/2\), the numerical task is to choose \(m\) interior breakpoints on the quarter-circle so that this staircase area is as small as possible.
In the first quadrant the circle is the graph
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
Choose breakpoints
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
and set \(y_i=f(x_i)\). On each interval \([x_i,x_{i+1}]\), the staircase uses the constant height \(y_i\). Therefore the quadrant contribution is
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
The full red area is then
$$A_N=4Q(x_1,\dots,x_m).$$
This is exactly the quantity accumulated by the code after the optimal breakpoints have been found.
The key point is that the solver is not using an arbitrary mesh. It chooses the breakpoints so that \(Q\) is stationary with respect to every interior variable \(x_k\). Only two summands depend on \(x_k\):
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{and} \qquad (x_{k+1}-x_k)f(x_k). $$
Differentiating \(Q\) with respect to \(x_k\) gives
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
For the unit circle,
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
Setting \(\frac{\partial Q}{\partial x_k}=0\) and rearranging yields
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
This boxed identity is the exact recurrence implemented in the C++, Python, and Java solutions.
Once \(x_1\) is fixed, the recurrence determines \(x_2,x_3,\dots,x_{m+1}\) one after another. That reduces the original \(m\)-variable minimization problem to a one-variable boundary condition:
$$x_{m+1}=1.$$
The implementations encode this through the residual function
$$R(x_1)=x_{m+1}(x_1)-1.$$
Then a shooting step becomes: guess \(x_1\), build the whole sequence, inspect the sign of \(R(x_1)\), and refine the guess. The code brackets \(x_1\) inside \((10^{-18},0.999999999999)\) and performs 260 bisection iterations. If a trial leaves the admissible region or produces a non-finite value, the build is rejected and the residual is treated as \(+\infty\), which safely pushes the search back toward valid values.
After bisection, the sequence is rebuilt from the final \(x_1\). The code then forces \(x_{m+1}=1\) exactly to eliminate tiny floating-point boundary drift. With the final sequence in hand, it computes
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i),$$
and returns
$$A_N=4Q.$$
So the numerical work has two clean phases: first satisfy the optimality equations with the endpoint condition, then evaluate the resulting staircase area.
For \(N=2\) we have \(m=1\). The optimum occurs at
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
which gives
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
This is the first checkpoint used in the C++ program.
For \(N=10\), shooting produces the breakpoints
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
and the total area
$$A_{10}\approx 3.3469640797.$$
This is the second checkpoint in the C++ file. With the default input \(N=400\), the implementations output
$$A_{400}\approx 3.1486734435.$$
f(x) evaluates the quarter-circle height. build_sequence stores the breakpoints and applies the recurrence step by step. shooting_residual returns \(R(x_1)\). solve_breakpoints performs the fixed-count bisection loop and then enforces the right endpoint numerically. Finally, minimal_red_area accumulates the strip areas and multiplies by \(4\). The Python and Java files are direct translations of the same method; the C++ version additionally checks \(N=2\) and \(N=10\) before printing the default \(N=400\) answer.
Let \(m=N/2\). One call to build_sequence computes \(m+1\) new values, so it costs \(O(m)\) time and \(O(m)\) memory. Bisection performs a fixed 260 residual evaluations, hence the implemented runtime is \(O(260m)=O(N)\). If the iteration count is written symbolically as \(B\), the method is \(O(BN)\) time and \(O(N)\) memory.
Für gerades \(N\) beschreibt die Implementierung die rote Fläche als symmetrische Treppenkonstruktion um den Einheitskreis. Wegen der Symmetrie tragen alle vier Quadranten denselben Anteil bei, daher genügt es, einen einzigen Quadranten zu optimieren und das Ergebnis mit \(4\) zu multiplizieren. Für \(m=N/2\) müssen also \(m\) innere Stützstellen auf dem Viertelkreis so gewählt werden, dass diese Treppenfläche minimal wird.
Im ersten Quadranten ist der Kreis der Graph von
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
Wir wählen Stützstellen
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
und setzen \(y_i=f(x_i)\). Auf jedem Intervall \([x_i,x_{i+1}]\) verwendet die Treppe die konstante Höhe \(y_i\). Damit ist der Quadrantenbeitrag
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
Die gesamte rote Fläche lautet also
$$A_N=4Q(x_1,\dots,x_m).$$
Genau diese Größe wird im Code aufsummiert, sobald die optimalen Stützstellen feststehen.
Der Solver benutzt kein beliebiges Gitter. Er bestimmt die Punkte so, dass \(Q\) bezüglich jeder inneren Variablen \(x_k\) stationär ist. Von \(x_k\) hängen nur zwei Summanden ab:
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{und} \qquad (x_{k+1}-x_k)f(x_k). $$
Ableiten nach \(x_k\) ergibt
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
Für den Einheitskreis gilt
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
Aus \(\frac{\partial Q}{\partial x_k}=0\) folgt nach Umstellen
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
Diese Rekurrenz ist exakt die Formel aus den C++-, Python- und Java-Lösungen.
Sobald \(x_1\) vorgegeben ist, bestimmt die Rekurrenz nacheinander \(x_2,x_3,\dots,x_{m+1}\). Damit schrumpft das ursprüngliche Optimierungsproblem mit \(m\) Variablen auf eine einzige Randbedingung:
$$x_{m+1}=1.$$
Die Implementierungen schreiben dies als Restfunktion
$$R(x_1)=x_{m+1}(x_1)-1.$$
Ein Shooting-Schritt bedeutet also: \(x_1\) raten, die gesamte Folge aufbauen, das Vorzeichen von \(R(x_1)\) prüfen und den Startwert verfeinern. Der Code klammert \(x_1\) in \((10^{-18},0.999999999999)\) ein und führt 260 Bisektionsschritte aus. Falls ein Versuch den zulässigen Bereich verlässt oder einen nicht-finiten Wert erzeugt, wird der Aufbau verworfen und der Rest als \(+\infty\) behandelt; dadurch verschiebt sich die Suche zuverlässig zurück in den gültigen Bereich.
Nach der Bisektion wird die Folge mit dem endgültigen \(x_1\) noch einmal aufgebaut. Anschließend setzt der Code \(x_{m+1}=1\) explizit, um winzige numerische Randfehler zu eliminieren. Danach wird
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
berechnet und
$$A_N=4Q$$
zurückgegeben. Die numerische Arbeit zerfällt also sauber in zwei Phasen: erst die Optimalitätsgleichungen mitsamt Endpunkt lösen, dann die resultierende Treppenfläche auswerten.
Für \(N=2\) ist \(m=1\). Das Optimum liegt bei
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
und damit
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
Das ist der erste Prüfpunkt im C++-Programm.
Für \(N=10\) liefert das Shooting die Stützstellen
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
und die Gesamtfläche
$$A_{10}\approx 3.3469640797.$$
Das ist der zweite Prüfpunkt. Mit der Standardvorgabe \(N=400\) geben die Implementierungen aus
$$A_{400}\approx 3.1486734435.$$
f(x) berechnet die Viertelkreis-Höhe. build_sequence speichert die Stützstellen und wendet die Rekurrenz Schritt für Schritt an. shooting_residual liefert \(R(x_1)\). solve_breakpoints führt die Bisektion mit fester Iterationszahl aus und erzwingt danach numerisch den rechten Endpunkt. Schließlich summiert minimal_red_area die Streifenflächen und multipliziert mit \(4\). Die Python- und Java-Dateien sind direkte Übersetzungen desselben Verfahrens; die C++-Version enthält zusätzlich die Prüfungen für \(N=2\) und \(N=10\).
Sei \(m=N/2\). Ein Aufruf von build_sequence berechnet \(m+1\) neue Werte und kostet daher \(O(m)\) Zeit sowie \(O(m)\) Speicher. Die Bisektion verwendet fest 260 Residualauswertungen, also ist die implementierte Laufzeit \(O(260m)=O(N)\). Schreibt man die Iterationszahl symbolisch als \(B\), erhält man \(O(BN)\) Zeit und \(O(N)\) Speicher.
Çift \(N\) için implementasyon, kırmızı bölgeyi birim çemberin etrafına kurulan simetrik bir basamak yapısı olarak ele alır. Dört çeyrek simetri nedeniyle aynı katkıyı verdiği için tek bir çeyreği optimize edip sonucu \(4\) ile çarpmak yeterlidir. \(m=N/2\) alındığında, amaç çeyrek çember üzerindeki \(m\) iç kırılma noktasını seçip bu basamak alanını en küçük yapmaktır.
İlk çeyrekte çember şu eğridir:
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
Kırılma noktalarını
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1$$
olarak seçelim ve \(y_i=f(x_i)\) tanımlayalım. Basamak yapısı, \([x_i,x_{i+1}]\) aralığında sabit yükseklik olarak \(y_i\) kullanır. Böylece çeyrek katkı
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
olur. Toplam kırmızı alan ise
$$A_N=4Q(x_1,\dots,x_m)$$
şeklindedir. Kod, en iyi kırılma noktalarını bulduktan sonra tam olarak bu toplamı hesaplar.
Çözücü rastgele bir ağ kullanmıyor. \(Q\) fonksiyonunu her iç değişken \(x_k\) bakımından durağan yapan noktaları seçiyor. \(x_k\)'ye bağlı olan yalnızca iki terim vardır:
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{ve} \qquad (x_{k+1}-x_k)f(x_k). $$
\(x_k\)'ye göre türev alınırsa
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k)$$
elde edilir. Birim çember için
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}$$
olduğundan, \(\frac{\partial Q}{\partial x_k}=0\) koşulu
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m$$
sonucunu verir. Bu, C++, Python ve Java çözümlerindeki reküransın aynısıdır.
\(x_1\) seçildiği anda rekürans \(x_2,x_3,\dots,x_{m+1}\) değerlerini sırayla belirler. Böylece başlangıçta \(m\) değişkenli görünen optimizasyon, tek bir sınır koşuluna indirgenir:
$$x_{m+1}=1.$$
Implementasyon bunu
$$R(x_1)=x_{m+1}(x_1)-1$$
artık fonksiyonu ile ifade eder. Yani bir shooting adımı şudur: \(x_1\) tahmin et, tüm diziyi kur, \(R(x_1)\)'in işaretine bak, sonra tahmini daralt. Kod \(x_1\) için \((10^{-18},0.999999999999)\) aralığını kullanır ve 260 biseksiyon adımı uygular. Eğer bir deneme geçerli bölgeden çıkarsa veya sonlu olmayan bir değer üretirse, bu deneme reddedilir ve residual \(+\infty\) kabul edilir; böylece arama güvenli biçimde geçerli bölgeye geri itilir.
Biseksiyon tamamlandıktan sonra dizi son \(x_1\) ile yeniden kurulur. Ardından kod, kayan nokta kaynaklı küçük sınır hatalarını temizlemek için \(x_{m+1}=1\) değerini açıkça zorlar. Sonrasında
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
hesaplanır ve
$$A_N=4Q$$
döndürülür. Böylece sayısal yöntem iki temiz parçaya ayrılır: önce optimal koşulları ve uç noktayı sağla, sonra oluşan basamak alanını topla.
\(N=2\) için \(m=1\) olur. En iyi nokta
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}}$$
ve toplam alan
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2$$
şeklindedir. Bu, C++ dosyasındaki ilk kontroldür.
\(N=10\) için shooting şu kırılma noktalarını üretir:
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
ve toplam alan
$$A_{10}\approx 3.3469640797$$
çıkar. Bu ikinci kontrol değeridir. Varsayılan giriş \(N=400\) olduğunda üç implementasyon da
$$A_{400}\approx 3.1486734435$$
yazdırır.
f(x) çeyrek çember yüksekliğini hesaplar. build_sequence kırılma noktalarını saklar ve reküransı adım adım uygular. shooting_residual fonksiyonu \(R(x_1)\) değerini döndürür. solve_breakpoints sabit sayıda biseksiyon yapar ve sonunda sağ uç noktayı sayısal olarak düzeltir. Son olarak minimal_red_area şerit alanlarını toplar ve sonucu \(4\) ile çarpar. Python ve Java dosyaları aynı yöntemin doğrudan çevirileridir; C++ sürümü ek olarak \(N=2\) ve \(N=10\) kontrollerini çalıştırır.
\(m=N/2\) olsun. build_sequence çağrısı \(m+1\) yeni değer üretir; dolayısıyla süre maliyeti \(O(m)\), bellek maliyeti \(O(m)\) olur. Biseksiyon sabit olarak 260 residual hesabı yaptığı için implementasyondaki toplam süre \(O(260m)=O(N)\)'dir. İterasyon sayısını sembolik olarak \(B\) yazarsak yöntem \(O(BN)\) zaman ve \(O(N)\) bellek kullanır.
Para \(N\) par, la implementación representa la región roja como una escalera simétrica construida alrededor de la circunferencia unidad. Por simetría, los cuatro cuadrantes aportan lo mismo, así que basta optimizar un solo cuadrante y multiplicar el resultado por \(4\). Si \(m=N/2\), el problema numérico consiste en elegir \(m\) puntos interiores sobre el cuarto de círculo para que el área de esa escalera sea mínima.
En el primer cuadrante, la circunferencia está dada por
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
Elegimos puntos de corte
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
y definimos \(y_i=f(x_i)\). En cada intervalo \([x_i,x_{i+1}]\), la escalera usa la altura constante \(y_i\). Por tanto, el aporte del cuadrante es
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
El área roja total es entonces
$$A_N=4Q(x_1,\dots,x_m).$$
Ésa es exactamente la cantidad que acumula el código una vez encontrados los puntos óptimos.
El programa no usa una malla arbitraria. Escoge los puntos para que \(Q\) sea estacionaria respecto de cada variable interior \(x_k\). Sólo dos sumandos dependen de \(x_k\):
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{y} \qquad (x_{k+1}-x_k)f(x_k). $$
Al derivar respecto de \(x_k\) se obtiene
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
Para la circunferencia unidad,
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
Imponiendo \(\frac{\partial Q}{\partial x_k}=0\) y reordenando aparece
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
Ésta es la misma recurrencia implementada en los tres lenguajes.
Una vez fijado \(x_1\), la recurrencia determina \(x_2,x_3,\dots,x_{m+1}\) en cadena. Eso reduce el problema original, que parecía tener \(m\) variables, a una única condición de contorno:
$$x_{m+1}=1.$$
Las implementaciones lo expresan mediante el residuo
$$R(x_1)=x_{m+1}(x_1)-1.$$
Un paso de shooting consiste en adivinar \(x_1\), construir toda la secuencia, observar el signo de \(R(x_1)\) y refinar la conjetura. El código encierra \(x_1\) en \((10^{-18},0.999999999999)\) y ejecuta 260 iteraciones de bisección. Si una prueba abandona la región admisible o produce un valor no finito, se descarta y el residuo se trata como \(+\infty\), lo que empuja la búsqueda de vuelta a valores válidos.
Tras la bisección, la secuencia se reconstruye usando el valor final de \(x_1\). Después, el código fija \(x_{m+1}=1\) exactamente para eliminar pequeñas derivas numéricas en el borde. Con la secuencia final, calcula
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
y devuelve
$$A_N=4Q.$$
Así, el método numérico se divide en dos fases claras: primero resolver las ecuaciones de optimalidad con la condición final, y luego evaluar el área de la escalera resultante.
Para \(N=2\) se tiene \(m=1\). El óptimo aparece en
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
y por tanto
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
Éste es el primer checkpoint de la versión en C++.
Para \(N=10\), el shooting produce los puntos
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
y el área total
$$A_{10}\approx 3.3469640797.$$
Ése es el segundo checkpoint. Con la entrada por defecto \(N=400\), las implementaciones imprimen
$$A_{400}\approx 3.1486734435.$$
f(x) evalúa la altura del cuarto de círculo. build_sequence almacena los puntos y aplica la recurrencia paso a paso. shooting_residual devuelve \(R(x_1)\). solve_breakpoints ejecuta el bucle fijo de bisección y luego fuerza numéricamente el extremo derecho. Finalmente, minimal_red_area suma las áreas de las franjas y multiplica por \(4\). Los archivos de Python y Java son traducciones directas del mismo procedimiento; la versión en C++ además verifica los casos \(N=2\) y \(N=10\).
Sea \(m=N/2\). Una llamada a build_sequence calcula \(m+1\) valores nuevos, así que cuesta \(O(m)\) tiempo y \(O(m)\) memoria. La bisección usa 260 evaluaciones del residuo, de modo que el tiempo total implementado es \(O(260m)=O(N)\). Si se escribe el número de iteraciones como \(B\), el método tiene coste \(O(BN)\) en tiempo y \(O(N)\) en memoria.
当 \(N\) 为偶数时，程序把红色区域表示成围绕单位圆构造的对称阶梯形区域。由于四个象限完全对称，只需求出一个象限中的最优构造，再把结果乘以 \(4\)。令 \(m=N/2\)，数值任务就变成：在四分之一圆弧上选择 \(m\) 个内部断点，使这种阶梯面积最小。
第一象限中的圆弧可写成函数
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
取断点
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
并记 \(y_i=f(x_i)\)。在每个区间 \([x_i,x_{i+1}]\) 上，阶梯使用常数高度 \(y_i\)。因此单个象限的面积为
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
整个红色区域的面积就是
$$A_N=4Q(x_1,\dots,x_m).$$
这正是代码在求得最优断点之后实际累加的量。
程序并不是随便取网格，而是寻找使 \(Q\) 对每个内部变量 \(x_k\) 都达到驻点的断点。对 \(x_k\) 有依赖的只有两项：
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{和} \qquad (x_{k+1}-x_k)f(x_k). $$
对 \(x_k\) 求导得到
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
对单位圆有
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
令 \(\frac{\partial Q}{\partial x_k}=0\)，整理后得到
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
这正是 C++、Python 和 Java 三份解答里使用的核心递推。
一旦给定 \(x_1\)，递推关系就会依次确定 \(x_2,x_3,\dots,x_{m+1}\)。原本看似有 \(m\) 个变量的优化问题，被压缩成一个边界条件：
$$x_{m+1}=1.$$
程序把它写成残差函数
$$R(x_1)=x_{m+1}(x_1)-1.$$
于是 shooting 的过程就是：先猜一个 \(x_1\)，构造整条序列，检查 \(R(x_1)\) 的符号，再继续缩小范围。代码把 \(x_1\) 夹在 \((10^{-18},0.999999999999)\) 内，并进行 260 次二分。如果某个试探值使序列离开可行区间，或者出现非有限数，程序就把这次尝试判为无效，并把残差视为 \(+\infty\)，这样二分会自动把搜索推回有效区域。
二分结束后，程序用最终的 \(x_1\) 再构造一次完整序列，然后把 \(x_{m+1}\) 直接设成 \(1\)，以消除浮点计算带来的微小边界漂移。随后计算
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i),$$
并返回
$$A_N=4Q.$$
因此整个数值方法可以清楚地分成两步：先满足最优性方程和终点条件，再对得到的阶梯区域做面积求和。
当 \(N=2\) 时，\(m=1\)。最优点为
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
于是总面积为
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
这就是 C++ 程序中的第一个检查点。
当 \(N=10\) 时，shooting 得到的断点为
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
对应总面积
$$A_{10}\approx 3.3469640797.$$
这正是第二个检查点。默认输入 \(N=400\) 时，三种实现都会输出
$$A_{400}\approx 3.1486734435.$$
f(x) 计算四分之一圆弧的高度。build_sequence 保存断点并逐步应用上面的递推式。shooting_residual 返回 \(R(x_1)\)。solve_breakpoints 执行固定次数的二分，并在结束后把右端点数值上强制设为 \(1\)。最后，minimal_red_area 累加各个水平条带的面积，再乘以 \(4\)。Python 和 Java 文件都是同一算法的直接翻译；C++ 版本额外运行 \(N=2\) 与 \(N=10\) 的校验。
令 \(m=N/2\)。一次 build_sequence 调用需要计算 \(m+1\) 个新值，因此时间复杂度为 \(O(m)\)，空间复杂度也为 \(O(m)\)。二分固定做 260 次残差计算，所以实际实现的总时间复杂度是 \(O(260m)=O(N)\)。如果把迭代次数写成符号 \(B\)，则可记为 \(O(BN)\) 时间和 \(O(N)\) 空间。
Для чётного \(N\) реализация рассматривает красную область как симметричную ступенчатую фигуру, построенную вокруг единичной окружности. Благодаря симметрии все четыре квадранта дают одинаковый вклад, поэтому достаточно оптимизировать один квадрант и умножить результат на \(4\). Если \(m=N/2\), нужно выбрать \(m\) внутренних точек на четверти окружности так, чтобы площадь этой ступенчатой конструкции была минимальной.
В первом квадранте окружность задаётся графиком
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
Выберем точки
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
и положим \(y_i=f(x_i)\). На каждом интервале \([x_i,x_{i+1}]\) ступенька имеет постоянную высоту \(y_i\). Тогда вклад одного квадранта равен
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
Полная красная площадь равна
$$A_N=4Q(x_1,\dots,x_m).$$
Именно эту величину программа вычисляет после нахождения оптимальных точек.
Решение не использует произвольную сетку. Точки выбираются так, чтобы \(Q\) было стационарно по каждой внутренней переменной \(x_k\). От \(x_k\) зависят только два слагаемых:
$$ (x_k-x_{k-1})f(x_{k-1}) \qquad \text{и} \qquad (x_{k+1}-x_k)f(x_k). $$
Дифференцирование по \(x_k\) даёт
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
Для единичной окружности
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
Из условия \(\frac{\partial Q}{\partial x_k}=0\) после преобразования получается
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
Это в точности та рекурсия, которая реализована в C++, Python и Java.
Как только задано \(x_1\), рекурсия однозначно строит \(x_2,x_3,\dots,x_{m+1}\). Поэтому исходная задача оптимизации с \(m\) переменными сводится к одному граничному условию:
$$x_{m+1}=1.$$
В коде это записано через функцию невязки
$$R(x_1)=x_{m+1}(x_1)-1.$$
Дальше действует схема shooting: предположить \(x_1\), построить всю последовательность, посмотреть знак \(R(x_1)\) и уточнить начальное значение. Программа ограничивает \(x_1\) интервалом \((10^{-18},0.999999999999)\) и делает 260 шагов бисекции. Если пробное значение выводит последовательность из допустимой области или рождает нечисловой результат, такая попытка отвергается, а невязка считается равной \(+\infty\); это безопасно возвращает поиск в корректную зону.
После бисекции последовательность строится заново с финальным \(x_1\). Затем код явно присваивает \(x_{m+1}=1\), чтобы убрать крошечный численный дрейф на правой границе. После этого вычисляется
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
и возвращается
$$A_N=4Q.$$
То есть численная схема чётко разделена на две части: сначала решить уравнения оптимальности с конечным условием, затем вычислить площадь построенной ступенчатой фигуры.
Для \(N=2\) имеем \(m=1\). Оптимальная точка равна
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
поэтому
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
Это первая контрольная проверка в C++-версии.
Для \(N=10\) метод shooting даёт точки
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
а общая площадь равна
$$A_{10}\approx 3.3469640797.$$
Это вторая проверка. При стандартном запуске с \(N=400\) все три реализации выводят
$$A_{400}\approx 3.1486734435.$$
f(x) вычисляет высоту четверти окружности. build_sequence хранит точки и пошагово применяет рекурсию. shooting_residual возвращает \(R(x_1)\). solve_breakpoints выполняет фиксированное число шагов бисекции и затем численно закрепляет правую границу. Наконец, minimal_red_area суммирует площади полос и умножает результат на \(4\). Файлы Python и Java являются прямыми переводами той же схемы; версия C++ дополнительно проверяет случаи \(N=2\) и \(N=10\).
Пусть \(m=N/2\). Один вызов build_sequence вычисляет \(m+1\) новых значений, поэтому стоит \(O(m)\) по времени и \(O(m)\) по памяти. Бисекция выполняет фиксированные 260 вычислений невязки, следовательно, фактическая сложность реализации равна \(O(260m)=O(N)\). Если обозначить число итераций через \(B\), получаем \(O(BN)\) по времени и \(O(N)\) по памяти.
عندما يكون \(N\) زوجياً، تتعامل الشيفرة مع المنطقة الحمراء على أنها شكل سلمي متماثل مبني حول دائرة الوحدة. وبسبب التناظر، فإن مساهمة الأرباع الأربعة متطابقة، لذا يكفي تحسين ربع واحد ثم ضرب النتيجة في \(4\). إذا كتبنا \(m=N/2\)، فإن المهمة العددية تصبح اختيار \(m\) نقاط داخلية على ربع الدائرة بحيث تكون مساحة هذا السلم أصغر ما يمكن.
في الربع الأول تمثل الدائرة المنحنى
$$f(x)=\sqrt{1-x^2}, \qquad 0 \le x \le 1.$$
نختار نقاط الفصل
$$0=x_0 \lt x_1 \lt \cdots \lt x_m \lt x_{m+1}=1,$$
ثم نعرف \(y_i=f(x_i)\). وعلى كل فترة \([x_i,x_{i+1}]\) يستعمل السلم الارتفاع الثابت \(y_i\). لذلك تكون مساهمة الربع
$$Q(x_1,\dots,x_m)=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i).$$
ومن ثم فإن المساحة الحمراء الكلية هي
$$A_N=4Q(x_1,\dots,x_m).$$
وهذه هي الكمية نفسها التي تجمعها الشيفرة بعد العثور على النقاط المثلى.
البرنامج لا يختار شبكة عشوائية، بل يحدد النقاط بحيث تكون \(Q\) ساكنة بالنسبة إلى كل متغير داخلي \(x_k\). لا يعتمد على \(x_k\) إلا حدان فقط:
$$ (x_k-x_{k-1})f(x_{k-1}), \qquad (x_{k+1}-x_k)f(x_k). $$
باشتقاق \(Q\) بالنسبة إلى \(x_k\) نحصل على
$$\frac{\partial Q}{\partial x_k}=f(x_{k-1})-f(x_k)+(x_{k+1}-x_k)f'(x_k).$$
وبالنسبة إلى دائرة الوحدة،
$$f'(x)=\frac{-x}{\sqrt{1-x^2}}=-\frac{x}{f(x)}.$$
وعند فرض \(\frac{\partial Q}{\partial x_k}=0\) ثم إعادة الترتيب نحصل على
$$\boxed{x_{k+1}=x_k+\frac{(f(x_{k-1})-f(x_k))f(x_k)}{x_k}}, \qquad 1 \le k \le m.$$
وهذه هي بالضبط العلاقة المستعملة في ملفات C++ و Python و Java.
بمجرد تثبيت \(x_1\)، تحدد العلاقة التكرارية القيم \(x_2,x_3,\dots,x_{m+1}\) بالتتابع. وهكذا يختزل برنامج التحسين، الذي يبدو في الأصل ذا \(m\) متغيرات، إلى شرط حدّي واحد:
$$x_{m+1}=1.$$
تترجم الشيفرة ذلك إلى دالة متبقٍ
$$R(x_1)=x_{m+1}(x_1)-1.$$
وبذلك تصبح خطوة shooting كما يلي: نخمن \(x_1\)، نبني السلسلة كاملة، نفحص إشارة \(R(x_1)\)، ثم نحسن التخمين. الشيفرة تحصر \(x_1\) داخل \((10^{-18},0.999999999999)\) وتنفذ 260 خطوة بحث ثنائي. وإذا أدت قيمة مجربة إلى خروج السلسلة من المجال المسموح أو إلى قيمة غير منتهية، ترفض تلك المحاولة ويعامل المتبقي على أنه \(+\infty\)، وهذا يدفع البحث بأمان نحو القيم الصحيحة.
بعد انتهاء البحث الثنائي، يعاد بناء السلسلة باستخدام القيمة النهائية لـ \(x_1\). ثم تفرض الشيفرة \(x_{m+1}=1\) صراحةً حتى تزيل الانحراف العددي الطفيف عند الحافة. بعد ذلك تحسب
$$Q=\sum_{i=0}^{m}(x_{i+1}-x_i)f(x_i)$$
ثم تعيد
$$A_N=4Q.$$
إذن فالمنهج العددي يتكون من مرحلتين واضحتين: أولاً حل معادلات المثالية مع شرط النهاية، ثم تقييم مساحة السلم الناتج.
عندما \(N=2\)، يكون \(m=1\). وتحدث النقطة المثلى عند
$$x_1=\frac{1}{\sqrt{2}}, \qquad f(x_1)=\frac{1}{\sqrt{2}},$$
ومن ثم
$$A_2=4\left(x_1+(1-x_1)f(x_1)\right)=4\sqrt{2}-2.$$
وهذا هو فحص التحقق الأول في برنامج C++.
وعندما \(N=10\)، يعطي shooting النقاط
$$0,\ 0.3800728430,\ 0.5627007923,\ 0.7071067812,\ 0.8266606428,\ 0.9249565579,\ 1,$$
وتكون المساحة الكلية
$$A_{10}\approx 3.3469640797.$$
وهذا هو فحص التحقق الثاني. أما عند التشغيل الافتراضي بالقيمة \(N=400\)، فإن جميع التطبيقات تطبع
$$A_{400}\approx 3.1486734435.$$
الدالة f(x) تحسب ارتفاع ربع الدائرة. وتقوم build_sequence بتخزين نقاط الفصل وتطبيق العلاقة التكرارية خطوةً خطوة. أما shooting_residual فتعيد القيمة \(R(x_1)\). وتنفذ solve_breakpoints حلقة البحث الثنائي ذات العدد الثابت من التكرارات، ثم تثبت الحد الأيمن عددياً. وأخيراً تجمع minimal_red_area مساحات الشرائط وتضرب الناتج في \(4\). وملفا Python و Java ترجمتان مباشرتان للطريقة نفسها، بينما تضيف نسخة C++ فحوص \(N=2\) و \(N=10\) قبل طباعة جواب \(N=400\).
لنكتب \(m=N/2\). إن استدعاء build_sequence الواحد يحسب \(m+1\) قيمة جديدة، ولذلك كلفته \(O(m)\) زمناً و \(O(m)\) ذاكرةً. وبما أن البحث الثنائي يجري 260 تقييماً ثابتاً للمتبقي، فإن الزمن الكلي في التطبيق هو \(O(260m)=O(N)\). وإذا رمزنا لعدد التكرارات بالحرف \(B\)، تصبح الكلفة \(O(BN)\) زمناً و \(O(N)\) ذاكرةً.