Υπολογιστής Fibonacci

Ξεκινώντας με 1, 1, κάθε επόμενος αριθμός είναι το άθροισμα των δύο προηγούμενων.

Έτσι δημιουργείται η διάσημη ακολουθία: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Καθώς οι αριθμοί Fibonacci μεγαλώνουν, ο λόγος μεταξύ διαδοχικών όρων προσεγγίζει τη χρυσή τομή φ ≈ 1.618.

Αυτός ο λόγος εμφανίζεται παντού στη φύση, την τέχνη και την αρχιτεκτονική.

Ένας αριθμός Fibonacci είναι οποιοσδήποτε όρος της ακολουθίας στην οποία κάθε τιμή ισούται με το άθροισμα των δύο προηγούμενων, ξεκινώντας με 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Ο κανόνας είναι F(n) = F(n-1) + F(n-2), με αρχικές τιμές F(1) = F(2) = 1.

Η ακολουθία πήρε το όνομά της από τον Ιταλό μαθηματικό του 13ου αιώνα Λεονάρντο της Πίζας, γνωστό ως Φιμπονάτσι, και έγινε δημοφιλής μέσα από το βιβλίο του Liber Abaci (1202) με ένα πρόβλημα αναπαραγωγής κουνελιών.

Όπως σημειώνει το Wolfram MathWorld, πρόκειται για μία από τις πιο μελετημένες ακολουθίες ακεραίων στα μαθηματικά, καταγεγραμμένη ως ακολουθία A000045 στο OEIS.

Για να βρείτε απευθείας τον ν-οστό αριθμό Φιμπονάτσι χωρίς να παραθέσετε κάθε προηγούμενο όρο, χρησιμοποιήστε τον τύπο του Binet: F(n) = (φⁿ − ψⁿ) / √5, όπου φ = (1 + √5)/2 ≈ 1.6180339887 είναι η χρυσή τομή και ψ = (1 − √5)/2 ≈ −0.6180339887.

Επειδή η απόλυτη τιμή |ψ| είναι μικρότερη από 1, το ψⁿ πλησιάζει στο μηδέν, επομένως το F(n) είναι απλώς ο πλησιέστερος ακέραιος στο φⁿ/√5. Για παράδειγμα, φ¹⁰/√5 ≈ 55.004, το οποίο στρογγυλοποιείται σε F(10) = 55.

Η Ψηφιακή Βιβλιοθήκη Μαθηματικών Συναρτήσεων του NIST (DLMF) τεκμηριώνει αυτή την κλειστή μορφή μαζί με σχετικές ταυτότητες αριθμών Lucas.

Ο 10ος αριθμός Φιμπονάτσι είναι το 55 όταν η ακολουθία ξεκινά την αρίθμηση από το F(1) = 1. Η καταμέτρηση των όρων στη σειρά δίνει 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, οπότε η δέκατη τιμή είναι το 55.

Η αρίθμηση έχει σημασία: ορισμένες αναφορές, συμπεριλαμβανομένων τμημάτων της καταχώρισης OEIS, ξεκινούν από το F(0) = 0, γεγονός που μετατοπίζει κάθε θέση κατά μία μονάδα και θα καθιστούσε τη δέκατη αναγραφόμενη τιμή το 34.

Αυτός ο υπολογιστής χρησιμοποιεί τη συνήθη σύμβαση με βάση το 1, F(1) = F(2) = 1. Επιβεβαιώνετε πάντα αν μια πηγή ξεκινά την μέτρηση από το F(0) ή το F(1) πριν συγκρίνετε αποτελέσματα.

Ένας θετικός ακέραιος N είναι αριθμός Φιμπονάτσι αν και μόνο αν το 5N² + 4 ή το 5N² − 4 είναι τέλειο τετράγωνο. Αυτός ο έλεγχος προέρχεται από την αλγεβρική δομή πίσω από τον τύπο του Binet και σας επιτρέπει να επαληθεύσετε την ιδιότητα αυτή χωρίς να δημιουργήσετε ολόκληρη την ακολουθία.

Πάρτε το N = 13: 5 × 13² − 4 = 5 × 169 − 4 = 841 = 29², ένα τέλειο τετράγωνο, επομένως το 13 είναι αριθμός Φιμπονάτσι.

Αντίθετα, το N = 20 αποτυγχάνει και στους δύο ελέγχους (5 × 400 + 4 = 2004 και 5 × 400 − 4 = 1996 δεν είναι τετράγωνα), οπότε το 20 δεν είναι αριθμός Φιμπονάτσι.

Το Khan Academy καλύπτει τη λογική των τέλειων τετραγώνων στην οποία βασίζεται αυτή η ταυτότητα.

Το άθροισμα των πρώτων n αριθμών Φιμπονάτσι ισούται με F(n+2) − 1, μια κομψή ταυτότητα που αποφεύγει την προσθήκη όρων έναν προς έναν. Για τους πρώτους 10 αριθμούς, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143, που συμπίπτει με το F(12) − 1 = 144 − 1 = 143.

Αξίζει επίσης να γνωρίζετε δύο σχετικές ταυτότητες:

• το άθροισμα των πρώτων n περιττών όρων ισούται με F(2n)
• το άθροισμα των τετραγώνων F(1)² + … + F(n)² ισούται με F(n) × F(n+1)

