1. Fraction continue :
Tout nombre réel x peut être exprimé sous forme de fraction continue :
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
En abrégé : x = [a₀ ; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (partie entière de x)
- Si x n'est pas un entier, soit x₁ = 1/(x - a₀) et continuez avec a₁ = ⌊x₁⌋
- Répétez ce processus pour obtenir a₂, a₃, ...
- L’expansion continue des fractions des nombres rationnels est finie
- L’expansion continue des fractions des nombres irrationnels est infinie
2. Convergents :
La fraction obtenue en interceptant les n premiers termes d'une fraction continue est appelée la n-ième fraction asymptotique, enregistrée sous la forme pn/qn :
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Formule de récursion : pn = an·p(n-1) + p(n-2)
- Formule de récursion : qn = an·q(n-1) + q(n-2)
- Une fraction asymptotique est la meilleure approximation rationnelle du nombre original
3. Meilleure approximation rationnelle :
- Pour un nombre réel donné x et une borne supérieure sur le dénominateur Q, trouver la fraction p/q (q ≤ Q) telle que |x - p/q| soit minimisée
- Les fractions asymptotiques de fractions continues donnent toutes les meilleures approximations rationnelles
- Si p/q est une fraction asymptotique de x, alors pour tout q' < q, |x - p/q| < |x - p'/q'|
4. Fractions continues de nombres spéciaux :
- Nombre d'or φ :[1; 1, 1, 1, 1, ...] (Tous 1, convergence la plus lente)
- √2 :[1; 2, 2, 2, 2, ...] (fraction continue périodique)
- e：[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (有规律)
- π：[3; 7, 15, 1, 292, 1, ...] (无明显规律)
算法复杂度：
- Complexité temporelle :O(n)，où n est le nombre de termes à développer
- Complexité spatiale :O(n)，Tous les coefficients et fractions asymptotiques doivent être stockés
- Stabilité numérique :Utilisez des nombres à virgule flottante de haute précision ou de grands entiers pour éviter toute perte de précision
Scénarios d'application :
- Calcul numérique :Utiliser des fractions simples pour approximer des nombres irrationnels complexes (par exemple π ≈ 22/7, 355/113)
- Théorie musicale :L'harmonie des intervalles est liée à la simplicité des expansions de fractions continues
- astronomie:approximation rationnelle pour calculer la période de mouvement planétaire
- Théorie des nombres :approximation diophantienne, solution de l'équation de Pell
- Infographie :Algorithme de ligne droite de Bresenham, etc.