Ο κώδικας είναι για Python 3, αν και θα πρέπει να λειτουργεί και για Python 2.
Αρχικά, επιτρέψτε μου να σας υπενθυμίσω τον ορισμό:
F n \u003d F n-1 + F n-2
Και F 1 \u003d F 2 \u003d 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 return int(PHI ** n / SQRT5 + 0,5)
Καλός:
Γρήγορο και εύκολο για μικρά ν
Κακό:
Απαιτούνται πράξεις κινητής υποδιαστολής. Το μεγαλύτερο n θα απαιτήσει μεγαλύτερη ακρίβεια.
Κακό:
Η χρήση μιγαδικών αριθμών για τον υπολογισμό του F n είναι όμορφη από μαθηματική άποψη, αλλά άσχημη από υπολογιστή.
αναδρομή
Η πιο προφανής λύση, που έχετε ήδη δει πολλές φορές - πιθανότατα ως παράδειγμα του τι είναι η αναδρομή. Θα το επαναλάβω για πληρότητα. Στην Python, μπορεί να γραφτεί σε μία γραμμή:fib = λάμδα n: fib(n - 1) + fib(n - 2) εάν n > 2 other 1
Καλός:
Μια πολύ απλή υλοποίηση που επαναλαμβάνει τον μαθηματικό ορισμό
Κακό:
Εκθετικός χρόνος εκτέλεσης. Για μεγάλα ν πολύ αργά
Κακό:
Υπερχείλιση στοίβας
απομνημόνευση
Η αναδρομική λύση έχει ένα μεγάλο πρόβλημα: επικαλυπτόμενους υπολογισμούς. Όταν καλείται το 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 στην ισχύ του n. Υποθέτει ότι I είναι ο πίνακας ταυτότητας που πολλαπλασιάζεται με mult και n είναι ένας θετικός ακέραιος """ εάν n == 0: επιστροφή I elif n == 1: επιστροφή x else: y = pow(x, n // 2, I, mult) y = mult(y, y) εάν n % 2: y = mult(x, y) επιστροφή y def ταυτότητα_μήτρας (n): """Επιστρέφει έναν πίνακα ταυτότητας n κατά n""" r = list(range(n)) return [για j σε r] def matrix_multiply(A, B): BT = list(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, οι εμφανίσεις στο A n είναι ο αριθμός των μονοπατιών μήκους n στο γράφημα (ένα από τα προβλήματα που αναφέρονται στην ταινία Good Will Hunting).
Γιατί υπάρχουν τέτοιοι χαρακτηρισμοί στις άκρες; Αποδεικνύεται ότι όταν εξετάζετε μια άπειρη ακολουθία συμβόλων σε μια άπειρη και προς τις δύο κατευθύνσεις ακολουθία μονοπατιών σε ένα γράφημα, λαμβάνετε κάτι που ονομάζεται "υπομετατόπιση πεπερασμένου τύπου", που είναι ένας τύπος συστήματος συμβολικής δυναμικής. Η συγκεκριμένη στροφή τελικός τύποςγνωστή ως «μετατόπιση χρυσού λόγου» και δίνεται από ένα σύνολο «απαγορευμένων λέξεων» (11). Με άλλα λόγια, θα λάβουμε δυαδικές ακολουθίες που είναι άπειρες και στις δύο κατευθύνσεις και κανένα ζευγάρι από αυτές δεν θα είναι γειτονικά. Η τοπολογική εντροπία αυτού του δυναμικού συστήματος είναι ίση με τη χρυσή αναλογία φ. Είναι ενδιαφέρον πώς αυτός ο αριθμός εμφανίζεται περιοδικά σε διαφορετικούς τομείς των μαθηματικών.
Αριθμοί Fibonacci- αυτή είναι μια σειρά αριθμών στους οποίους κάθε επόμενος αριθμός είναι ίσος με το άθροισμα των δύο προηγούμενων: 1, 1, 2, 3, 5, 8, 13, .... Μερικές φορές η σειρά ξεκινά από το μηδέν: 0, 1, 1, 2, 3, 5, .... Σε αυτή την περίπτωση, θα παραμείνουμε στην πρώτη επιλογή.
Τύπος:
F1=1
F2 = 1
F n \u003d F n-1 + F n-2
Παράδειγμα υπολογισμού:
F 3 \u003d F 2 + F 1 \u003d 1 + 1 \u003d 2
F 4 \u003d F 3 + F 2 \u003d 2 + 1 \u003d 3
F 5 \u003d F 4 + F 3 \u003d 3 + 2 \u003d 5
F 6 \u003d F 5 + F 4 \u003d 5 + 3 \u003d 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=input() 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(input( "Αριθμός στοιχείου της σειράς 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 ) : return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )
Ας πούμε n = 4. Τότε οι fibonacci(3) και fibonacci(2) θα κληθούν αναδρομικά. Το δεύτερο θα επιστρέψει ένα και το πρώτο θα οδηγήσει σε δύο ακόμη κλήσεις συνάρτησης: fibonacci(2) και fibonacci(1). Και οι δύο κλήσεις θα επιστρέψουν μία, για συνολικά δύο. Έτσι, η κλήση στο fibonacci(3) επιστρέφει τον αριθμό 2, ο οποίος προστίθεται στον αριθμό 1 από την κλήση στο fibonacci(2). Το αποτέλεσμα 3 επιστρέφεται στον κύριο κλάδο του προγράμματος. Το τέταρτο στοιχείο της σειράς Fibonacci είναι τρία: 1 1 2 3.
Πολύ συχνά σε διάφορες Ολυμπιάδες υπάρχουν προβλήματα όπως αυτό, τα οποία, εκ πρώτης όψεως, φαίνεται ότι μπορούν να λυθούν με μια απλή απαρίθμηση. Αν όμως μετρήσουμε τον αριθμό επιλογές, τότε θα δούμε αμέσως την αναποτελεσματικότητα αυτής της προσέγγισης: για παράδειγμα, μια απλή αναδρομική συνάρτηση παρακάτω θα καταναλώσει σημαντικούς πόρους ήδη στον 30ο αριθμό Fibonacci, ενώ στις Ολυμπιάδες ο χρόνος λύσης συχνά περιορίζεται στα 1-5 δευτερόλεπτα.
int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( 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]; )
Δεδομένου ότι σε αυτήν την εργασία είναι εγγυημένο ότι χρειαζόμαστε (N-1)η τιμή για να υπολογίσουμε την τιμή N, δεν θα είναι δύσκολο να ξαναγράψουμε τον τύπο σε επαναληπτική μορφή - απλά θα συμπληρώσουμε τον πίνακα μας σε μια σειρά μέχρι να φτάσουμε στο επιθυμητό κελί:
<= 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) και ολόκληρη η επανάληψη μπορεί να ξαναγραφτεί χρησιμοποιώντας μία μόνο έκφραση:
cache=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;
Για όσους δεν μπορούν να καταλάβουν πώς λειτουργεί το modulo magic ή απλά θέλουν να δουν έναν πιο μη προφανή τύπο, υπάρχει μια άλλη λύση:
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); )
Αλλά, όπως μπορείτε να μαντέψετε, το αλίευμα είναι ότι το τίμημα του υπολογισμού των δυνάμεων των μη ακέραιων αριθμών είναι αρκετά μεγάλο, όπως και το σφάλμα τους.