Το Wolfram MathWorld περιλαμβάνει αυτούς τους τύπους αθροίσματος στα κλασικά αποτελέσματα κλειστής μορφής της ακολουθίας.

Ο λόγος των διαδοχικών αριθμών Φιμπονάτσι συγκλίνει στη χρυσή τομή φ ≈ 1.6180339887 καθώς οι όροι μεγαλώνουν. Οι αρχικοί λόγοι ταλαντώνονται γύρω από το φ: 55/34 ≈ 1.6176 και 89/55 ≈ 1.6182, πλησιάζοντας όλο και περισσότερο σε κάθε βήμα.

Αυτό συμβαίνει επειδή ο τύπος του Binet καθιστά το φⁿ τον κυρίαρχο όρο. Σύμφωνα με την Encyclopaedia Britannica, το φ ικανοποιεί την εξίσωση φ² = φ + 1, επομένως το φ ≈ 1.618 και ο αντίστροφός του 1/φ ≈ 0.618 διαφέρουν ακριβώς κατά 1.

Η ίδια σταθερά εμφανίζεται στις διαγωνίους του πενταγώνου και στις λογαριθμικές σπείρες, γι' αυτό και οι λόγοι Φιμπονάτσι επανεμφανίζονται στη γεωμετρία και το design.

Οι αριθμοί Φιμπονάτσι εμφανίζονται σε πολύ περισσότερα πεδία από τα σχολικά βιβλία.

• Στη φύση, τα σπόρια του ηλίανθου, τα λέπια των κουκουναριών και τα οστρακοειδή ναυτίλος διατάσσονται κατά μήκος σπειρών που σχετίζονται με την ακολουθία Φιμπονάτσι για μέγιστη πυκνότητα, ένα φαινόμενο που τεκμηριώνεται από την Encyclopaedia Britannica.
• Στην πληροφορική, χρησιμοποιούνται για την αξιολόγηση της αναδρομής και του δυναμικού προγραμματισμού — με τον ίδιο τρόπο που ένας υπολογιστής παραγοντικού κάνει για την άλλη κλασική αναδρομική تعریف — και εμφανίζονται σε σωρούς Φιμπονάτσι και αλγόριθμους αναζήτησης.
• Στα χρηματοοικονομικά, οι αναλυτές χρησιμοποιούν επίπεδα αναδιοργάνωσης (retracement) Φιμπονάτσι (23.6%, 38.2%, 61.8%) που προκύπτουν από τους λόγους της ακολουθίας.
• Οι ομάδες ανάπτυξης λογισμικού (Agile) χρησιμοποιούν ακόμη και μια κλίμακα τύπου Φιμπονάτσι (1, 2, 3, 5, 8, 13) για την εκτίμηση μεγέθους εργασιών (story points), καθώς τα αυξανόμενα κενά αντανακλούν τη μεγαλύτερη αβεβαιότητα στις πιο σύνθετες εργασίες.

Ορισμένα συχνά λάθη μπερδεύουν τους χρήστες:

• Το πιο συχνό σφάλμα είναι η σύγχυση δεικτών: η ανάμειξη της σύμβασης F(0) = 0 με τη σύμβαση F(1) = 1 μετατοπίζει κάθε όρο κατά μία θέση και παράγει αποτελέσματα που διαφέρουν κατά ένα βήμα.
• Παγίδα αποτελεί επίσης η εμπιστοσύνη στον τύπο του Binet για πολύ μεγάλα n σε έναν απλό υπολογιστή, όπου η στρογγυλοποίηση κινητής υποδιαστολής μπορεί να δώσει λάθος πλησιέστερο ακέραιο· η επαναληπτική πρόσθεση ή η αριθμητική μεγάλων ακεραίων παραμένει ακριβής.
• Άλλοι υποθέτουν εσφαλμένα ότι κάθε μεγάλος αριθμός είναι Φιμπονάτσι χωρίς να εφαρμόσουν τον έλεγχο τέλειου τετραγώνου 5N² ± 4, ή ξεχνούν ότι το 1 εμφανίζεται δύο φορές στην αρχή.
• Τέλος, θυμηθείτε ότι κανένας αρνητικός δείκτης δεν δίνει όρο κάτω από το F(1) σε αυτό το εργαλείο.

Οι αριθμοί Φιμπονάτσι ανήκουν σε μια ευρύτερη οικογένεια αναδρομικών σχέσεων δεύτερης τάξης που μοιράζονται τον κανόνα όρος = προηγούμενος + προ-προηγούμενος, αλλά χρησιμοποιούν διαφορετικές αρχικές τιμές.

Οι αριθμοί Lucas ξεκινούν με 2, 1, 3, 4, 7, 11, 18 και είναι καταχωρισμένοι ως ακολουθία OEIS A000032· ικανοποιούν τη σχέση L(n) = φⁿ + ψⁿ και συνδέονται στενά με τους Φιμπονάτσι μέσω ταυτοτήτων όπως F(2n) = F(n) × L(n). Οι αριθμοί Pell (1, 2, 5, 12, 29) ακολουθούν διαφορετικό πολλαπλασιαστή.

Η μελέτη αυτών των σχετικών ακολουθιών, όπως αναλύει το Wolfram MathWorld, διευκρινίζει γιατί η χρυσή τομή καθορίζει τον ρυθμό αύξησης ολόκληρης της οικογένειας.