Αριθμοί Φιμπονάτσι

Ας θυμηθούμε πώς ονομάζει η γραμματική τις λέξεις {πρώτος, δεύτερος, τρίτος, ...}. Λέγονται τακτικά αριθμητικά. Δίνουν την τάξη (την θέση του σε μια σειρά) του ουσιαστικού.

Λοιπόν, σήμερα θα γράψουμε ένα απλό πρόγραμμα (σε ΓΛΩΣΣΑ) που θα υπολογίζει έναν αριθμό Φιμπονάτσι όταν του δίνουμε την τάξη του. Οι αριθμοί Φιμπονάτσι είναι μια σειρά από αριθμούς που δημιουργούνται ως εξής:

Ο πρώτος (τάξη=1) ορίζεται ίσος με 0, δηλαδή f(1)=0.
Ο δεύτερος (τάξη=2) ορίζεται ίσος με 1, δηλαδή f(2)=1.
Κάθε άλλος επόμενος (τάξη=k, κ>2) ισούται με το άθροισμα των δύο προηγουμένων του, f(k)=f(k-1)+f(k-2) .
Από τον τρόπο σχηματισμού των όρων της, η σειρά ονομάζεται αναδρομική.
Οι αρχικοί αριθμοί της σειράς είναι : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, κλπ.

Αν ψάξετε στο διαδίκτυο για Fibonacci, (το όνομα του Ιταλού μαθηματικού που τους περιέγραψε Λεονάρντο της Πίζας), θα εκπλαγείτε από τον πλούτο των ευρημάτων στην φύση, σχετικών με τους αριθμούς αυτούς.
Θα τους βρείτε στους στήμονες των λουλουδιών, στις έλικες των κουκουναριών, στις γεννήσεις των κουνελιών, (δείτε, από περιέργεια, αυτή την σελίδα εδώ).

Καθαρά μαθηματικές έννοιες επίσης υπάρχουν άφθονες, όπως ότι δύο διαδοχικοί αριθμοί Φιμπονάτσι έχουν λόγο που προσεγγίζει την χρυσή τομή (f(k-1)/f(k)=0.618 ή f(k+1)/f(k)=1.618), όσο μεγαλύτερη είναι η τάξη k.

Εδώ θέλουμε μόνο να γράψουμε το πρόγραμμα που θα διαβάζει το k (δεχόμαστε μόνο k>2) και θα γράφει το f(k).
Επειδή δεν γνωρίζουμε την τάξη k που θα μας δοθεί, και επειδή δεν χρειάζεται να αποθηκεύσουμε όλη την σειρά αλλά μπορούμε από δύο διαδοχικούς όρους να βρίσκουμε τον επόμενο, δεν πρέπει να χρησιμοποιήσουμε την δομή του Πίνακα για αποθήκευση (των ενδιάμεσων) αποτελεσμάτων. Αρκεί η χρήση τριών μεταβλητών για τους όρους. Θα βάλουμε στην μεταβλητή fa έναν όρο της σειράς, θα βάλουμε στην μεταβλητή fb τον επόμενο όρο, και στην fc θα βάλουμε το άθροισμα των δύο προηγουμένων.

Αρχικοποιούμε fa=0, fb=1.
Μας δίνουν την τάξη k του όρου που θα βρούμε. Ελέγχουμε να είναι k>2.

Ξεκινάμε μια επαναληπτική διεργασία.
Βρίσκουμε τον τρίτο όρο f(3), (ή όρο τρίτης τάξης) : fc=fa+fb=0+1=1, άρα f(3)=1.
Βάζουμε τώρα στην μεταβλητή fa αυτό που περιέχει η μεταβλητή fb, και μετά
βάζουμε στην μεταβλητή fb αυτό που περιέχει η μεταβλητή fc, (περιέχουν δηλαδή το fa=1, και το fb=1),
και είμαστε έτοιμοι να υπολογίσουμε τον τέταρτο όρο f(4), (ή όρο τέταρτης τάξης) : fc=fa+fb=1+1=2, άρα f(4)=2.

Συνεχίζοντας με παρόμοιο τρόπο βάζουμε στην fa το 1 (της fb), στην fb το 2 (της fc) για να υπολογίσουμε τον πέμπτο όρο f(5), (ή όρο πέμπτης τάξης) : fc=fa+fb=1+2=3, άρα f(5)=3.

Σταματούμε όταν έχουμε υπολογίσει τον όρο f(k), της k τάξης που μας δόθηκε αρχικά.

ΠΡΟΓΡΑΜΜΑ arfi

ΜΕΤΑΒΛΗΤΕΣ

__ΑΚΕΡΑΙΕΣ: fa, fb, fc, i, k

ΑΡΧΗ

fa <- 0

fb <- 1

ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ

__ΓΡΑΨΕ 'Δώσε ακέραιο μεγαλύτερο του 2'

__ΔΙΑΒΑΣΕ k

ΜΕΧΡΙΣ_ΟΤΟΥ k > 2

ΓΙΑ i ΑΠΟ 3 ΜΕΧΡΙ k

__fc <- fa + fb

__fa <- fb

__fb <- fc

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΓΡΑΨΕ 'Αριθμός Φιμπονάτσι τάξης ', k, ' είναι ο ', fc

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Για να εξασκηθείτε στο γράψιμο κώδικα (δηλαδή εντολών σε ΓΛΩΣΣΑ), μπορείτε να κατεβάσετε στον υπολογιστή σας δωρεάν τον Διερμηνευτή του Άλκη Γεωργόπουλου, ένα πολύ καλοφτιαγμένο περιβάλλον εκτέλεσης προγραμμάτων σε ΓΛΩΣΣΑ, που συνοδεύεται από συλλογή παραδειγμάτων.
Μπορείτε να κατεβάσετε Διερμηνευτή και παραδείγματα από εδώ .