1. Συνεχές κλάσμα:
Κάθε πραγματικός αριθμός x μπορεί να εκφραστεί ως συνεχές κλάσμα:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Συντομογραφία: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (ακέραιο μέρος του x)
- Αν το x δεν είναι ακέραιος, θέτουμε x₁ = 1/(x - a₀), συνεχίζουμε με a₁ = ⌊x₁⌋
- Επαναλαμβάνουμε τη διαδικασία για a₂, a₃, ...
- Η ανάπτυξη ρητού αριθμού σε συνεχές κλάσμα είναι πεπερασμένη
- Η ανάπτυξη αρρήτου αριθμού σε συνεχές κλάσμα είναι άπειρη
2. Συγκλίνοντα κλάσματα:
Το κλάσμα από τους πρώτους n όρους ονομάζεται n-οστό συγκλίνον κλάσμα, συμβολίζεται pn/qn:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Αναδρομικός τύπος: pn = an·p(n-1) + p(n-2)
- Αναδρομικός τύπος: qn = an·q(n-1) + q(n-2)
- Τα συγκλίνοντα κλάσματα είναι οι καλύτερες ρητές προσεγγίσεις του αρχικού αριθμού
3. Καλύτερη ρητή προσέγγιση:
- Για έναν πραγματικό αριθμό x και άνω φράγμα Q παρονομαστή, βρείτε το κλάσμα p/q (q ≤ Q) που ελαχιστοποιεί το |x - p/q|
- Τα συγκλίνοντα κλάσματα δίνουν όλες τις καλύτερες ρητές προσεγγίσεις
- Αν το p/q είναι συγκλίνον κλάσμα του x, τότε για κάθε q' < q, |x - p/q| < |x - p'/q'|
4. Συνεχή κλάσματα ειδικών αριθμών:
- Χρυσή τομή φ:[1; 1, 1, 1, 1, ...] (Όλα μονάδες, αργότερη σύγκλιση)
- √2:[1; 2, 2, 2, 2, ...] (Περιοδικό συνεχές κλάσμα)
- e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Κανονικό μοτίβο)
- π:[3; 7, 15, 1, 292, 1, ...] (Χωρίς εμφανές μοτίβο)
Πολυπλοκότητα αλγορίθμου:
- Χρονική πολυπλοκότητα:O(n)，όπου n είναι ο αριθμός των όρων ανάπτυξης
- Χωρική πολυπλοκότητα:O(n)，Απαιτείται αποθήκευση όλων των συντελεστών και συγκλινόντων κλασμάτων
- Αριθμητική σταθερότητα:Χρήση αριθμών κινητής υποδιαστολής υψηλής ακρίβειας ή μεγάλων ακεραίων αποτρέπει απώλεια ακρίβειας
Σενάρια εφαρμογής:
- Αριθμητικός υπολογισμός:Προσέγγιση σύνθετων αρρήτων με απλά κλάσματα (π.χ. π ≈ 22/7, 355/113)
- Θεωρία μουσικής:Η αρμονία διαστημάτων σχετίζεται με την απλότητα των αναπτύξεων σε συνεχή κλάσματα
- Αστρονομία:Ρητές προσεγγίσεις για υπολογισμό τροχιακών περιόδων πλανητών
- Θεωρία αριθμών:Διοφαντικές προσεγγίσεις, λύσεις εξίσωσης Pell
- Γραφικά υπολογιστών:Αλγόριθμος γραμμής Bresenham και άλλα