Υπολογιστής Ακολουθίας Fibonacci

Τύπος

How this is calculated

Εισαγάγετε έναν μη αρνητικό ακέραιο n, που είναι τόσο ο δείκτης του όρου που θέλετε όσο και το πλήθος που ορίζει πόσο μακριά τρέχει η παρατιθέμενη ακολουθία. Ο υπολογιστής επαναλαμβάνει από τις δύο αρχικές τιμές F(0)=0 και F(1)=1, προσθέτοντας τους δύο προηγούμενους όρους για να πάρει κάθε επόμενο όρο, οπότε F(k)=F(k-1)+F(k-2). Αυτός ο βρόχος από κάτω προς τα πάνω αποφεύγει την εκθετική έκρηξη της αφελούς αναδρομής και τρέχει σε γραμμικό χρόνο.

Ο n-οστός αριθμός Fibonacci είναι απλώς το F(n), ο τελευταίος όρος που χτίστηκε. Το άθροισμα όλων των παρατιθέμενων όρων F(0) έως F(n) υπολογίζεται χρησιμοποιώντας την ταυτότητα Άθροισμα = F(n+2) - 1, που είναι ακριβής και αποφεύγει τη συσσώρευση σφάλματος στρογγυλοποίησης. Επειδή οι αριθμοί Fibonacci μεγαλώνουν περίπου σαν τη χρυσή τομή φ≈1.618 υψωμένη στη δύναμη n, οι τιμές γίνονται τεράστιες γρήγορα: το F(100) έχει ήδη 21 ψηφία. Για να παραμείνει ακριβής η μηχανή χρησιμοποιεί αριθμητική BigInt αυθαίρετης ακρίβειας, οπότε η εμφανιζόμενη n-οστή τιμή και το άθροισμα είναι ακριβή ακόμη κι όταν ο αριθμός στην κάρτα αποτελέσματος (ένα float 64 bit) χάνει ακρίβεια για πολύ μεγάλα n.

Ακραίες περιπτώσεις: n=0 επιστρέφει F(0)=0 με την ακολουθία ενός στοιχείου [0], και η ταυτότητα αθροίσματος εξακολουθεί να ισχύει αφού F(2)-1 = 0. Οι είσοδοι στρογγυλοποιούνται προς τα κάτω στον πλησιέστερο ακέραιο, και το εύρος περιορίζεται στο 1000 για να παραμείνει η σελίδα αποκριτική. Η AreaCurve σχεδιάζει τις αριθμητικές τιμές της ακολουθίας, αποδεικνύοντας οπτικά την εκθετική ανάπτυξη που χαρακτηρίζει τη σειρά.