Βρίσκουμε τον N'ο αριθμό Fibonacci με τρεις τρόπους σε εύλογο χρόνο: τα βασικά του δυναμικού προγραμματισμού. Βρίσκουμε τον Ν' αριθμό Φιμπονάτσι με τρεις τρόπους σε εύλογο χρόνο: τα βασικά του δυναμικού προγραμματισμού Αναδρομικός υπολογισμός του ν' αριθμού της σειράς Fibonacci
Οι προγραμματιστές θα πρέπει να έχουν βαρεθεί με τους αριθμούς Fibonacci μέχρι τώρα. Παραδείγματα υπολογισμού τους χρησιμοποιούνται παντού. Αυτό συμβαίνει επειδή αυτοί οι αριθμοί παρέχουν το απλούστερο παράδειγμα αναδρομής. Είναι επίσης ένα καλό παράδειγμα δυναμικού προγραμματισμού. Είναι όμως απαραίτητο να τα υπολογίσουμε έτσι σε ένα πραγματικό έργο; Μην. Ούτε ο αναδρομικός ούτε ο δυναμικός προγραμματισμός είναι ιδανικές επιλογές. Και όχι ένας κλειστός τύπος που χρησιμοποιεί αριθμούς κινητής υποδιαστολής. Τώρα θα σας πω πώς να το κάνετε σωστά. Αλλά πρώτα, ας δούμε όλες τις γνωστές λύσεις.Ο κώδικας είναι για Python 3, αν και θα πρέπει να πάει και για Python 2.
Αρχικά, επιτρέψτε μου να σας υπενθυμίσω τον ορισμό:
F n = F n-1 + F n-2
Και F 1 = F 2 = 1.
Κλειστή φόρμουλα
Θα παραλείψουμε τις λεπτομέρειες, αλλά όσοι επιθυμούν μπορούν να εξοικειωθούν με την παραγωγή του τύπου. Η ιδέα είναι να υποθέσουμε ότι υπάρχει κάποιο x για το οποίο F n = x n, και μετά να βρούμε το x.Τι κάνει
Μείωση x n-2
Λύνουμε την τετραγωνική εξίσωση:
Πού μεγαλώνει η "χρυσή τομή" από ϕ = (1 + √5) / 2. Αντικαθιστώντας τις αρχικές τιμές και κάνοντας μερικούς ακόμη υπολογισμούς, παίρνουμε:
Αυτό που χρησιμοποιούμε για να υπολογίσουμε το F n.
Από __future__ εισαγωγική διαίρεση εισαγωγής μαθηματικών def fib (n): SQRT5 = math.sqrt (5) PHI = (SQRT5 + 1) / 2 int επιστροφής (PHI ** n / SQRT5 + 0,5)
Καλός:
Γρήγορο και εύκολο για μικρά ν
Κακό:
Απαιτούνται λειτουργίες κινητής υποδιαστολής. Το μεγάλο n θα απαιτήσει μεγαλύτερη ακρίβεια.
Κακό:
Η χρήση μιγαδικών αριθμών για τον υπολογισμό του F n είναι όμορφο από μαθηματική άποψη, αλλά άσχημο από την άποψη του υπολογιστή.
Αναδρομή
Η πιο προφανής λύση, που έχετε ήδη δει πολλές φορές, είναι πιθανότατα ως παράδειγμα του τι είναι η αναδρομή. Θα το επαναλάβω ξανά, για πληρότητα. Στην Python, μπορεί να γραφτεί σε μία γραμμή:Fib = λάμδα n: fib (n - 1) + fib (n - 2) εάν n> 2 other 1
Καλός:
Πολύ απλή υλοποίηση επαναλαμβάνοντας τον μαθηματικό ορισμό
Κακό:
Εκθετικός χρόνος εκτέλεσης. Πολύ αργό για μεγάλο n
Κακό:
Υπερχείλιση στοίβας
Απομνημόνευση
Η αναδρομική λύση έχει ένα μεγάλο πρόβλημα: τεμνόμενους υπολογισμούς. Όταν καλείται το fib (n), το fib (n-1) και το fib (n-2) μετράται. Αλλά όταν μετρηθεί το fib (n-1), θα μετρήσει και πάλι ανεξάρτητα το fib (n-2) - δηλαδή, το fib (n-2) μετράται δύο φορές. Αν συνεχίσουμε το σκεπτικό, θα δούμε ότι το fib (n-3) θα μετρηθεί τρεις φορές κ.ο.κ. Πάρα πολλές διασταυρώσεις.Επομένως, πρέπει απλώς να απομνημονεύσετε τα αποτελέσματα για να μην τα μετρήσετε ξανά. Ο χρόνος και η μνήμη για αυτή τη λύση καταναλώνονται με γραμμικό τρόπο. Χρησιμοποιώ ένα λεξικό στη λύση, αλλά θα μπορούσε να είχε χρησιμοποιηθεί και ένας απλός πίνακας.
M = (0: 0, 1: 1) def fib (n): εάν n σε M: επιστροφή M [n] M [n] = fib (n - 1) + fib (n - 2) επιστροφή M [n]
(Στην Python, αυτό μπορεί να γίνει και με το διακοσμητή, functools.lru_cache.)
Καλός:
Απλώς μετατρέψτε την αναδρομή σε λύση μνήμης. Μετατρέπει τον εκθετικό χρόνο εκτέλεσης σε γραμμικό χρόνο, ο οποίος καταναλώνει περισσότερη μνήμη.
Κακό:
Χάνει πολλή μνήμη
Κακό:
Πιθανή υπερχείλιση στοίβας, όπως η αναδρομή
Δυναμικός προγραμματισμός
Μετά την απόφαση με την ανάμνηση, γίνεται σαφές ότι δεν χρειαζόμαστε όλα τα προηγούμενα αποτελέσματα, αλλά μόνο τα δύο τελευταία. Εναλλακτικά, αντί να ξεκινάτε από το fib (n) και να περπατάτε προς τα πίσω, μπορείτε να ξεκινήσετε από το fib (0) και να περπατήσετε μπροστά. Ο παρακάτω κώδικας έχει γραμμικό χρόνο εκτέλεσης και σταθερή χρήση μνήμης. Στην πράξη, η ταχύτητα της λύσης θα είναι ακόμη μεγαλύτερη, αφού δεν υπάρχουν αναδρομικές κλήσεις συναρτήσεων και σχετικές εργασίες. Και ο κώδικας φαίνεται πιο απλός.Αυτή η λύση αναφέρεται συχνά ως παράδειγμα δυναμικού προγραμματισμού.
Def fib (n): a = 0 b = 1 για __ στην περιοχή (n): a, b = b, a + b επιστρέφουν a
Καλός:
Λειτουργεί γρήγορα για μικρό n, απλό κώδικα
Κακό:
Ακόμα γραμμικός χρόνος εκτέλεσης
Κακό:
Τίποτα ιδιαίτερο.
Άλγεβρα μήτρας
Και τέλος, η λιγότερο φωτισμένη, αλλά η πιο σωστή λύση, χρησιμοποιώντας σοφά και χρόνο και μνήμη. Μπορεί επίσης να επεκταθεί σε οποιαδήποτε ομοιογενή γραμμική ακολουθία. Η ιδέα είναι να χρησιμοποιηθούν πίνακες. Αρκεί μόνο να το δεις
Μια γενίκευση αυτού υποδηλώνει ότι
Οι δύο τιμές για το x που λάβαμε νωρίτερα, εκ των οποίων η μία ήταν η χρυσή τομή, είναι οι ιδιοτιμές του πίνακα. Επομένως, ένας άλλος τρόπος για να εξάγουμε έναν κλειστό τύπο είναι να χρησιμοποιήσετε μια εξίσωση πίνακα και μια γραμμική άλγεβρα.
Γιατί λοιπόν είναι χρήσιμο ένα τέτοιο σκεύασμα; Το γεγονός ότι η εκθετικότητα μπορεί να γίνει σε λογαριθμικό χρόνο. Αυτό γίνεται μέσω τετραγωνισμού. Η ουσία είναι ότι
Όπου η πρώτη έκφραση χρησιμοποιείται για άρτιο Α, η δεύτερη για περιττό. Απομένει μόνο να οργανώσετε τον πολλαπλασιασμό του πίνακα και τελειώσατε. Βγαίνει ο παρακάτω κώδικας. Έχω οργανώσει μια αναδρομική εφαρμογή του pow γιατί είναι πιο κατανοητό. Δείτε την επαναληπτική έκδοση εδώ.
Def pow (x, n, I, mult): "" "Επιστρέφει το x στην ντη δύναμη. Υποθέτουμε ότι I είναι ο πίνακας ταυτότητας πολλαπλασιασμένος με mult και n είναι ένας θετικός ακέραιος" "" εάν n == 0: επιστροφή I elif n == 1: επιστροφή x άλλο: y = pow (x, n // 2, I, mult) y = mult (y, y) εάν n% 2: y = mult (x, y) επιστροφή y def ταυτότητα_μήτρας ( n): "" "Επιστρέφει τον πίνακα ταυτότητας n-by-n" "" r = λίστα (εύρος (n)) επιστροφή [για j σε r] def matrix_multiply (A, B): BT = λίστα (zip (* B ) ) return [για row_a στο A] def fib (n): F = pow ([,], n, matrix_identity (2), matrix_multiply) return F
Καλός:
Σταθερό μέγεθος μνήμης, λογαριθμικός χρόνος
Κακό:
Πιο περίπλοκος κώδικας
Κακό:
Πρέπει να δουλέψουμε με πίνακες, αν και δεν είναι τόσο κακοί
Σύγκριση απόδοσης
Αξίζει μόνο να συγκρίνουμε την παραλλαγή του δυναμικού προγραμματισμού και τη μήτρα. Εάν τα συγκρίνουμε με τον αριθμό των ψηφίων του αριθμού n, τότε αποδεικνύεται ότι η λύση του πίνακα είναι γραμμική και η λύση με δυναμικό προγραμματισμό είναι εκθετική. Ένα πρακτικό παράδειγμα είναι ο υπολογισμός του fib (10 ** 6), ένας αριθμός που θα έχει περισσότερους από διακόσιες χιλιάδες χαρακτήρες.N = 10 ** 6
Υπολογισμός fib_matrix: το fib (n) έχει 208988 ψηφία συνολικά, ο υπολογισμός διήρκεσε 0,24993 δευτερόλεπτα.
Υπολογισμός fib_dynamic: το fib (n) έχει 208988 ψηφία συνολικά, χρειάστηκαν 11,83377 δευτερόλεπτα για τον υπολογισμό.
Θεωρητικές παρατηρήσεις
Χωρίς να αγγίζει άμεσα τον παραπάνω κώδικα, αυτή η παρατήρηση εξακολουθεί να έχει κάποιο ενδιαφέρον. Σκεφτείτε το ακόλουθο γράφημα:
Ας μετρήσουμε τον αριθμό των μονοπατιών μήκους n από το Α στο Β. Για παράδειγμα, για n = 1 έχουμε ένα μονοπάτι, 1. Για n = 2 έχουμε πάλι ένα μονοπάτι, 01. Για n = 3 έχουμε δύο μονοπάτια, 001 και 101 Μπορεί να αποδειχθεί πολύ απλά ότι ο αριθμός των μονοπατιών μήκους n από το Α στο Β είναι ακριβώς ίσος με το F n. Καταγράφοντας τον πίνακα γειτνίασης για το γράφημα, παίρνουμε τον ίδιο πίνακα που περιγράφηκε παραπάνω. Αυτό είναι ένα πολύ γνωστό αποτέλεσμα από τη θεωρία γραφημάτων ότι για έναν δεδομένο πίνακα γειτνίασης Α, οι εμφανίσεις στο A n είναι ο αριθμός των μονοπατιών μήκους n στο γράφημα (ένα από τα προβλήματα που αναφέρονται στην ταινία "Good Will Hunting").
Γιατί υπάρχουν τέτοια σημάδια στις άκρες; Αποδεικνύεται ότι όταν κοιτάζετε μια άπειρη ακολουθία χαρακτήρων σε μια άπειρη και προς τις δύο κατευθύνσεις ακολουθία μονοπατιών σε ένα γράφημα, λαμβάνετε κάτι που ονομάζεται "πεπερασμένες υπομετατοπίσεις", που είναι ένας τύπος συμβολικού δυναμικού συστήματος. Αυτή η συγκεκριμένη υπομετατόπιση του τελικού τύπου είναι γνωστή ως «μετατόπιση χρυσού λόγου» και προσδιορίζεται από ένα σύνολο «απαγορευμένων λέξεων» (11). Με άλλα λόγια, παίρνουμε άπειρες και προς τις δύο κατευθύνσεις δυαδικές ακολουθίες και κανένα ζευγάρι από αυτές δεν θα είναι γειτονικά. Η τοπολογική εντροπία αυτού του δυναμικού συστήματος είναι ίση με τη χρυσή αναλογία φ. Είναι ενδιαφέρον πώς αυτός ο αριθμός εμφανίζεται περιοδικά σε διάφορους τομείς των μαθηματικών.
Αριθμοί FibonacciΕίναι μια σειρά αριθμών στην οποία κάθε επόμενος αριθμός είναι ίσος με το άθροισμα των δύο προηγούμενων: 1, 1, 2, 3, 5, 8, 13, .... Μερικές φορές η σειρά ξεκινά από το μηδέν: 0, 1, 1, 2, 3, 5, .... Σε αυτή την περίπτωση, θα παραμείνουμε στην πρώτη επιλογή.
Τύπος:
F 1 = 1
F 2 = 1
F n = F n-1 + F n-2
Παράδειγμα υπολογισμού:
F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...
Υπολογισμός του nου αριθμού μιας σειράς Fibonacci χρησιμοποιώντας έναν βρόχο while
- Εκχωρήστε στις μεταβλητές fib1 και fib2 τις τιμές των δύο πρώτων στοιχείων της σειράς, δηλαδή αντιστοιχίστε μονάδες στις μεταβλητές.
- Ρωτήστε τον χρήστη για τον αριθμό του στοιχείου, την τιμή του οποίου θέλει να πάρει. Αντιστοιχίστε έναν αριθμό στη μεταβλητή n.
- Εκτελέστε τα ακόλουθα βήματα n - 2 φορές, αφού τα δύο πρώτα στοιχεία έχουν ήδη ληφθεί υπόψη:
- Προσθέστε fib1 και fib2, εκχωρώντας το αποτέλεσμα σε μια μεταβλητή προσωρινής αποθήκευσης, όπως το fib_sum.
- Ορίστε τη μεταβλητή fib1 σε fib2.
- Ορίστε τη μεταβλητή fib2 σε fib_sum.
- Εμφανίστε την τιμή fib2.
Σημείωση.Εάν ο χρήστης εισάγει 1 ή 2, το σώμα του βρόχου δεν εκτελείται ποτέ, εμφανίζεται η αρχική τιμή του fib2.
fib1 = 1 fib2 = 1 n = είσοδος () n = int (n) i = 0 ενώ i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
Συμπαγής έκδοση του κώδικα:
fib1 = fib2 = 1 n = int (είσοδος ( "Αριθμός στοιχείου της σειράς Fibonacci:")) - 2 ενώ n> 0: fib1, fib2 = fib2, fib1 + fib2 n - = 1 εκτύπωση (fib2)
Έξοδος αριθμών Fibonacci με βρόχο for
Σε αυτήν την περίπτωση, δεν εμφανίζεται μόνο η τιμή του απαιτούμενου στοιχείου της σειράς Fibonacci, αλλά και όλοι οι αριθμοί μέχρι και συμπεριλαμβανομένου αυτού. Για να γίνει αυτό, η έξοδος της τιμής fib2 τοποθετείται σε βρόχο.
fib1 = fib2 = 1 n = int (είσοδος ()) εάν n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
Παράδειγμα εκτέλεσης:
10 1 1 2 3 5 8 13 21 34 55
Αναδρομικός υπολογισμός του nου αριθμού της σειράς Fibonacci
- Εάν n = 1 ή n = 2, επιστρέψτε ένα στον κλάδο που καλεί, καθώς το πρώτο και το δεύτερο στοιχείο της σειράς Fibonacci είναι ίσα με ένα.
- Σε όλες τις άλλες περιπτώσεις, καλέστε την ίδια συνάρτηση με τα ορίσματα n - 1 και n - 2. Προσθέστε το αποτέλεσμα των δύο κλήσεων και επιστρέψτε το στον κλάδο του καλούντος προγράμματος.
def fibonacci (n): εάν n σε (1, 2): επιστροφή 1 επιστροφή fibonacci (n - 1) + fibonacci (n - 2) εκτύπωση (fibonacci (10))
Ας πούμε n = 4. Αυτό θα καλέσει αναδρομικά το fibonacci (3) και το fibonacci (2). Το δεύτερο θα επιστρέψει ένα και το πρώτο θα οδηγήσει σε δύο ακόμη κλήσεις συνάρτησης: fibonacci (2) και fibonacci (1). Και οι δύο κλήσεις θα επιστρέψουν μία, για συνολικά δύο. Έτσι, η κλήση στο fibonacci (3) επιστρέφει τον αριθμό 2, ο οποίος προστίθεται στον αριθμό 1 από την κλήση στο fibonacci (2). Το αποτέλεσμα 3 επιστρέφει στο mainstream. Το τέταρτο στοιχείο της σειράς Fibonacci είναι ίσο με τρία: 1 1 2 3.
Πολύ συχνά, σε διάφορες Ολυμπιάδες, συναντώνται προβλήματα όπως αυτό, τα οποία, όπως φαίνεται με την πρώτη ματιά, μπορούν να λυθούν με μια απλή αναζήτηση. Αλλά αν μετρήσουμε τον αριθμό των πιθανών επιλογών, τότε θα πειστούμε αμέσως για την αναποτελεσματικότητα αυτής της προσέγγισης: για παράδειγμα, η απλή αναδρομική συνάρτηση παρακάτω θα καταναλώσει σημαντικούς πόρους ήδη στον 30ο αριθμό Fibonacci, ενώ στις Ολυμπιάδες, ο χρόνος λύσης περιορίζεται συχνά σε 1-5 δευτερόλεπτα.
Int fibo (int n) (αν (n == 1 || n == 2) (return 1;) other (return fibo (n - 1) + fibo (n - 2);))
Ας σκεφτούμε γιατί συμβαίνει αυτό. Για παράδειγμα, για να υπολογίσουμε το fibo (30), υπολογίζουμε πρώτα το fibo (29) και το fibo (28). Ταυτόχρονα όμως, το πρόγραμμά μας «ξεχνάει» ότι fibo (28) εμείς έχει ήδη καταλάβειόταν ψάχνετε για fibo (29).
Το κύριο λάθος μιας τέτοιας προσέγγισης "κατά μέτωπο" είναι ότι οι ίδιες τιμές των ορισμάτων συνάρτησης υπολογίζονται πολλές φορές - και αυτές είναι λειτουργίες που απαιτούν αρκετά πόρους. Για να απαλλαγούμε από επαναλαμβανόμενους υπολογισμούς, θα μας βοηθήσει η μέθοδος δυναμικού προγραμματισμού - αυτή είναι μια τεχνική στην οποία ένα πρόβλημα χωρίζεται σε γενικές και επαναλαμβανόμενες δευτερεύουσες εργασίες, καθεμία από τις οποίες επιλύεται μόνο 1 φορά - αυτό αυξάνει σημαντικά την αποτελεσματικότητα του προγράμματος. Αυτή η μέθοδος περιγράφεται λεπτομερώς στο, υπάρχουν επίσης παραδείγματα επίλυσης άλλων προβλημάτων.
Ο απλούστερος τρόπος για να βελτιώσουμε τη λειτουργία μας είναι να θυμόμαστε ποιες τιμές έχουμε ήδη υπολογίσει. Για να γίνει αυτό, πρέπει να εισαγάγουμε έναν πρόσθετο πίνακα, ο οποίος θα χρησιμεύσει ως ένα είδος «κρυφής μνήμης» για τους υπολογισμούς μας: πριν υπολογίσουμε μια νέα τιμή, θα ελέγξουμε αν την έχουμε υπολογίσει πριν. Αν υπολογίσαμε, τότε θα πάρουμε την τελική τιμή από τον πίνακα, και αν δεν την υπολογίσαμε, θα πρέπει να την υπολογίσουμε με βάση τις προηγούμενες και να τη θυμηθούμε για το μέλλον:
Int cache? int fibo (int n) (if (cache [n] == 0) (if (n == 1 || n == 2) (cache [n] = 1;) other (cache [n] = fibo (n - 1) + fibo (n - 2);)) cache επιστροφής [n];)
Δεδομένου ότι σε αυτήν την εργασία, για να υπολογίσουμε την Nth τιμή, χρειαζόμαστε εγγυημένα (N-1) -th, δεν θα είναι δύσκολο να ξαναγράψουμε τον τύπο σε επαναληπτική μορφή - απλώς θα γεμίσουμε τον πίνακα μας στη σειρά μέχρι να φτάσουμε στο επιθυμητό κελί:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
Τώρα μπορούμε να παρατηρήσουμε ότι όταν υπολογίζουμε την τιμή του F (N), τότε η τιμή του F (N-3) είναι ήδη εγγυημένη για εμάς ποτέδεν θα χρειαστεί. Δηλαδή, χρειάζεται να αποθηκεύσουμε μόνο δύο τιμές στη μνήμη - F (N-1) και F (N-2). Επιπλέον, μόλις υπολογίσουμε το F (N), η αποθήκευση του F (N-2) χάνει κάθε νόημα. Ας προσπαθήσουμε να γράψουμε αυτές τις σκέψεις με τη μορφή κώδικα:
// Δύο προηγούμενες τιμές: int cache1 = 1; int cache2 = 1; // Νέα τιμή int cache3; για (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>Μετά την επανάληψη, η cache2 θα χάσει τη συνάφειά της, δηλ. θα πρέπει να γίνει cache1 // Με άλλα λόγια, cache1 - f (n-2), cache2 - f (n-1), cache3 - f (n). // Έστω N = n + 1 (ο αριθμός που υπολογίζουμε στην επόμενη επανάληψη). Τότε η-2 = Ν-3, η-1 = Ν-2, η = Ν-1. // Σύμφωνα με τις νέες πραγματικότητες, ξαναγράφουμε τις τιμές των μεταβλητών μας: cache1 = cache2; cache2 = cache3; ) κόουτ<< cache3;
Ένας έμπειρος προγραμματιστής καταλαβαίνει ότι ο παραπάνω κώδικας είναι, γενικά, ανοησία, καθώς η cache3 δεν χρησιμοποιείται ποτέ (γράφεται αμέσως στην cache2) και ολόκληρη η επανάληψη μπορεί να ξαναγραφτεί χρησιμοποιώντας μία μόνο έκφραση:
Προσωρινή μνήμη = 1; cache = 1; για (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
Για όσους δεν μπορούν να καταλάβουν πώς λειτουργεί η μαγεία με το modulus ή απλά θέλουν να δουν έναν πιο μη προφανή τύπο, υπάρχει μια άλλη λύση:
Int x = 1; int y = 1; για (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
Προσπαθήστε να ακολουθήσετε την εκτέλεση αυτού του προγράμματος: θα πειστείτε για την ορθότητα του αλγορίθμου.
ΥΣΤΕΡΟΓΡΑΦΟ. Γενικά, υπάρχει ένας μόνο τύπος για τον υπολογισμό οποιουδήποτε αριθμού Fibonacci που δεν απαιτεί επανάληψη ή αναδρομή:
Const double SQRT5 = sqrt (5); const διπλό PHI = (SQRT5 + 1) / 2; int fibo (int n) (return int (pow (PHI, n) / SQRT5 + 0,5);)
Αλλά, όπως μπορείτε να μαντέψετε, το αδιέξοδο είναι ότι το κόστος υπολογισμού των δυνάμεων των μη ακεραίων είναι αρκετά υψηλό, όπως και το σφάλμα τους.
