Έννοια των αριθμών Fibonacci
Οι αριθμοί Fibonacci είναι μια συγκεκριμένη ακολουθία θετικών ακεραίων, ξεκινώντας από το 0. Οι ακέραιοι αριθμοί είναι θετικοί ακέραιοι. Έτσι, ένας αριθμός Fibonacci είναι μια συγκεκριμένη ακολουθία ακέραιων αριθμών ή φυσικών αριθμών, ξεκινώντας από το 0. Σε αυτήν την ακολουθία, οι δύο πρώτοι αριθμοί είναι 0 και 1, με αυτή τη σειρά. Οι υπόλοιποι αριθμοί αναπτύσσονται από εκεί προσθέτοντας τους δύο προηγούμενους αριθμούς. Οι πρώτοι δώδεκα αριθμοί Fibonacci λαμβάνονται ως εξής:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Με άλλα λόγια, οι πρώτοι δώδεκα αριθμοί Fibonacci είναι:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Φυσικά, ο δέκατος τρίτος αριθμός θα ήταν: 144 = 55 + 89. Οι αριθμοί Fibonacci μπορεί να φανταστούμε ότι βρίσκονται σε έναν πίνακα, όπως:
| 0 | 1 | 1 | δύο | 3 | 5 | 8 | 13 | είκοσι ένα | 3. 4 | 55 | 89 |
Ένας πίνακας έχει ευρετήρια. Στον παρακάτω πίνακα, η δεύτερη σειρά δείχνει τους αντίστοιχους μηδενικούς δείκτες για τους αριθμούς Fibonacci σε έναν πίνακα:
| 0 | 1 | 1 | δύο | 3 | 5 | 8 | 13 | είκοσι ένα | 3. 4 | 55 | 89 |
| 0 | 1 | δύο | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | έντεκα |
Με μηδενικούς δείκτες, αν υπάρχουν δώδεκα στοιχεία, τότε ο τελευταίος δείκτης είναι 11.
Οι αριθμοί Fibonacci μπορούν να παραχθούν σε χρόνο O(n) ή σε χρόνο O(1). Σε αυτές τις εκφράσεις πολυπλοκότητας χρόνου, το n σημαίνει n κύριες λειτουργίες και το 1 σημαίνει 1 κύρια λειτουργία. Με το O(n), παράγονται n αριθμοί Fibonacci, ξεκινώντας από το 0. Με το O(1), ένας αριθμός Fibonacci παράγεται από τον αντίστοιχο δείκτη. Αυτός είναι ο λόγος για τον οποίο το O(1) παίρνει μόνο μία κύρια λειτουργία αντί για n κύριες πράξεις.
Ο στόχος αυτού του άρθρου είναι να εξηγήσει πώς να παράγετε αριθμούς Fibonacci, με κάθε τρόπο, χρησιμοποιώντας JavaScript, η οποία είναι στην πραγματικότητα ECMAScript σήμερα.
Περιβάλλον Κωδικοποίησης
Το περιβάλλον node.js δεν θα χρησιμοποιηθεί όπως θα περίμενε ο αναγνώστης. Αντίθετα, το πρόγραμμα περιήγησης θα χρησιμοποιηθεί για την ερμηνεία του κώδικα και την εμφάνιση των αποτελεσμάτων. Το σενάριο (κώδικας) θα πρέπει να γραφτεί σε ένα αρχείο επεξεργασίας κειμένου, το οποίο θα πρέπει να αποθηκευτεί με την επέκταση '.html'. Το σενάριο θα πρέπει να έχει ως ελάχιστο κωδικό:
DOCTYPE HTML >< html >
< κεφάλι >
< τίτλος > Αριθμοί Fibonacci με JavaScript τίτλος >
κεφάλι >
< σώμα >
< τύπο σεναρίου = 'κείμενο/κείμενο' >
γραφή >
σώμα >
html >
Αυτός είναι ένας κατά προσέγγιση ελάχιστος κωδικός που χρειάζεται μια ιστοσελίδα. Όλη η κωδικοποίηση για αυτό το άρθρο βρίσκεται μεταξύ των ετικετών, .
Για να εκτελέσετε τον κώδικα που γράφτηκε (προστέθηκε), απλώς κάντε διπλό κλικ στο εικονίδιο του ονόματος αρχείου και το πρόγραμμα περιήγησης του υπολογιστή θα το ανοίξει.
Ορισμός αριθμού Fibonacci
Υπάρχει ένας μαθηματικός ορισμός για έναν αριθμό Fibonacci. Ορίζεται ως εξής:
Όπου Fn είναι ένας αριθμός Fibonacci που αντιστοιχεί σε μηδενικό δείκτη, n.
Οι δύο πρώτοι αριθμοί: 0 και 1, είναι προδηλωμένοι, με αυτή τη σειρά. Η τελευταία γραμμή αυτής της συνάρτησης δείχνει πώς οι υπόλοιποι αριθμοί προέρχονται από τους δύο πρώτους αριθμούς στη σειρά τους.
Αυτός ο ορισμός είναι επίσης ένας από τους τύπους για τον αριθμό Fibonacci.
Παραγωγή αριθμών Fibonacci σε χρόνο O(n).
Εάν το n είναι 1, τότε μόνο το 0 θα εμφανίζεται ως αριθμός Fibonacci. Εάν το n είναι 2, τότε το 0 και το 1 θα εμφανίζονται ως αριθμοί Fibonacci, με αυτή τη σειρά. Εάν το n είναι 3, τότε τα 0, 1 και 1 θα εμφανίζονται ως αριθμοί Fibonacci με αυτή τη σειρά. Εάν το n είναι 4, τότε τα 0, 1, 1 και 2 θα εμφανίζονται ως αριθμοί Fibonacci, με αυτή τη σειρά. Εάν το n είναι 5, τότε τα 0, 1, 1, 2 και 3 θα εμφανίζονται ως αριθμοί Fibonacci, με αυτή τη σειρά. Εάν το n είναι 6, τότε τα 0, 1, 1, 2, 3 και 5 θα εμφανίζονται ως αριθμοί Fibonacci, με αυτή τη σειρά – και ούτω καθεξής.
Η συνάρτηση ECMAscript για τη δημιουργία των πρώτων n ακεραίων Fibonacci (αριθμοί) είναι:
< τύπο σεναρίου = 'κείμενο/κείμενο' >λειτουργία Φιμπονάτσι ( ΕΝΑ ) {
n = ΕΝΑ. μήκος ;
αν ( n > 0 )
ΕΝΑ [ 0 ] = 0 ;
αν ( n > 1 )
ΕΝΑ [ 1 ] = 1 ;
Για ( Εγώ = δύο ; Εγώ < n ; Εγώ ++ ) { //n=0 και n=2 έχουν ληφθεί υπόψη
currNo = ΕΝΑ [ Εγώ - 1 ] + ΕΝΑ [ Εγώ - δύο ] ;
ΕΝΑ [ Εγώ ] = currNo ;
}
}
Η ετικέτα κλεισίματος σεναρίου δεν έχει εμφανιστεί. Η συνάρτηση λαμβάνει έναν πίνακα. Οι δύο πρώτοι αριθμοί Fibonacci εκχωρούνται στη θέση τους. Ο βρόχος for επαναλαμβάνεται από τον μηδενικό δείκτη, 2 έως ακριβώς κάτω από το n. Η πιο σημαντική δήλωση στο for-loop είναι:
currNo = A[i – 1] + A[i – 2];
Αυτό προσθέτει τους αμέσως προηγούμενους δύο αριθμούς στον πίνακα για να έχει τον τρέχοντα αριθμό. Μέχρι να τελειώσει η εκτέλεση της συνάρτησης fibonacci(), όλα τα στοιχεία του πίνακα είναι οι πρώτοι n αριθμοί Fibonacci. Ένας κατάλληλος κώδικας για να καλέσετε τη συνάρτηση fibonacci() και να εμφανίσετε τους αριθμούς Fibonacci είναι:
Ν = 12 ;αρ = νέος Πίνακας ( Ν ) ;
Φιμπονάτσι ( αρ ) ;
Για ( Εγώ = 0 ; Εγώ < Ν ; Εγώ ++ )
έγγραφο. γράφω ( αρ [ Εγώ ] + '' ) ;
έγγραφο. γράφω ( '
' ) ;
γραφή >
Αυτός ο κώδικας εμφανίζει την ετικέτα κλεισίματος σεναρίου. Ο κωδικός πληκτρολογείται κάτω από τον παραπάνω κωδικό. Η έξοδος που εμφανίζεται στην ιστοσελίδα είναι:
0 1 1 2 3 5 8 13 21 34 55 89
όπως αναμενόταν.
Παραγωγή ενός αριθμού Fibonacci σε χρόνο O(1).
Το O(1) είναι σταθερός χρόνος. Αναφέρεται σε μία κύρια λειτουργία. Ένας άλλος μαθηματικός τύπος για την παραγωγή ενός αριθμού Fibonacci είναι:
Σημειώστε ότι στη δεξιά πλευρά της εξίσωσης, δεν είναι η τετραγωνική ρίζα του 5 που αυξάνεται στην ισχύ n. είναι η έκφραση σε παρένθεση που ανυψώνεται στη δύναμη n. Υπάρχουν δύο τέτοιες εκφράσεις.
Αν το n είναι 0, το Fibn θα ήταν 0. Εάν το n είναι 1, το Fibn θα ήταν 1. Εάν το n είναι 2, το Fibn θα ήταν 1. Εάν το n είναι 3, το Fibn θα ήταν 2. Εάν το n είναι 4, το Fibn θα ήταν 3 – και ούτω καθεξής. Ο αναγνώστης μπορεί να επαληθεύσει αυτόν τον τύπο μαθηματικά αντικαθιστώντας διαφορετικές τιμές για n και αξιολογώντας. Το n είναι ένας μηδενικός δείκτης σε αυτόν τον τύπο. Το αποτέλεσμα είναι ο αντίστοιχος αριθμός Fibonacci.
Ο κώδικας ECMAScript (JavaScript) για αυτόν τον τύπο είναι:
< τύπο σεναρίου = 'κείμενο/κείμενο' >λειτουργία fibNo ( n ) {
FibN = ( Μαθηματικά . pow ( ( 1 + Μαθηματικά . sqrt ( 5 ) ) / δύο , n ) - Μαθηματικά . pow ( ( 1 - Μαθηματικά . sqrt ( 5 ) ) / δύο , n ) ) / Μαθηματικά . sqrt ( 5 ) ;
ΕΠΙΣΤΡΟΦΗ FibN ;
}
Η ετικέτα κλεισίματος σεναρίου δεν έχει εμφανιστεί. Σημειώστε πώς έχουν χρησιμοποιηθεί οι προκαθορισμένες συναρτήσεις ισχύος (pow) και τετραγωνικής ρίζας (sqrt). Στο ECMAScript (JavaScript), η ενότητα Math δεν χρειάζεται να εισαχθεί. Η συνάρτηση fibNo() υλοποιεί τον τύπο απευθείας. Μια κατάλληλη κλήση και εμφάνιση για τη συνάρτηση fibNo() στην ιστοσελίδα είναι:
Ν = έντεκα ;σωστά = fibNo ( Ν ) ;
έγγραφο. γράφω ( σωστά ) ;
γραφή >
Ο κώδικας εμφανίζει την ετικέτα κλεισίματος σεναρίου. Η έξοδος είναι:
89.000000000000003
Είναι δυνατό να αφαιρέσετε τα περιττά δεκαδικά ψηφία από την απάντηση. Ωστόσο, αυτή είναι μια συζήτηση για κάποια άλλη στιγμή.
Εάν απαιτούνται περισσότεροι από ένας αριθμοί Fibonacci, τότε ο κωδικός πρέπει να καλέσει τον τύπο μία φορά για κάθε αντίστοιχο n δείκτη με βάση το μηδέν.
συμπέρασμα
Οι αριθμοί Fibonacci είναι μια συγκεκριμένη ακολουθία θετικών ακεραίων, ξεκινώντας από το 0. Οι ακέραιοι αριθμοί είναι θετικοί ακέραιοι. Έτσι, ένας αριθμός Fibonacci είναι μια συγκεκριμένη ακολουθία ακέραιων αριθμών ή φυσικών αριθμών, ξεκινώντας από το 0. Σε αυτήν την ακολουθία, οι δύο πρώτοι αριθμοί είναι 0 και 1, με αυτή τη σειρά. Αυτοί οι δύο πρώτοι αριθμοί ορίζονται ακριβώς ως τέτοιοι. Οι υπόλοιποι αριθμοί αναπτύσσονται από εκεί προσθέτοντας τους αμέσως προηγούμενους δύο αριθμούς.
Μετά την παραγωγή των δύο πρώτων αριθμών Fibonacci, για να παραχθούν οι υπόλοιποι αριθμοί Fibonacci, για να καταλήξουμε σε ένα σύνολο n αριθμών, πρέπει να χρησιμοποιηθεί ένας βρόχος for με την πρόταση:
currNo = A[i – 1] + A[i – 2];
Αυτό προσθέτει τους άμεσους δύο τελευταίους αριθμούς Fibonacci για να έχουν τον τρέχοντα αριθμό Fibonacci.
Όταν δίνεται ένας μηδενικός δείκτης, για να έχετε τον αντίστοιχο αριθμό Fibonacci, χρησιμοποιήστε τον τύπο:
