1. Fortsetzungsbruch:
Jede reelle Zahl x kann als Kettenbruch ausgedrückt werden:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Abgekürzt als: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (ganzzahliger Teil von x)
- Wenn x keine ganze Zahl ist, sei x₁ = 1/(x - a₀) und fahre fort mit a₁ = ⌊x₁⌋
- Wiederholen Sie diesen Vorgang, um a₂, a₃, ... zu erhalten.
- Die Kettenbruchentwicklung rationaler Zahlen ist endlich
- Die Kettenbruchentwicklung irrationaler Zahlen ist unendlich
2. Konvergenten:
Der durch Abfangen der ersten n Terme eines Kettenbruchs erhaltene Bruch wird als n-ter asymptotischer Bruch bezeichnet und als pn/qn aufgezeichnet:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Rekursionsformel: pn = an·p(n-1) + p(n-2)
- Rekursionsformel: qn = an·q(n-1) + q(n-2)
- Ein asymptotischer Bruch ist die beste rationale Annäherung an die ursprüngliche Zahl
3. Beste rationale Näherung:
- Finden Sie für eine gegebene reelle Zahl x und eine Obergrenze des Nenners Q den Bruch p/q (q ≤ Q), so dass |x - p/q| minimiert wird
- Asymptotische Brüche von Kettenbrüchen liefern die besten rationalen Näherungen
- Wenn p/q ein asymptotischer Bruchteil von x ist, dann gilt für alle q' < q, |x - p/q| < |x - p'/q'|
4. Kettenbrüche spezieller Zahlen:
- Goldener Schnitt φ:[1; 1, 1, 1, 1, ...] (Alle 1, langsamste Konvergenz)
- √2:[1; 2, 2, 2, 2, ...] (periodischer Kettenbruch)
- e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regelmäßig)
- π:[3; 7, 15, 1, 292, 1, ...] (kein offensichtliches Muster)
Komplexität des Algorithmus:
- Zeitkomplexität:O(n)，Dabei ist n die Anzahl der zu erweiternden Terme
- Raumkomplexität:O(n)，Alle Koeffizienten und asymptotischen Brüche müssen gespeichert werden
- Numerische Stabilität:Verwenden Sie hochpräzise Gleitkommazahlen oder große Ganzzahlen, um Präzisionsverluste zu vermeiden
Anwendungsszenarien:
- Numerische Berechnung:Verwenden Sie einfache Brüche, um komplexe irrationale Zahlen anzunähern (z. B. π ≈ 22/7, 355/113)
- Musiktheorie:Intervallharmonie hängt mit der Einfachheit von Kettenbruchentwicklungen zusammen
- Astronomie:Rationale Näherung zur Berechnung der Periode der Planetenbewegung
- Zahlentheorie:Diophantische Näherung, Lösung der Pell-Gleichung
- Computergrafik:Bresenham-Geradenalgorithmus usw.