1. Frazione continua:
Qualsiasi numero reale x può essere espresso come frazione continua:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Abbreviato come: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (parte intera di x)
- Se x non è un intero, sia x₁ = 1/(x - a₀) e continuiamo con a₁ = ⌊x₁⌋
- Ripetere questo processo per ottenere a₂, a₃, ...
- Lo sviluppo in frazioni continue dei numeri razionali è finito
- L’espansione frazionaria continua dei numeri irrazionali è infinita
2. Convergenti:
La frazione ottenuta intercettando i primi n termini di una frazione continua è detta n-esima frazione asintotica, registrata come pn/qn:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Formula di ricorsione: pn = an·p(n-1) + p(n-2)
- Formula di ricorsione: qn = an·q(n-1) + q(n-2)
- Una frazione asintotica è la migliore approssimazione razionale del numero originale
3. Migliore approssimazione razionale:
- Per un dato numero reale x e un limite superiore al denominatore Q, trovare la frazione p/q (q ≤ Q) tale che |x - p/q| sia minimizzato
- Le frazioni asintotiche di frazioni continue forniscono tutte le migliori approssimazioni razionali
- Se p/q è una frazione asintotica di x, allora per ogni q' < q, |x - p/q| < |x - p'/q'|
4. Frazioni continue di numeri speciali:
- Sezione aurea φ:[1; 1, 1, 1, 1, ...] (Tutti 1, convergenza più lenta)
- √2:[1; 2, 2, 2, 2, ...] (frazione continua periodica)
- e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regolarmente)
- π:[3; 7, 15, 1, 292, 1, ...] (nessuno schema evidente)
Complessità dell'algoritmo:
- Complessità temporale:O(n)，dove n è il numero di termini da espandere
- Complessità spaziale:O(n)，Tutti i coefficienti e le frazioni asintotiche devono essere memorizzati
- Stabilità numerica:Utilizzare numeri a virgola mobile ad alta precisione o numeri interi di grandi dimensioni per evitare perdite di precisione
Scenari applicativi:
- Calcolo numerico:Utilizzare frazioni semplici per approssimare numeri irrazionali complessi (ad esempio π ≈ 22/7, 355/113)
- Teoria musicale:L'armonia degli intervalli è legata alla semplicità delle espansioni delle frazioni continue
- astronomia:Approssimazione razionale per il calcolo del periodo del moto planetario
- Teoria dei numeri:Approssimazione diofantea, soluzione dell'equazione di Pell
- Grafica computerizzata:Algoritmo di linea retta di Bresenham, ecc.