Στην πραγματικότητα, οι δύο πρώτοι αριθμοί Fibonacci είναι προκαθορισμένοι. Ο πρώτος αριθμός Fibonacci είναι 0 και ο δεύτερος αριθμός Fibonacci είναι 1. Με μηδενική ευρετηρίαση και υποθέτοντας ότι οι αριθμοί Fibonacci είναι σε έναν πίνακα, τότε:
στο ευρετήριο 0 , ο αριθμός Fibonacci είναι 0 , ( προκαθορισμένος ) ;στο ευρετήριο 1 , ο αριθμός Fibonacci είναι 1 , ( προκαθορισμένος ) ;
στο ευρετήριο δύο , ο αριθμός Fibonacci είναι 1 = 1 + 0 , ( εξ ορισμού ) ;
στο ευρετήριο 3 , ο αριθμός Fibonacci είναι δύο = 1 + 1 , ( εξ ορισμού ) ;
στο ευρετήριο 4 , ο αριθμός Fibonacci είναι 3 = δύο + 1 , ( εξ ορισμού ) ;
στο ευρετήριο 5 , ο αριθμός Fibonacci είναι 5 = 3 + δύο , ( εξ ορισμού ) ;
στο ευρετήριο 6 , ο αριθμός Fibonacci είναι 8 = 5 + 3 , ( εξ ορισμού ) ;
στο ευρετήριο 7 , ο αριθμός Fibonacci είναι 13 = 8 + 5 , ( εξ ορισμού ) ;
στο ευρετήριο 8 , ο αριθμός Fibonacci είναι είκοσι ένα = 13 + 8 , ( εξ ορισμού ) ;
στο ευρετήριο 9 , ο αριθμός Fibonacci είναι 3. 4 = είκοσι ένα + 13 , ( εξ ορισμού ) ;
και ούτω καθεξής.
Στον προγραμματισμό, η μεταβλητή n και όχι i χρησιμοποιείται για τους μηδενικούς δείκτες για αυτούς τους αριθμούς Fibonacci. Και μαζί με αυτό, οι πρώτοι δώδεκα αριθμοί Fibonacci είναι:
| 0 | 1 | 1 | δύο | 3 | 5 | 8 | 13 | είκοσι ένα | 3. 4 | 55 | 89 |
| 0 | 1 | δύο | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | έντεκα |
Η δεύτερη σειρά του πίνακα δίνει τους μηδενικούς δείκτες, καθένας από τους οποίους θα έχει τη μεταβλητή n στον προγραμματισμό. Η πρώτη σειρά δίνει τους αντίστοιχους αριθμούς Fibonacci. Έτσι, οι αριθμοί Fibonacci δεν είναι οποιοιδήποτε αριθμοί. Ο βασικός ορισμός ξεκινά με 0, για τον πρώτο αριθμό Fibonacci και 1 για τον δεύτερο αριθμό Fibonacci. Οι υπόλοιποι αριθμοί παράγονται από εκεί.
Οι αριθμοί Fibonacci μπορούν να παραχθούν σε χρόνο O(n) και επίσης σε χρόνο O(1). Για χρόνο O(n), εάν το n είναι 12 για παράδειγμα, τότε θα παράγονται οι πρώτοι δώδεκα αριθμοί Fibonacci. Για χρόνο O(1), παράγεται μόνο ένας αριθμός Fibonacci. Για παράδειγμα, αν το n είναι 6, τότε θα παράγεται ο αριθμός Fibonacci 8.
Αυτό το άρθρο εξηγεί αυτούς τους δύο τρόπους παραγωγής αριθμών Fibonacci στην Java.
Τύπος για έναν αριθμό Fibonacci
Υπάρχει ένας μαθηματικός τύπος για έναν αριθμό Fibonacci. Αυτός ο τύπος μπορεί να γραφτεί σε τρεις γραμμές ή σε μία γραμμή. Σε τρεις γραμμές γράφεται ως εξής:
όπου F n είναι ο αριθμός Fibonacci στο μηδενικό n ου δείκτης. Έτσι ορίζεται ο αριθμός Fibonacci.
Παραγωγή αριθμών Fibonacci σε χρόνο O(n).
Εάν οι αριθμοί Fibonacci πρόκειται να παραχθούν σε O(3) φορές, θα παράγονται οι αριθμοί 0, 1, 1. αυτοί είναι οι τρεις πρώτοι αριθμοί Fibonacci. Το τελευταίο n με βάση το μηδέν ου Ο δείκτης εδώ είναι 2. Εάν οι αριθμοί Fibonacci πρόκειται να παραχθούν σε O(7) φορές, οι αριθμοί 0, 1, 1, 2, 3, 5, 8 θα παράγονται. αυτοί είναι οι πρώτοι επτά αριθμοί Fibonacci. Το τελευταίο n με βάση το μηδέν ου Ο δείκτης εδώ είναι 6. Εάν οι αριθμοί Fibonacci πρόκειται να παραχθούν σε O(n) φορές, θα παράγονται οι αριθμοί 0, 1, 1, 2, 3, 5, 8 – – –. αυτοί είναι οι πρώτοι n αριθμοί Fibonacci. Το τελευταίο n με βάση το μηδέν ου ο δείκτης εδώ είναι n-1.
Η μέθοδος Java σε μια κλάση για την παραγωγή των πρώτων n αριθμών Fibonacci είναι:
τάξη Φιμπονάτσι {κενός Φιμπονάτσι ( ενθ [ ] Π ) {
ενθ n = Π. μήκος ;
αν ( n > 0 )
Π [ 0 ] = 0 ;
αν ( n > 1 )
Π [ 1 ] = 1 ;
Για ( ενθ Εγώ = δύο ; Εγώ < n ; Εγώ ++ ) { //n=0 και n=2 έχουν ληφθεί υπόψη
ενθ currNo = Π [ Εγώ - 1 ] + Π [ Εγώ - δύο ] ;
Π [ Εγώ ] = currNo ;
}
}
}
Η τάξη, Fibonacci είναι ιδιωτική. ο fibonacci () μέθοδος παίρνει τον πίνακα P και επιστρέφει void. Η μέθοδος ξεκινά με τον προσδιορισμό του μήκους του πίνακα. Αυτό το μήκος του n είναι ο αριθμός των αριθμών Fibonacci που απαιτείται. Ο πρώτος και ο δεύτερος αριθμός Fibonacci καθορίζονται ρητά και τοποθετούνται στην πρώτη και στη δεύτερη θέση του πίνακα.
Οι υπόλοιποι αριθμοί Fibonacci που ξεκινούν από τον τρίτο (δείκτης, n = 2) προσδιορίζονται σε έναν βρόχο for και τοποθετούνται στις θέσεις τους στον πίνακα. Άρα, η συνάρτηση πρέπει να επιστρέψει void. Η κύρια δήλωση στον βρόχο for προσθέτει τους δύο προηγούμενους αριθμούς.
Η μεταβλητή δείκτη, i, έχει χρησιμοποιηθεί αντί για n, για λόγους σαφήνειας.
Μια κατάλληλη τάξη Java Main (με τη μέθοδο Java main) είναι:
δημόσιο τάξη Κύριος {δημόσιο στατικός κενός κύριος ( Σειρά args [ ] ) {
ενθ Μ = 12 ;
ενθ [ ] αρ = νέος ενθ [ Μ ] ;
Fibonacci obj = νέος Φιμπονάτσι ( ) ;
αντικ. Φιμπονάτσι ( αρ ) ;
Για ( ενθ Εγώ = 0 ; Εγώ < Μ ; Εγώ ++ )
Σύστημα . έξω . Τυπώνω ( αρ [ Εγώ ] + '' ) ;
Σύστημα . έξω . println ( ) ;
}
}
Αφού παραχθούν οι αριθμοί με τη μέθοδο fibonacci(), η κύρια μέθοδος Java τους διαβάζει.
Παραγωγή ενός αριθμού Fibonacci σε σταθερό χρόνο
Υπάρχει ένας μαθηματικός τύπος που μπορεί να χρησιμοποιηθεί για την παραγωγή ενός αριθμού Fibonacci, όταν δίνεται ο αντίστοιχος μηδενικός δείκτης, n. Ο τύπος είναι:
όπου n είναι ο μηδενικός δείκτης και Fib n είναι ο αντίστοιχος αριθμός Fibonacci. Σημειώστε ότι στη δεξιά πλευρά της εξίσωσης, δεν είναι η τετραγωνική ρίζα του 5 που αυξάνεται στην ισχύ n. είναι η έκφραση σε παρένθεση που ανυψώνεται στη δύναμη n. Υπάρχουν δύο τέτοιες εκφράσεις.
Αν το n είναι 0, Fib n θα ήταν 0. Εάν το n είναι 1, Fib n θα ήταν 1. Εάν το n είναι 2, Fib n θα ήταν 1. Εάν το n είναι 3, Fib n θα ήταν 2. Εάν το n είναι 4, Fib n θα ήταν 3 – και ούτω καθεξής. Ο αναγνώστης μπορεί να επαληθεύσει αυτόν τον τύπο μαθηματικά, αντικαθιστώντας διαφορετικές τιμές για n και αξιολογώντας.
Όταν κωδικοποιηθεί, αυτός ο τύπος θα παράγει μόνο έναν αριθμό Fibonacci για το n. Εάν απαιτούνται περισσότεροι από ένας αριθμοί Fibonacci, ο κωδικός για τον τύπο πρέπει να κληθεί μία φορά για κάθε έναν από τους διαφορετικούς αντίστοιχους δείκτες.
Στην Java, η μέθοδος για την παραγωγή μόνο ενός αριθμού Fibonacci είναι:
εισαγωγή java.lang.* ;τάξη Ψεματάκι {
διπλό fibNo ( ενθ n ) {
διπλό FibN = ( Μαθηματικά . pow ( ( 1 + Μαθηματικά . sqrt ( 5 ) ) / δύο , n ) – Μαθηματικά . pow ( ( 1 - Μαθηματικά . sqrt ( 5 ) ) / δύο , n ) ) / Μαθηματικά . sqrt ( 5 ) ;
ΕΠΙΣΤΡΟΦΗ FibN ;
}
}
Το πακέτο java.lang.* έπρεπε να εισαχθεί στην αρχή του προγράμματος. Αυτό συμβαίνει επειδή το πακέτο έχει την κλάση Math, η οποία έχει τις μεθόδους power (pow) και τετραγωνική ρίζα (sqrt). Η προσαρμοσμένη μέθοδος Java εδώ υλοποιεί απευθείας τον μαθηματικό τύπο.
Η χρονική πολυπλοκότητα για αυτή τη συνάρτηση είναι O(1), σταθερή εξημερότητα μιας κύριας λειτουργίας. Μια κατάλληλη κλάση Java Main, με μέθοδο Java main για την παραπάνω μέθοδο είναι:
δημόσιο τάξη Κύριος {δημόσιο στατικός κενός κύριος ( Σειρά args [ ] ) {
ενθ Ν = έντεκα ;
Fib obj = νέος Ψεματάκι ( ) ;
διπλό σωστά = αντικ. fibNo ( Ν ) ;
Σύστημα . έξω . println ( σωστά ) ;
}
}
Ο δείκτης n = 11 αποστέλλεται και ο αριθμός Fibonacci, 89 επιστρέφεται. Η έξοδος είναι:
89.000000000000003Τα περιττά δεκαδικά ψηφία μπορούν να αφαιρεθούν, αλλά αυτό είναι μια συζήτηση για κάποια άλλη στιγμή.
συμπέρασμα
Οι αριθμοί Fibonacci είναι μια συγκεκριμένη ακολουθία ακέραιων αριθμών. Για να λάβετε τον τρέχοντα αριθμό, προσθέστε τους αμέσως προηγούμενους δύο αντίστοιχους αριθμούς. Οι δύο πρώτοι αριθμοί Fibonacci, το 0 ακολουθούμενο από το 1, είναι προ-δηλωμένοι, για ολόκληρη την ακολουθία. Οι υπόλοιποι αριθμοί Fibonacci παράγονται από εκεί.
Για να παράγετε αριθμούς Fibonacci από τον δείκτη 2, σε αυτόν που αντιστοιχεί στον δείκτη n-1, χρησιμοποιήστε έναν βρόχο for με την κύρια πρόταση:
ενθ currNo = Π [ Εγώ - 1 ] + Π [ Εγώ - δύο ] ;όπου currNo είναι ο τρέχων αριθμός Fibonacci και P είναι ο πίνακας για την αποθήκευση των n αριθμών.
Για να δημιουργήσετε μόνο έναν αριθμό Fibonacci από οποιονδήποτε μηδενικό δείκτη n, χρησιμοποιήστε τον μαθηματικό τύπο:
