In the symmetric nanobot configuration, every bot follows the same geodesic-type path on the sphere, so the total travelled distance is \(T(n)=nL(n)\), where \(L(n)\) is the length assigned to one bot when there are \(n\) bots.
The C++, Python, and Java implementations do not simulate the full multi-bot motion directly. They reduce the geometry to one numerical integral depending only on \(n\), then search for the smallest integer \(n\ge 3\) such that
$$L(n) > 1000.$$
After locating that first threshold crossing, the reported value is the total distance
$$T(n)=nL(n),$$
printed to two decimal places.
Set
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
After the substitution \(u=\sin\theta\), where \(\theta\) is the colatitude from the geometric setup, the implementations evaluate
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
The rest of the method consists of evaluating this integral accurately and then searching the first \(n\) for which its value exceeds the target.
The rotational symmetry means every bot contributes the same path length. Therefore the global quantity of interest is obtained from a single scalar function \(L(n)\), and the full answer is simply
$$T(n)=nL(n).$$
This is why the implementations can ignore the detailed positions of the other bots once the single representative geodesic has been derived.
The dependence on \(n\) enters through the spacing parameter \(s=\sin(\pi/n)\). With the change of variable \(u=\sin\theta\), the arc-length formula becomes
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
This form isolates all \(n\)-dependence in a single parameter. The denominator \(1-u^2\) becomes small near \(u=1\), so the implementations evaluate the truncated model with the fixed cutoff \(u_0=0.999\); that is the exact numerical quantity used for the threshold test.
For \(f(u)=\sqrt{1-(su)^2}/(1-u^2)\), Simpson's rule on an interval \([a,b]\) is
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
The interval is bisected at \(m=(a+b)/2\). The implementations compare the coarse estimate \(S(a,b)\) with the refined estimate \(S(a,m)+S(m,b)\), using
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
as the local error signal. When \(|\Delta|\le 15\varepsilon\), the accepted corrected value is
$$S(a,m)+S(m,b)+\frac{\Delta}{15}.$$
Otherwise both halves are refined recursively. The tolerance is \(10^{-13}\), and the recursion depth cap is \(30\).
For fixed \(u\in[0,u_0]\), the integrand can be rewritten as
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
As \(n\) increases, \(s=\sin(\pi/n)\) decreases, so \(1/s^2\) increases. Therefore the integrand increases pointwise on the whole integration interval, and the computed \(L(n)\) is increasing as well. For large \(n\), \(s\sim \pi/n\), so \(L(n)\) grows on the order of \(1/s\), hence roughly linearly in \(n\). That guarantees the existence of a first threshold index
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
Because \(L(n)\) is monotone, the search is standard. Start from \(n=3\), repeatedly double an upper bound until the computed length exceeds \(1000\), and then binary-search inside that bracket. Once \(n_*\) is found, the final reported quantity is
$$T(n_*)=n_*L(n_*).$$
For three bots,
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
so the implemented integral becomes
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
Numerically, the implementation obtains
$$L(3)\approx 2.84.$$
This is the checkpoint used by the C++ version. The corresponding total distance is
$$T(3)\approx 3\times 2.84=8.52,$$
which is still far below \(1000\), so the threshold search must continue to much larger \(n\).
The C++, Python, and Java implementations all follow the same numerical pipeline. For a chosen \(n\), they compute \(s=\sin(\pi/n)\), evaluate the integrand at the two endpoints and the midpoint of \([0,0.999]\), build the initial Simpson estimate, and recursively refine only the subintervals whose local correction is too large.
Each successful integral evaluation returns one value \(L(n)\). Around that numerical kernel, the implementation first doubles an upper bound until \(L(n)>1000\), then uses binary search to isolate the smallest valid integer \(n\). The printed answer is the product \(nL(n)\), rounded to two decimal places.
The C++ implementation also performs explicit sanity checks: it verifies the \(n=3\) checkpoint and confirms that the final answer is truly the first threshold crossing by checking both \(L(n)\) and \(L(n-1)\).
Let \(Q(n)\) be the number of integrand evaluations used by the adaptive Simpson routine for one input \(n\). The threshold search requires \(O(\log n_*)\) length evaluations, so the total running time is
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
The memory usage is the recursion stack of the integrator, namely \(O(d)\), where \(d\) is the recursion depth. In the actual implementations, \(d\) is capped at \(30\).
In der symmetrischen Nanobot-Konfiguration legt jeder Bot dieselbe geodätische Bahn auf der Kugel zurück. Daher ist die gesamte Weglänge
$$T(n)=nL(n),$$
wobei \(L(n)\) die einem einzelnen Bot zugeordnete Länge bei \(n\) Bots ist.
Die C++-, Python- und Java-Implementierungen simulieren nicht die vollständige Mehrkörperbewegung. Stattdessen reduzieren sie die Geometrie auf ein einziges numerisches Integral in Abhängigkeit von \(n\) und suchen dann das kleinste ganze \(n\ge 3\) mit
$$L(n) > 1000.$$
Nach dieser ersten Überschreitung wird \(T(n)=nL(n)\) mit zwei Nachkommastellen ausgegeben.
Setze
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
Nach der Substitution \(u=\sin\theta\), wobei \(\theta\) die in der Geometrie verwendete Kolatitude ist, werten die Implementierungen aus:
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
Der Rest der Methode besteht darin, dieses Integral präzise zu berechnen und anschließend das erste \(n\) zu finden, für das der Zielwert überschritten wird.
Wegen der \(n\)-fachen Rotationssymmetrie trägt jeder Bot dieselbe Weglänge bei. Deshalb genügt eine einzige skalare Funktion \(L(n)\), und die gesuchte Gesamtgröße ist einfach
$$T(n)=nL(n).$$
Genau diese Reduktion erlaubt es dem Code, die übrigen Bots nach der Herleitung der repräsentativen Geodäte nicht mehr explizit verfolgen zu müssen.
Die Abhängigkeit von \(n\) steckt vollständig im Abstandsfaktor \(s=\sin(\pi/n)\). Nach der Variablentransformation \(u=\sin\theta\) wird die Bogenlänge zu
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
Diese Form isoliert alle \(n\)-Abhängigkeit in einem einzigen Parameter. Da der Nenner \(1-u^2\) in der Nähe von \(u=1\) klein wird, rechnen die Implementierungen mit dem abgeschnittenen Modell \(u_0=0.999\); genau diese numerische Größe wird mit der Schranke verglichen.
Für \(f(u)=\sqrt{1-(su)^2}/(1-u^2)\) lautet die Simpson-Regel auf \([a,b]\)
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
Das Intervall wird bei \(m=(a+b)/2\) halbiert. Verglichen werden die grobe Schätzung \(S(a,b)\) und die verfeinerte Summe \(S(a,m)+S(m,b)\), wobei
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
als lokales Fehlersignal dient. Wenn \(|\Delta|\le 15\varepsilon\) gilt, wird der korrigierte Wert
$$S(a,m)+S(m,b)+\frac{\Delta}{15}$$
akzeptiert; sonst wird auf beiden Hälften rekursiv weiter verfeinert. Die Toleranz ist \(10^{-13}\), die Tiefengrenze \(30\).
Für festes \(u\in[0,u_0]\) lässt sich der Integrand umschreiben zu
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
Wenn \(n\) wächst, dann sinkt \(s=\sin(\pi/n)\), also steigt \(1/s^2\). Damit wächst der Integrand punktweise auf dem ganzen Integrationsintervall, und folglich wächst auch \(L(n)\). Für große \(n\) gilt außerdem \(s\sim \pi/n\), also wächst \(L(n)\) in der Größenordnung von \(1/s\) und damit ungefähr linear in \(n\). So existiert sicher ein erster Schwellenindex
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
Weil \(L(n)\) monoton ist, ist die Suche standardisiert. Man startet bei \(n=3\), verdoppelt eine obere Schranke so lange, bis die berechnete Länge \(1000\) überschreitet, und führt danach eine Binärsuche im gefundenen Intervall aus. Für das gefundene \(n_*\) lautet das Endergebnis
$$T(n_*)=n_*L(n_*).$$
Für drei Bots gilt
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
also wird das implementierte Integral zu
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
Numerisch erhält die Implementierung
$$L(3)\approx 2.84.$$
Dies ist der Kontrollwert der C++-Version. Die zugehörige Gesamtweglänge beträgt
$$T(3)\approx 3\times 2.84=8.52,$$
also noch deutlich weniger als \(1000\); die Suche muss daher zu wesentlich größeren \(n\) weiterlaufen.
Die C++-, Python- und Java-Implementierungen benutzen denselben numerischen Ablauf. Für ein gegebenes \(n\) berechnen sie \(s=\sin(\pi/n)\), werten den Integranden an den beiden Randpunkten und am Mittelpunkt von \([0,0.999]\) aus, bauen daraus die erste Simpson-Näherung und verfeinern nur die Teilintervalle weiter, deren lokale Korrektur noch zu groß ist.
Jede erfolgreiche Integralberechnung liefert einen Wert \(L(n)\). Um diesen Kern herum verdoppelt die Implementierung zunächst eine obere Schranke, bis \(L(n)>1000\) gilt, und verwendet anschließend Binärsuche, um das kleinste zulässige \(n\) zu isolieren. Ausgegeben wird dann das Produkt \(nL(n)\), gerundet auf zwei Nachkommastellen.
Die C++-Implementierung enthält zusätzlich explizite Plausibilitätsprüfungen: Sie testet den Kontrollwert für \(n=3\) und verifiziert am Ende, dass wirklich die erste Überschreitung gefunden wurde, indem sowohl \(L(n)\) als auch \(L(n-1)\) geprüft werden.
Sei \(Q(n)\) die Anzahl der Integrand-Auswertungen, die die adaptive Simpson-Quadratur für einen Wert \(n\) benötigt. Die Schwellenwertsuche benötigt \(O(\log n_*)\) Längenberechnungen, also insgesamt
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
Der Speicherbedarf ist der Rekursionsstack des Integrators, also \(O(d)\) mit Rekursionstiefe \(d\). In den tatsächlichen Implementierungen ist \(d\) durch \(30\) beschränkt.
Simetrik nanobot düzeninde her robot küre üzerinde aynı jeodezik türü yolu izler. Bu yüzden toplam gidilen mesafe
$$T(n)=nL(n),$$
burada \(L(n)\), \(n\) robot varken tek bir robota düşen yol uzunluğudur.
C++, Python ve Java uygulamaları tüm çoklu-robot hareketini doğrudan benzetmez. Bunun yerine geometriyi yalnızca \(n\)'ye bağlı tek bir sayısal integrale indirger ve sonra
$$L(n) > 1000$$
koşulunu sağlayan en küçük \(n\ge 3\) değerini arar. İlk eşik geçildiğinde raporlanan sonuç iki ondalık basamakla \(T(n)=nL(n)\) olur.
Şunu tanımlayalım:
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
\(\theta\) küresel geometride kullanılan kolatitud iken \(u=\sin\theta\) değişken dönüşümü yapıldığında, uygulamaların hesapladığı ifade
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du$$
olur. Yöntemin geri kalanı bu integrali hassas biçimde hesaplamak ve sonra değeri eşiği aşan ilk \(n\)'yi bulmaktan ibarettir.
\(n\)-kat dönel simetri nedeniyle her robot aynı yol uzunluğunu katkılar. Dolayısıyla küresel problem tek bir skaler fonksiyon \(L(n)\) ile belirlenir ve toplam cevap
$$T(n)=nL(n)$$
şeklindedir. Kodun diğer robotların konumlarını açıkça taşımamasının nedeni budur.
\(n\)'ye bağlılık yalnızca \(s=\sin(\pi/n)\) parametresi üzerinden gelir. \(u=\sin\theta\) dönüşümünden sonra yay uzunluğu
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du$$
biçimine iner. Böylece bütün \(n\)-bağımlılığı tek parametrede toplanır. \(u=1\) civarında \(1-u^2\) küçüldüğü için uygulamalar sabit kesim noktası \(u_0=0.999\) ile çalışır; eşik testinde kullanılan sayısal büyüklük tam olarak budur.
\(f(u)=\sqrt{1-(su)^2}/(1-u^2)\) için Simpson kuralı \([a,b]\) aralığında
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right)$$
şeklindedir. Aralık \(m=(a+b)/2\) noktasında ikiye ayrılır. Kaba tahmin \(S(a,b)\) ile inceltilmiş toplam \(S(a,m)+S(m,b)\) karşılaştırılır ve
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
yerel hata sinyali olarak kullanılır. \(|\Delta|\le 15\varepsilon\) olduğunda kabul edilen düzeltilmiş değer
$$S(a,m)+S(m,b)+\frac{\Delta}{15}$$
olur; aksi halde her iki yarıda özyinelemeli inceltme sürer. Tolerans \(10^{-13}\), derinlik sınırı ise \(30\)'dur.
Sabit bir \(u\in[0,u_0]\) için integrand
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}$$
şeklinde yazılabilir. \(n\) büyüdükçe \(s=\sin(\pi/n)\) küçülür, dolayısıyla \(1/s^2\) büyür. Bu yüzden integrand tüm aralıkta noktasal olarak artar ve hesaplanan \(L(n)\) de artar. Ayrıca büyük \(n\) için \(s\sim \pi/n\) olduğundan \(L(n)\) kabaca \(1/s\) mertebesinde, yani yaklaşık doğrusal biçimde büyür. Böylece
$$n_*=\min\{n\ge 3:L(n)>1000\}$$
şeklinde ilk eşik indeksi kesin olarak vardır.
\(L(n)\) monoton olduğundan arama klasik hale gelir. \(n=3\)'ten başlanır, üst sınır değer \(L(n)\) 1000'i geçene kadar iki katına çıkarılır, sonra bulunan aralıkta ikili arama yapılır. Bulunan \(n_*\) için son cevap
$$T(n_*)=n_*L(n_*)$$
olur.
Üç robot için
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
dolayısıyla hesaplanan integral
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du$$
olur. Sayısal olarak uygulama
$$L(3)\approx 2.84$$
değerini üretir. Bu, C++ sürümündeki kontrol noktasıdır. Buna karşılık toplam mesafe
$$T(3)\approx 3\times 2.84=8.52$$
olur; bu da \(1000\)'den çok küçüktür ve aramanın daha büyük \(n\) değerlerine devam etmesi gerektiğini gösterir.
C++, Python ve Java uygulamaları aynı sayısal akışı izler. Verilen bir \(n\) için önce \(s=\sin(\pi/n)\) hesaplanır, sonra \([0,0.999]\) aralığının iki uç noktasında ve orta noktasında integrand değerlendirilir, ilk Simpson tahmini kurulup yalnızca yerel düzeltmesi büyük olan alt aralıklar özyinelemeli olarak inceltilir.
Her başarılı integral hesabı tek bir \(L(n)\) değeri döndürür. Bu çekirdeğin etrafında uygulama önce \(L(n)>1000\) olana kadar üst sınırı iki katına çıkarır, ardından en küçük geçerli tamsayıyı bulmak için ikili arama uygular. Yazdırılan sonuç iki ondalık basamakla \(nL(n)\) çarpımıdır.
C++ uygulaması ayrıca açık doğrulamalar içerir: \(n=3\) kontrol noktasını sınar ve sonucun gerçekten ilk eşik geçişi olduğunu görmek için hem \(L(n)\) hem de \(L(n-1)\) değerlerini kontrol eder.
Adaptive Simpson yordamının tek bir \(n\) için kullandığı integrand değerlendirme sayısına \(Q(n)\) diyelim. Eşik araması \(O(\log n_*)\) adet uzunluk hesabı gerektirir; dolayısıyla toplam çalışma süresi
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n)$$
olur. Bellek kullanımı integratörün özyineleme yığınıdır; yani \(O(d)\). Gerçek uygulamalarda \(d\) değeri \(30\) ile sınırlandırılmıştır.
En la configuración simétrica de nanobots, cada bot recorre la misma trayectoria geodésica sobre la esfera. Por tanto, la distancia total recorrida es
$$T(n)=nL(n),$$
donde \(L(n)\) es la longitud asignada a un solo bot cuando hay \(n\) bots.
Las implementaciones en C++, Python y Java no simulan directamente todo el movimiento colectivo. Reducen la geometría a una sola integral numérica que depende de \(n\) y luego buscan el menor entero \(n\ge 3\) tal que
$$L(n) > 1000.$$
Una vez encontrado ese primer cruce, el valor que se informa es \(T(n)=nL(n)\), redondeado a dos decimales.
Definimos
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
Tras el cambio de variable \(u=\sin\theta\), donde \(\theta\) es la colatitud usada en la construcción geométrica, las implementaciones evalúan
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
El resto del método consiste en calcular esta integral con precisión y después localizar el primer \(n\) cuyo valor supera el objetivo.
La simetría rotacional implica que todos los bots aportan la misma longitud. Así, toda la magnitud global queda determinada por una sola función escalar \(L(n)\), y la respuesta completa es
$$T(n)=nL(n).$$
Por eso las implementaciones pueden olvidarse de las posiciones detalladas de los demás bots una vez obtenida la geodésica representativa.
La dependencia respecto de \(n\) entra únicamente a través del parámetro \(s=\sin(\pi/n)\). Después del cambio \(u=\sin\theta\), la longitud de arco toma la forma
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
Esta expresión concentra toda la dependencia en un solo parámetro. Como el denominador \(1-u^2\) se vuelve pequeño cuando \(u\) se acerca a \(1\), las implementaciones trabajan con el modelo truncado \(u_0=0.999\); esa es exactamente la cantidad numérica que se compara con el umbral.
Para \(f(u)=\sqrt{1-(su)^2}/(1-u^2)\), la regla de Simpson en un intervalo \([a,b]\) es
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
Se parte el intervalo en \(m=(a+b)/2\). Las implementaciones comparan la estimación gruesa \(S(a,b)\) con la estimación refinada \(S(a,m)+S(m,b)\), usando
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
como señal local de error. Cuando \(|\Delta|\le 15\varepsilon\), se acepta el valor corregido
$$S(a,m)+S(m,b)+\frac{\Delta}{15}.$$
Si no, ambas mitades se refinan recursivamente. La tolerancia es \(10^{-13}\) y la profundidad máxima de recursión es \(30\).
Para un \(u\) fijo en \([0,u_0]\), el integrando puede reescribirse como
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
Cuando \(n\) aumenta, \(s=\sin(\pi/n)\) disminuye, de modo que \(1/s^2\) aumenta. Por tanto, el integrando crece punto a punto en todo el intervalo y también crece \(L(n)\). Además, para \(n\) grande, \(s\sim \pi/n\), así que \(L(n)\) es del orden de \(1/s\), es decir, crece aproximadamente de manera lineal con \(n\). Esto garantiza la existencia de un primer índice
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
Como \(L(n)\) es monótona, la búsqueda es directa. Se empieza en \(n=3\), se duplica una cota superior hasta que la longitud calculada supera \(1000\), y luego se aplica búsqueda binaria dentro del intervalo obtenido. Una vez hallado \(n_*\), la cantidad final es
$$T(n_*)=n_*L(n_*).$$
Para tres bots,
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
de modo que la integral implementada es
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
Numéricamente, la implementación obtiene
$$L(3)\approx 2.84.$$
Ese es el punto de control utilizado en la versión en C++. La distancia total correspondiente es
$$T(3)\approx 3\times 2.84=8.52,$$
muy por debajo de \(1000\), así que la búsqueda debe continuar hacia valores de \(n\) mucho mayores.
Las implementaciones en C++, Python y Java siguen el mismo esquema numérico. Para un \(n\) dado, calculan \(s=\sin(\pi/n)\), evalúan el integrando en los dos extremos y en el punto medio de \([0,0.999]\), forman la primera estimación de Simpson y refinan recursivamente solo aquellos subintervalos cuya corrección local aún es demasiado grande.
Cada evaluación exitosa de la integral produce un valor \(L(n)\). Alrededor de ese núcleo numérico, la implementación primero duplica una cota superior hasta que \(L(n)>1000\) y después usa búsqueda binaria para aislar el menor entero válido. El resultado impreso es el producto \(nL(n)\), redondeado a dos decimales.
La implementación en C++ añade además comprobaciones explícitas: valida el punto de control \(n=3\) y confirma que la respuesta final es realmente el primer cruce del umbral comprobando tanto \(L(n)\) como \(L(n-1)\).
Sea \(Q(n)\) el número de evaluaciones del integrando usadas por Simpson adaptativo para un valor concreto de \(n\). La búsqueda del umbral requiere \(O(\log n_*)\) evaluaciones de longitud, por lo que el tiempo total es
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
La memoria es la pila recursiva del integrador, es decir, \(O(d)\), donde \(d\) es la profundidad de la recursión. En las implementaciones reales, \(d\) está acotada por \(30\).
在这个具有旋转对称性的纳米机器人构型里，每个机器人在球面上走的是同一种测地线路径，因此总路程可以写成
$$T(n)=nL(n),$$
其中 \(L(n)\) 表示有 \(n\) 个机器人时，单个机器人的路径长度。
C++、Python 和 Java 三个实现都没有直接模拟所有机器人的完整运动过程。它们先把几何问题压缩成一个只依赖 \(n\) 的数值积分，再寻找最小的整数 \(n\ge 3\)，使得
$$L(n) > 1000.$$
找到第一次越过阈值的位置后，最终输出的是
$$T(n)=nL(n),$$
并按两位小数格式化。
记
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
把几何推导中的余纬变量 \(\theta\) 改写为 \(u=\sin\theta\) 之后，三个实现实际计算的是
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
后续工作只有两件事：把这个积分算准，以及找到第一个使它超过目标值的 \(n\)。
由于构型具有 \(n\) 重旋转对称性，每个机器人贡献的路径长度完全相同。因此全局问题可以由一个标量函数 \(L(n)\) 完全描述，总答案只是
$$T(n)=nL(n).$$
这也是为什么实现里不需要显式跟踪其它机器人的位置；一旦代表性测地线路径被推出，剩下的就是求单条路径的长度。
与 \(n\) 有关的部分都浓缩在参数 \(s=\sin(\pi/n)\) 里。做变量代换 \(u=\sin\theta\) 后，弧长公式变成
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
这样写的好处是，所有关于 \(n\) 的影响都通过一个参数进入。由于分母 \(1-u^2\) 在 \(u\to 1\) 时会变得很小，三个实现都把积分上限固定截断在 \(u_0=0.999\)；程序实际拿去和阈值比较的正是这个截断后的数值模型。
设 \(f(u)=\sqrt{1-(su)^2}/(1-u^2)\)。在区间 \([a,b]\) 上，Simpson 公式为
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
把区间在中点 \(m=(a+b)/2\) 处分成两半，分别计算左右两段的 Simpson 估计，再把它们的和与粗略估计 \(S(a,b)\) 比较：
$$\Delta=S(a,m)+S(m,b)-S(a,b).$$
这里的 \(\Delta\) 就是局部误差信号。当 \(|\Delta|\le 15\varepsilon\) 时，接受修正后的结果
$$S(a,m)+S(m,b)+\frac{\Delta}{15}.$$
否则就在左右两个子区间上继续递归细分。实现中使用的误差容忍度是 \(10^{-13}\)，递归深度上限是 \(30\)。
对固定的 \(u\in[0,u_0]\)，被积函数可以改写成
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
当 \(n\) 增大时，\(s=\sin(\pi/n)\) 变小，因此 \(1/s^2\) 变大。于是整个被积函数在积分区间上逐点增大，所以计算得到的 \(L(n)\) 也是单调增大的。进一步地，当 \(n\) 很大时，\(s\sim \pi/n\)，于是 \(L(n)\) 的量级与 \(1/s\) 相同，也就是大致按 \(n\) 线性增长。这保证了第一次越过阈值的位置一定存在：
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
既然 \(L(n)\) 对 \(n\) 单调，搜索策略就很直接。先从 \(n=3\) 开始，不断把上界翻倍，直到计算得到的长度超过 \(1000\)；然后在这个区间里做二分查找，锁定最小可行整数 \(n_*\)。最后答案就是
$$T(n_*)=n_*L(n_*).$$
当 \(n=3\) 时，
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
所以实现中计算的积分为
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
数值结果约为
$$L(3)\approx 2.84.$$
这正是 C++ 实现里使用的检查点。于是三台机器人对应的总路程约为
$$T(3)\approx 3\times 2.84=8.52,$$
远小于 \(1000\)，因此搜索必须继续到更大的 \(n\)。
C++、Python 和 Java 三个实现遵循同一条数值流程。对于给定的 \(n\)，先计算 \(s=\sin(\pi/n)\)，在区间 \([0,0.999]\) 的左右端点和中点上计算被积函数值，构造初始 Simpson 估计，然后只对局部修正仍然过大的子区间继续递归细分。
每次成功的积分计算都会返回一个 \(L(n)\)。围绕这个数值核心，程序先不断倍增上界，直到 \(L(n)>1000\)；随后使用二分查找隔离最小满足条件的整数 \(n\)。最后输出的就是 \(nL(n)\)，并保留两位小数。
C++ 实现还多做了两项显式校验：先验证 \(n=3\) 时的检查点，再通过同时检查 \(L(n)\) 与 \(L(n-1)\) 来确认最终结果确实是第一次越过阈值的位置。
设自适应 Simpson 积分在某个输入 \(n\) 上总共使用了 \(Q(n)\) 次被积函数求值。整个阈值搜索需要 \(O(\log n_*)\) 次长度计算，因此总时间复杂度为
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
空间复杂度来自积分器的递归栈，即 \(O(d)\)，其中 \(d\) 是递归深度。在实际实现中，\(d\) 的上限固定为 \(30\)。
В симметричной конфигурации наноботов каждый бот проходит одну и ту же геодезическую траекторию на сфере. Поэтому полная длина пути равна
$$T(n)=nL(n),$$
где \(L(n)\) обозначает длину пути одного бота при \(n\) ботах.
Реализации на C++, Python и Java не моделируют сразу все траектории. Они сводят геометрию к одному численному интегралу, зависящему только от \(n\), а затем ищут наименьшее целое \(n\ge 3\), для которого
$$L(n) > 1000.$$
После нахождения этого первого пересечения порога выводится значение \(T(n)=nL(n)\) с двумя знаками после запятой.
Обозначим
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
После замены переменной \(u=\sin\theta\), где \(\theta\) есть колатитуда из геометрической постановки, реализации вычисляют
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
Дальнейшая работа состоит в том, чтобы аккуратно посчитать этот интеграл и затем найти первое \(n\), при котором его значение превышает заданную границу.
\(n\)-кратная вращательная симметрия означает, что каждый бот вносит одну и ту же длину пути. Следовательно, вся глобальная величина определяется одной скалярной функцией \(L(n)\), а полный ответ равен
$$T(n)=nL(n).$$
Именно поэтому реализации могут не отслеживать явно остальные траектории после того, как получена одна представительная геодезическая линия.
Вся зависимость от \(n\) входит через параметр \(s=\sin(\pi/n)\). После замены \(u=\sin\theta\) формула длины дуги принимает вид
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
Такой вид удобен тем, что вся зависимость от \(n\) собрана в одном параметре. Поскольку знаменатель \(1-u^2\) становится малым при \(u\to 1\), реализации используют усеченную модель с фиксированной верхней границей \(u_0=0.999\); именно эту численную величину программа сравнивает с порогом.
Для функции \(f(u)=\sqrt{1-(su)^2}/(1-u^2)\) формула Симпсона на отрезке \([a,b]\) имеет вид
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
Отрезок делится пополам в точке \(m=(a+b)/2\). Реализации сравнивают грубую оценку \(S(a,b)\) с уточненной суммой \(S(a,m)+S(m,b)\), используя
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
как локальный индикатор ошибки. Если \(|\Delta|\le 15\varepsilon\), принимается скорректированное значение
$$S(a,m)+S(m,b)+\frac{\Delta}{15}.$$
Иначе обе половины уточняются рекурсивно. Точность установлена как \(10^{-13}\), а максимальная глубина рекурсии равна \(30\).
Для фиксированного \(u\in[0,u_0]\) подынтегральное выражение можно переписать так:
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
Когда \(n\) растет, \(s=\sin(\pi/n)\) убывает, значит \(1/s^2\) возрастает. Поэтому подынтегральная функция возрастает поточечно на всем интервале, а вместе с ней возрастает и вычисляемое значение \(L(n)\). Кроме того, при больших \(n\) выполняется \(s\sim \pi/n\), так что \(L(n)\) имеет порядок \(1/s\), то есть растет примерно линейно по \(n\). Это гарантирует существование первого индекса
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
Так как \(L(n)\) монотонна, поиск устроен стандартно. Сначала берут \(n=3\), затем удваивают верхнюю границу, пока вычисленная длина не станет больше \(1000\), после чего выполняют бинарный поиск внутри найденного интервала. Для найденного \(n_*\) итоговая величина равна
$$T(n_*)=n_*L(n_*).$$
Для трех ботов
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
поэтому используемый в коде интеграл имеет вид
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
Численно реализация получает
$$L(3)\approx 2.84.$$
Это контрольная точка, присутствующая в версии на C++. Соответствующая полная длина пути равна
$$T(3)\approx 3\times 2.84=8.52,$$
что намного меньше \(1000\), поэтому поиск продолжается для существенно больших \(n\).
Реализации на C++, Python и Java используют один и тот же численный конвейер. Для заданного \(n\) они вычисляют \(s=\sin(\pi/n)\), считают подынтегральную функцию в концах и в середине отрезка \([0,0.999]\), строят начальную формулу Симпсона и рекурсивно уточняют только те подотрезки, где локальная поправка еще слишком велика.
Каждое успешное вычисление интеграла возвращает одно значение \(L(n)\). Поверх этого численного ядра реализация сначала удваивает верхнюю границу, пока не выполнится \(L(n)>1000\), а затем применяет бинарный поиск, чтобы выделить минимальное допустимое целое \(n\). Печатается произведение \(nL(n)\), округленное до двух знаков после запятой.
В реализации на C++ есть и явные проверки корректности: она подтверждает контрольную точку для \(n=3\) и отдельно удостоверяется, что найден именно первый переход через порог, проверяя значения \(L(n)\) и \(L(n-1)\).
Пусть \(Q(n)\) обозначает число вычислений подынтегральной функции, требуемых адаптивному методу Симпсона для одного значения \(n\). Поиск порога требует \(O(\log n_*)\) вычислений длины, поэтому общая трудоемкость равна
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
Память определяется стеком рекурсии интегратора, то есть это \(O(d)\), где \(d\) есть глубина рекурсии. В фактических реализациях глубина ограничена числом \(30\).
في الترتيب المتماثل للنانو-روبوتات يسلك كل روبوت المسار الجيوديسي نفسه على سطح الكرة، ولذلك فإن المسافة الكلية المقطوعة تساوي
$$T(n)=nL(n),$$
حيث تمثل \(L(n)\) طول المسار الخاص بروبوت واحد عندما يكون عدد الروبوتات هو \(n\).
تنفيذات C++ وPython وJava لا تحاكي الحركة الكاملة لجميع الروبوتات مباشرة. بدلًا من ذلك تختزل الهندسة إلى تكامل عددي واحد يعتمد فقط على \(n\)، ثم تبحث عن أصغر عدد صحيح \(n\ge 3\) يحقق
$$L(n) > 1000.$$
وبعد تحديد أول تجاوز لهذه العتبة تكون القيمة المعروضة هي \(T(n)=nL(n)\) مع تقريب إلى منزلتين عشريتين.
لنعرّف
$$s=\sin\left(\frac{\pi}{n}\right),\qquad u_0=0.999.$$
بعد تبديل المتغير إلى \(u=\sin\theta\)، حيث تمثل \(\theta\) زاوية الميل المستعملة في الصياغة الهندسية، تصبح الكمية التي تحسبها التنفيذات هي
$$L(n)=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
وبعد ذلك تنحصر المهمة في حساب هذا التكامل بدقة، ثم العثور على أول \(n\) تجعل قيمته تتجاوز الحد المطلوب.
بسبب التناظر الدوراني من الرتبة \(n\)، يضيف كل روبوت طول المسار نفسه. لذلك يكفي التعامل مع دالة عددية واحدة \(L(n)\)، وتصبح الإجابة الكلية ببساطة
$$T(n)=nL(n).$$
ولهذا السبب لا تحتاج التنفيذات إلى تتبع مواقع بقية الروبوتات صراحة بعد اشتقاق الجيوديسية الممثلة الواحدة.
كل اعتماد على \(n\) يدخل عبر المعامل \(s=\sin(\pi/n)\). وبعد التحويل \(u=\sin\theta\) تأخذ صيغة طول القوس الشكل
$$L(n)=\int_0^{u_0}\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}\,du=\frac{1}{s}\int_0^{u_0}\frac{\sqrt{1-(su)^2}}{1-u^2}\,du.$$
هذه الصياغة تجمع كل أثر \(n\) في معامل واحد. ولأن المقام \(1-u^2\) يصبح صغيرًا عندما يقترب \(u\) من \(1\)، تعمل التنفيذات على نموذج مقطوع بحد علوي ثابت هو \(u_0=0.999\)؛ وهذه هي بالضبط الكمية العددية التي تُقارن مع العتبة.
إذا كانت
$$f(u)=\frac{\sqrt{1-(su)^2}}{1-u^2},$$
فإن قاعدة Simpson على الفترة \([a,b]\) تكتب على الصورة
$$S(a,b)=\frac{b-a}{6}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right).$$
تُقسم الفترة عند \(m=(a+b)/2\). ثم تقارن التنفيذات بين التقدير الخشن \(S(a,b)\) وبين المجموع المحسن \(S(a,m)+S(m,b)\)، مع استعمال
$$\Delta=S(a,m)+S(m,b)-S(a,b)$$
بوصفه إشارة الخطأ المحلي. فإذا تحقق الشرط \(|\Delta|\le 15\varepsilon\)، تُقبل القيمة المصححة
$$S(a,m)+S(m,b)+\frac{\Delta}{15}.$$
وإلا يستمر التنقيح العودي في كلا النصفين. قيمة السماحية هي \(10^{-13}\)، وحد عمق العودية هو \(30\).
لـ \(u\) ثابتة ضمن \([0,u_0]\)، يمكن إعادة كتابة الدالة تحت التكامل بالشكل
$$\frac{1}{s}\frac{\sqrt{1-(su)^2}}{1-u^2}=\frac{\sqrt{\frac{1}{s^2}-u^2}}{1-u^2}.$$
وعندما يزداد \(n\) فإن \(s=\sin(\pi/n)\) يتناقص، وبالتالي يزداد \(1/s^2\). لذلك تزداد الدالة تحت التكامل نقطةً بنقطة على كامل فترة التكامل، ومن ثم تزداد أيضًا القيمة المحسوبة \(L(n)\). إضافة إلى ذلك، عندما يكون \(n\) كبيرًا نحصل على \(s\sim \pi/n\)، ولذلك يكون \(L(n)\) من رتبة \(1/s\)، أي إنه ينمو تقريبًا نموًا خطيًا مع \(n\). وهذا يضمن وجود أول فهرس يحقق العتبة:
$$n_*=\min\{n\ge 3:L(n)>1000\}.$$
بما أن \(L(n)\) دالة رتيبة، فإن طريقة البحث تصبح مباشرة. نبدأ من \(n=3\)، ثم نضاعف حدًا علويًا حتى تتجاوز القيمة المحسوبة \(1000\)، وبعد ذلك نطبّق بحثًا ثنائيًا داخل المجال المحصور. وعند الوصول إلى \(n_*\) تكون الكمية النهائية هي
$$T(n_*)=n_*L(n_*).$$
عندما \(n=3\) يكون
$$s=\sin\left(\frac{\pi}{3}\right)=\frac{\sqrt{3}}{2},$$
ومن ثم يصبح التكامل الذي تحسبه التنفيذات
$$L(3)=\frac{2}{\sqrt{3}}\int_0^{0.999}\frac{\sqrt{1-\frac{3u^2}{4}}}{1-u^2}\,du.$$
عدديًا تعطي التنفيذات
$$L(3)\approx 2.84.$$
وهذه هي نقطة الفحص الموجودة في نسخة C++. أما المسافة الكلية المناظرة فهي
$$T(3)\approx 3\times 2.84=8.52,$$
وهي أصغر كثيرًا من \(1000\)، ولذلك يستمر البحث نحو قيم أكبر بكثير لـ \(n\).
تنفيذات C++ وPython وJava تتبع السلسلة العددية نفسها. فلكل قيمة \(n\) تُحسب أولًا \(s=\sin(\pi/n)\)، ثم تُقيَّم الدالة تحت التكامل عند طرفي الفترة \([0,0.999]\) وعند منتصفها، ويُبنى تقدير Simpson الأول، ثم لا تُعاد التجزئة عوديًا إلا على المقاطع التي ما زالت تصحيحاتها المحلية كبيرة.
كل حساب ناجح للتكامل يعيد قيمة واحدة \(L(n)\). وحول هذا القلب العددي يقوم التنفيذ أولًا بمضاعفة حد علوي حتى يتحقق \(L(n)>1000\)، ثم يستخدم البحث الثنائي لعزل أصغر عدد صحيح صالح. والنتيجة المطبوعة هي حاصل الضرب \(nL(n)\) مقربًا إلى منزلتين عشريتين.
وتضيف نسخة C++ فحوصًا صريحة للصحة: فهي تتحقق من نقطة الفحص عند \(n=3\)، ثم تؤكد أن الجواب النهائي هو فعلًا أول تجاوز للعتبة من خلال فحص كل من \(L(n)\) و\(L(n-1)\).
لنرمز بـ \(Q(n)\) إلى عدد مرات تقييم الدالة تحت التكامل التي يحتاجها Simpson التكيفي عند قيمة واحدة من \(n\). يتطلب البحث عن العتبة \(O(\log n_*)\) من حسابات الطول، ولذلك يكون الزمن الكلي
$$O\!\left(Q_{\max}\log n_*\right),\qquad Q_{\max}=\max_{3\le n\le n_*}Q(n).$$
أما الذاكرة فمصدرها مكدس العودية الخاص بالمكامل، أي \(O(d)\)، حيث \(d\) هو عمق العودية. وفي التنفيذات الفعلية يكون \(d\) محصورًا بالقيمة \(30\).