Λύση γρίφου 14

Ο γρίφος δημοσιεύτηκε εδώ : http://ideas-by-alkinoos.blogspot.gr/2013/02/14.html

Ακολουθεί η λύση:

Γρίφος 14

Ονομάζω τα κομμάτια αρχίζοντας με το επάνω και προχωρώ δεξιόστροφα, βάζοντας 
πεζό γράμμα για μικρό κρίκο και 
κεφαλαίο γράμμα για μεγάλο κρίκο : 
αΑ ΒΒ Γγ δδ εΕ ΖΖ Ηη θΘ ΙΙ Κκ λλ μμ.

Ανοίγω όλους τους κρίκους στα κομμάτια δδ και λλ (είναι περίπου στην μέση δεξιά κι αριστερά) 
και παίρνω κρίκους δ Δ δ Δ δ, λ Λ λ Λ λ. 

Τα 10 υπόλοιπα κομμάτια στη σειρά τους είναι
αΑ ΒΒ Γγ    εΕ ΖΖ Ηη θΘ ΙΙ Κκ    μμ
και τα ενώνω με τους 10 κρίκους που άνοιξα

αΑ δ ΒΒ δ Γγ Δ εΕ δ ΖΖ λ Ηη Δ θΘ λ ΙΙ λ Κκ Λ μμ Λ, 

χρεώνοντας 4 x 20 + 6 x 15 = 170 λεπτά!

Γρίφος 14

Άλλο ένα ωραίο πρόβλημα του Σαμ Λόιντ. Θα χαρώ πολύ να το λύσετε.

Η κυρία της εικόνας πήγε δώδεκα κομμάτια μιάς αλυσίδας (αυτά που βλέπετε στο περιθώριο της εικόνας) σε έναν χρυσοχόο και τον ρώτησε αν μπορεί να γίνει πάλι ολόκληρη με 100 κρίκους και ποιό θα είναι το κόστος της εργασίας.
Ο χρυσοχόος εξέτασε τα κομμάτια και είπε πως μπορεί να γίνει.

Το κόστος για να κόψει και να ξανακλείσει έναν μικρό κρίκο είναι 15 λεπτά.
Το κόστος για να κόψει και να ξανακλείσει έναν μεγάλο κρίκο είναι 20 λεπτά.

Το ερώτημα είναι "Πόσα χρήματα το λιγότερο πρέπει να ζητήσει ο χρυσοχόος, τηρώντας το κοστολόγιό του, ώστε να γίνει η εργασία συνένωσης των κομματιών της αλυσίδας;"

(Με κλικ στην εικόνα την βλέπετε μεγαλύτερη).
Δίνετε την λύση στα σχόλια.
Θα δημοσιεύσω την λύση σε μια εβδομάδα._

Απλό πρόγραμμα μετατροπής

Συχνά θέλουμε να μετατρέψουμε μιά ποσότητα, εκφρασμένη σε μιά μονάδα μέτρησης, σε μια σειρά ποσών, εκφρασμένων σε πολλές σχετιζόμενες μονάδες μέτρησης.
Για παράδειγμα, μας δίνουνε μια ποσότητα σε ευρώ και μας ζητούν βρούμε από πόσα πεντακοσάρικα, διακοσάρικα, εκατοστάρικα, πενηντάρικα, εικοσάρικα, δεκάρικα, πεντάευρα, δίευρα και ευρώ απαρτίζεται.

Στο πρόγραμμα που εμφανίζεται παρακάτω, μας δίνουν μια ποσότητα σε δευτερόλεπτα χρόνου και μας ζητούν να βρούμε από πόσες ημέρες, ώρες, λεπτά, δευτερόλεπτα απαρτίζεται. Στο πρόγραμμα φαίνονται δύο μέθοδοι, που βρίσκουν τις επί μέρους ποσότητες με αντίστροφη πορεία.

ΠΡΟΓΡΑΜΜΑ μετατροπή

!Μετατρέπει δεδομένο πλήθος Α δευτερολέπτων ...
! ...σε ημέρες, ώρες, λεπτά, δευτερόλεπτα

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: Α, ημε, ωρε, λεπ, δευ, ημε1, ωρε1, λεπ1

ΑΡΧΗ

ΓΡΑΨΕ 'Δώσε πλήθος δευτερολέπτων ='

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

ΔΙΑΒΑΣΕ Α

ΜΕΧΡΙΣ_ΟΤΟΥ Α > 0

!
!Μέθοδος πρώτη (το Α μένει αναλλοίωτο)
!Το Α γίνεται λεπτά και βρίσκουμε πόσα δευτερόλεπτα απομένουν

λεπ1 <- Α DIV 60

δευ <- Α - λεπ1*60

!Το λεπ1 γίνεται ώρες και βρίσκουμε πόσα λεπτά απομένουν

ωρε1 <- λεπ1 DIV 60

λεπ <- λεπ1 - ωρε1*60

!Το ωρε1 γίνεται ημέρες και βρίσκουμε πόσες ώρες απομένουν

ημε1 <- ωρε1 DIV 24

ωρε <- ωρε1 - ημε1*24

!Αν θέλουμε, συνεχίζουμε παρόμοια σε μήνες, χρόνια κλπ

ημε <- ημε1

ΓΡΑΨΕ ημε, ' ημέρες ', ωρε, ' ώρες ', λεπ, ' λεπτά ', δευ, ' δευτερόλεπτα'

!
!Μέθοδος δεύτερη (το Α μεταβάλλεται)
!24 * 60 * 60 = 86400 δευτερόλεπτα στην ημέρα

ημε <- Α DIV 86400

Α <- Α - ημε*86400

!60 * 60 = 3600 δευτερόλεπτα στην ώρα

ωρε <- Α DIV 3600

Α <- Α - ωρε*3600

!60 δευτερόλεπτα στο λεπτό

λεπ <- Α DIV 60

Α <- Α - λεπ*60

!και απομένουν...

δευ <- Α

ΓΡΑΨΕ ημε, ' ημέρες ', ωρε, ' ώρες ', λεπ, ' λεπτά ', δευ, ' δευτερόλεπτα'

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

Θέμα 3ον (και ίδιο αλλά και λίγο αλλαγμένο)

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

---

(α) Θέμα 3ον, όπως δόθηκε

Σε μια διαδρομή τρένου υπάρχουν 20 σταθμοί (σε αυτούς περιλαμβάνονται η αφετηρία και ο τερματικός σταθμός). Το τρένο σταματά σε όλους τους σταθμούς. Σε κάθε σταθμό επιβιβάζονται και αποβιβάζονται επιβάτες. Οι πρώτοι επιβάτες επιβιβάζονται στην αφετηρία και στον τερματικό σταθμό αποβιβάζονται όλοι οι επιβάτες.
Να κατασκευάσετε αλγόριθμο, ο οποίος να διαχειρίζεται την κίνηση των επιβατών. Συγκεκριμένα :
Α. Να ζητάει από τον χρήστη τον αριθμό των ατόμων που επιβιβάστηκαν σε κάθε σταθμό, εκτός από τον τερματικό, και να τον εισάγει σε πίνακα ΕΠΙΒ[19]. (Μονάδες 2)
Β. Να εισάγει σε πίνακα ΑΠΟΒ[19] τον αριθμό των ατόμων που αποβιβάστηκαν σε κάθε σταθμό, εκτός από τον τερματικό, ως εξής : Για την αφετηρία να εισάγει την τιμή μηδέν (0) και για τους υπόλοιπους σταθμούς να ζητάει από τον χρήστη τον αριθμό των ατόμων που αποβιβάστηκαν. (Μονάδες 4)
Γ. Να δημιουργεί πίνακα ΑΕ[19], στον οποίο να καταχωρίζει τον αριθμό των επιβατών που βρίσκονται στο τρένο, μετά από κάθε αναχώρησή του. (Μονάδες 7)
Δ. Να βρίσκει και να εμφανίζει τον σταθμό από τον οποίο το τρένο αναχωρεί με τον μεγαλύτερο αριθμό επιβατών. (Να θεωρήσετε ότι από κάθε σταθμό το τρένο αναχωρεί με διαφορετικό αριθμό επιβατών). (Μονάδες 7)

Ενδεικτική λύση με διαχωρισμό σε ερωτήματα όπως δόθηκαν στην εκφώνηση :

Αλγόριθμος Θέμα3

// ΕΠΙΒ[19], ΑΠΟΒ[19] //

! Α επιβιβαζόμενοι

Για σταθμός από 1 μέχρι 19

__Διάβασε ΕΠΙΒ[σταθμός]

Τέλος_επανάληψης

! Β αποβιβαζόμενοι

ΑΠΟΒ[1] <– 0

Για σταθμός από 2 μέχρι 19

__Διάβασε ΑΠΟΒ[σταθμός]

Τέλος_επανάληψης

! Γ παραμένοντες στο τρένο

Πλήθος <– 0

Για σταθμός από 1 μέχρι 19

__Πλήθος <– Πλήθος + ΕΠΙΒ[σταθμός] – ΑΠΟΒ[σταθμός]

__ΑΕ[σταθμός] <– Πλήθος

Τέλος_επανάληψης

! Δ σταθμός μεγίστου πλήθους

ΣταθμόςΜΠλήθους <– 1

ΜέγιστοΠλήθος <– ΑΕ[1]

Για σταθμός από 2 μέχρι 19

__Αν ΑΕ[σταθμός] > ΜέγιστοΠλήθος τότε

____ΣταθμόςΜΠλήθους <– σταθμός

____ΜέγιστοΠλήθος <– ΑΕ[σταθμός]

__Τέλος_αν

Τέλος_επανάληψης

Εμφάνισε ‘Σταθμός ‘,ΣταθμόςΜΠλήθους,’ με πλήθος ‘,ΜέγιστοΠλήθος

// ΣταθμόςΜΠλήθους //

Τέλος Θέμα3

Άλλη ενδεικτική λύση χωρίς διαχωρισμό σε ερωτήματα, δίνει την σωστή απάντηση αλλά δυσκολεύει τους διορθωτές :

Αλγόριθμος Θέμα3_σύντομος

// ΕΠΙΒ[19], ΑΠΟΒ[19] //

Για σταθμός από 1 μέχρι 19

__Αν σταθμός = 1 τότε

____Διάβασε ΕΠΙΒ[1]

____ΑΠΟΒ[1] <– 0

____ΑΕ[1] <– ΕΠΙΒ[1]

____ΣταθμόςΜΠλήθους <– 1

____ΜέγιστοΠλήθος <– ΑΕ[1]

__Αλλιώς

____Διάβασε ΕΠΙΒ[σταθμός], ΑΠΟΒ[σταθμός]

____ΑΕ[σταθμός] <– ΑΕ[σταθμός–1]+ΕΠΙΒ[σταθμός]-ΑΠΟΒ[σταθμός]

____Αν ΑΕ[σταθμός] > ΜέγιστοΠλήθος τότε

______ΣταθμόςΜΠλήθους <– σταθμός

______ΜέγιστοΠλήθος <– ΑΕ[σταθμός]

____Τέλος_αν

__Τέλος_αν

Τέλος_επανάληψης

Εμφάνισε ‘Σταθμός ‘,ΣταθμόςΜΠλήθους,’ με πλήθος ‘,ΜέγιστοΠλήθος

// ΣταθμόςΜΠλήθους //

Τέλος Θέμα3_σύντομος

---

(β) Θέμα 3ον, λίγο αλλαγμένο

Ένα τρένο επιτρέπεται να μεταφέρει ένα μέγιστο όριο επιβατών. Το Όριο_επιβατών δίδεται όταν φεύγει το τρένο από το Αμαξοστάσιο.
Στην πρώτη στάση, στην Αφετηρία, ανεβαίνουν επιβάτες. Το τρένο μετά την Αφετηρία κάνει 18 ενδιάμεσες στάσεις και φτάνει στο Τέρμα. Στις ενδιάμεσες στάσεις πρώτα κατεβαίνουν οι επιβαίνοντες και μετά ανεβαίνουν νέοι επιβάτες. Στο Τέρμα κατεβαίνουν όλοι οι επιβάτες.
Ζητείται αλγόριθμος που να διαχειρίζεται την κίνηση των επιβατών. Θα διαβάζει πόσοι κατέβηκαν (ΑΠΟΒ[19]) και πόσοι ανέβηκαν (ΕΠΙΒ[19]), αλλά θα ελέγχει τις τιμές να είναι πάντοτε επιτρεπτές. Θα παρακολουθεί το πλήθος επιβατών (ΑΕ[19]).
Να εμφανιστεί ο αριθμός της τελευταίας στάσης που αναχώρησε το τρένο με τους περισσότερους επιβάτες, το μέγιστο αυτό πλήθος επιβατών, και το πλήθος επιβατών που κατέβηκαν στο Τέρμα.

Αλγόριθμος Θέμα3_αλλαγμένος

// Όριο_Επιβατών, ΕΠΙΒ[19], ΑΠΟΒ[19] //

! Καθορίζεται το όριο επιβατών στο Αμαξοστάσιο

Αρχή_επανάληψης

__Διάβασε Όριο_επιβατών

Μέχρις_ότου Όριο_επιβατών > 0

! Στην πρώτη στάση μπορεί να γεμίσει από επιβάτες

Αρχή_επανάληψης

__Διάβασε ΕΠΙΒ[1]

Μέχρις_ότου ΕΠΙΒ[1]>=0 και ΕΠΙΒ[1]<=Όριο_επιβατών

ΑΠΟΒ[1] <– 0

ΑΕ[1] <– ΕΠΙΒ[1]

ΣτάσηΜΠλήθους <– 1

ΜέγιστοΠλήθος <– ΑΕ[1]

Για στάση από 2 μέχρι 19

! Σε επόμενη στάση αποβιβάζονται το πολύ όλοι όσοι επιβαίνουν

__Αρχή_επανάληψης

____Διάβασε ΑΠΟΒ[στάση]

__Μέχρις_ότου ΑΠΟΒ[στάση]>=0 και ΑΠΟΒ[στάση]<=ΑΕ[στάση–1]

! Βρίσκουμε πόσοι παρέμειναν μέσα στο όχημα

__ΑΕ[στάση] <– ΑΕ[στάση–1]–ΑΠΟΒ[στάση]

! Μετά επιβιβάζονται σε όσες ελεύθερες θέσεις υπάρχουν, μέχρι το όριο επιβατών __Αρχή_επανάληψης

____Διάβασε ΕΠΙΒ[στάση]

__Μέχρις_ότου ΕΠΙΒ[στάση]>=0 και ΕΠΙΒ[στάση]<=(Όριο_επιβατών–ΑΕ[στάση])

! Βρίσκουμε πόσοι έγιναν οι επιβάτες, πριν ξεκινήσει το όχημα

____ΑΕ[στάση] <– ΑΕ[στάση]+ΕΠΙΒ[στάση]

____Αν ΑΕ[στάση] > ΜέγιστοΠλήθος τότε

______ΣτάσηΜΠλήθους <– στάση

______ΜέγιστοΠλήθος <– ΑΕ[στάση]

____Τέλος_αν

Τέλος_επανάληψης

Εμφάνισε ‘Στάση ‘,ΣτάσηΜΠλήθους,’ με μέγιστο πλήθος ‘,ΜέγιστοΠλήθος

Αν ΑΕ[19]>0 τότε

__Εμφάνισε ‘Στο τέρμα κατεβαίνουν ‘,ΑΕ[19],’ επιβάτες

αλλιώς

__Εμφάνισε ‘Δεν υπάρχουν επιβάτες που κατεβαίνουν στο Τέρμα’

Τέλος_αν

// ΣτάσηΜΠλήθους, ΜέγιστοΠλήθος, ΑΕ[19] //

Τέλος Θέμα3_αλλαγμένος

Πράξεις σε μέρος ενός Πίνακα

Όταν χρησιμοποιούμε έναν Πίνακα, μπορεί να υποχρεωθούμε να κάνουμε πράξεις με ένα υποσύνολο των στοιχείων του.

Γενικά, ο Πίνακας έχει ένα όνομα, έστω Πιν.
Ορίζουμε έναν δείκτη γρα, που θα μας δείχνει σε ποιά γραμμή του πίνακα είμαστε, και μια μέγιστη τιμή αυτού του δείκτη : γραμαξ.
Ορίζουμε έναν δείκτη στη, που θα μας δείχνει σε ποιά στήλη του πίνακα είμαστε, και μια μέγιστη τιμή αυτού του δείκτη : στημαξ.
Ο πίνακας έχει πλήθος στοιχείων (γραμαξ x στημαξ), και αν είναι τετραγωνικός θα έχουμε γραμαξ=στημαξ.

Το πρόβλημα που δίνουμε σήμερα είναι το εξής : Σε έναν τετραγωνικό πίνακα 20x20 βάζουμε κατά γραμμές τους αριθμούς 1, 2, 3, ..., 400. Ο πίνακας έχει μια διαγώνιο από Πιν[1,1] μέχρι Πιν[20,20]. Θέλουμε να φτιάξουμε ένα πρόγραμμα σε ΓΛΩΣΣΑ που θα τυπώνει τον μέσο αριθμητικό των στοιχείων του πίνακα που βρίσκονται κάτω από την διαγώνιο αυτή, τον μέσο αριθμητικό των στοιχείων που ορίζουν την διαγώνιο, και τον μέσο αριθμητικό των στοιχείων του πίνακα που είναι πάνω από την διαγώνιο.

Για να βάλουμε τις αρχικές τιμές, χρησιμοποιούμε τιμές γραμμο-δείκτη γρα από 1 μέχρι γραμαξ, και τιμές στηλο-δείκτη στη από 1 μέχρι στημαξ. Όταν όμως προχωρήσουμε σε πράξεις σε μέρη του πίνακα, προσέχουμε πολύ στον καθορισμό των ορίων μεταβολής του καθενός δείκτη. Παρακάτω γράφουμε το πρόγραμμα και την απάντηση.
Φτιάξτε το δικό σας πρόγραμμα ως άσκηση, βρείτε τους τρεις μέσους όρους, και μετά συγκρίνετε τα προγράμματα και τις απαντήσεις.

ΠΡΟΓΡΑΜΜΑ μο3

! Βάζουμε ακέραιους αριθμούς (1, 2, 3, ...) σε έναν τετραγωνικό πίνακα κατά γραμμές
! και βρίσκουμε τους μέσους όρους στο αριστερό κάτω τριγωνικό μέρος, στην διαγώνιο,
! και στο δεξιό πάνω τριγωνικό μέρος του πίνακα

ΜΕΤΑΒΛΗΤΕΣ

__ΑΚΕΡΑΙΕΣ: Πιν[20, 20], γρα, γραμαξ, στη, στημαξ, πλήθος, άθροισμα

__ΠΡΑΓΜΑΤΙΚΕΣ: ΜΟαριστερά, ΜΟδιαγώνια, ΜΟδεξιά

ΑΡΧΗ

γραμαξ <- 20

στημαξ <- 20

! τοποθέτηση αρχικών τιμών στον Πίνακα κατά γραμμές

πλήθος <- 0

ΓΙΑ γρα ΑΠΟ 1 ΜΕΧΡΙ γραμαξ

__ΓΙΑ στη ΑΠΟ 1 ΜΕΧΡΙ στημαξ

____πλήθος <- πλήθος + 1

____Πιν[γρα, στη] <- πλήθος

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

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

! εύρεση του μέσου όρου των αριστερών

πλήθος <- 0

άθροισμα <- 0

ΓΙΑ γρα ΑΠΟ 2 ΜΕΧΡΙ γραμαξ

__ΓΙΑ στη ΑΠΟ 1 ΜΕΧΡΙ γρα - 1

____πλήθος <- πλήθος + 1

____άθροισμα <- άθροισμα + Πιν[γρα, στη]

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

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

ΜΟαριστερά <- άθροισμα/πλήθος

! εύρεση του μέσου όρου των διαγωνίων

πλήθος <- 0

άθροισμα <- 0

ΓΙΑ γρα ΑΠΟ 1 ΜΕΧΡΙ γραμαξ

__πλήθος <- πλήθος + 1

__άθροισμα <- άθροισμα + Πιν[γρα, γρα]

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

ΜΟδιαγώνια <- άθροισμα/πλήθος

! εύρεση του μέσου όρου των δεξιών

πλήθος <- 0

άθροισμα <- 0

ΓΙΑ γρα ΑΠΟ 1 ΜΕΧΡΙ γραμαξ - 1

__ΓΙΑ στη ΑΠΟ γρα + 1 ΜΕΧΡΙ στημαξ

____πλήθος <- πλήθος + 1

____άθροισμα <- άθροισμα + Πιν[γρα, στη]

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

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

ΜΟδεξιά <- άθροισμα/πλήθος

! εκτύπωση των τριών μέσων όρων

ΓΡΑΨΕ 'Μέσοι όροι : Αριστερών=', ΜΟαριστερά, ', Διαγωνίων=', ΜΟδιαγώνια, ' και Δεξιών=', ΜΟδεξιά

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

Όταν εκτελεστεί το πρόγραμμα αυτό, δίνει απάντηση :

Μέσοι όροι : Αριστερών=267.00, Διαγωνίων=200.50 και Δεξιών=134.00

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

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

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

Ο πρώτος (τάξη=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

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

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

Συμπληρώματα σε άλλη βάση

Από μια ερώτηση που μου έθεσαν, θέλω να διευκρινίσω τα παρακάτω:

Ερώτηση 1:
Ενας υπολογιστής χρησιμοποιεί λέξη των 6 bits.
Για τους αρνητικούς χρησιμοποιεί [Συμπλήρωμα του 2].
Ασχολούμαστε με τον -23₁₀.
Από το +23₁₀ = 0 10111₂ παίρνουμε ότι
[Στ1, Συμπλήρωμα του 1] είναι το 1 01000₂ και
[Στ2, Συμπλήρωμα του 2] είναι το 1 01001₂ = -23₁₀.
Πώς γράφεται το συμπλήρωμά του στο οκταδικό σύστημα;

Απάντηση 1:
Ο υπολογιστής κάνει πράξεις στο δυαδικό και μόνο εκεί χρειαζόμαστε τα Στ1 και Στ2.
Για να παραστήσουμε αρνητικούς αριθμούς στο οκταδικό
θα χρησιμοποιούσαμε [Στ7, Συμπλήρωμα του 7] και [Στ8, Συμπλήρωμα του 8].
Ο αριθμός +23₁₀ γράφεται 027₈ (πρόσημο θετικό, 2*8 + 7 = 23₁₀ η τιμή).
Το Στ7 του 0 2 7₈ είναι 1 5 0₈ (το 0 έγινε 1, το 2 έγινε 7-2=5, το 7 έγινε 7-7=0).
Άρα το Στ8 είναι 150₈ + 1 = 151₈ (αυτός είναι ο -23₁₀ στο οκταδικό με σύστημα Στ8).
Επαλήθευση : 027₈ + 151₈ δίνει 000₈ = +0₈ (το κρατούμενο από την θέση του προσήμου χάνεται).

Ερώτηση 2:
Λέτε ότι -23₁₀ = 151₈.
Έδωσα στο calculator των windows τον δεκαδικό -23,
ζήτησα να το δείξει οκταδικά με μήκος word 6 και έδωσε 177751. Ποιό είναι το σωστό;

Απάντηση 2:
Ο υπολογιστής, για τον οποίο ορίσαμε λέξη 6 bits, κάνει πράξεις στο δυαδικό.
Στο οκταδικό μόνο εμφανίζει, άρα γίνονται κάποιοι συμβιβασμοί.

Αν η λέξη έχει μόνο 6 δυαδικά ψηφία, ο μέγιστος θετικός θα είναι 0 11 111₂ = 0 37₈ = +31₁₀,
(συμβιβαστικά, το οκταδικό 3 φτιάχτηκε από τα δύο ψηφία 11
με την υπόθεση ότι μπροστά τους είχαν κι άλλο ψηφίο=0, 011₂ = 3₈).
Αυτό σημαίνει ότι η λέξη δεν χωράει τους αμέσως μεγαλύτερους οκταδικούς 0 40₈, 0 41₈, κλπ..

Ο -23₁₀ στο δυαδικό είναι 1 01001₂. Αυτά είναι 6 bits.
Όταν η αριθμομηχανή δείχνει 177751₈, χρησιμοποιεί 16 bits (1 πρόσημο + 5 οκταδικά * 3 bits/οκταδικό).

Για τα 6 bits λοιπόν, το -23₁₀ = 101 001₂ = 51₈
(όπου υπονοείται ότι το πρώτο bit από τα τρία bits του 5 είναι το πρόσημο).
(Η αριθμομηχανή με βαθμιαία μεγαλύτερη λέξη θα τον δείχνει 151, 351, 751, 1751, 3751, 7751, 17751 κλπ).

Σε δεκαεξαδική μορφή -23₁₀ = 10 1001₂ = 29₁₆.
(Η αριθμομηχανή με βαθμιαία μεγαλύτερη λέξη θα τον δείχνει 69, E9, 1E9, 3E9, 7E9, FE9, 1FE9 κλπ).

Εδώ μπορείτε να αρχίσετε να φτιάχνετε μια ιδιαίτερη κατηγορία προβλημάτων:
"Έδωσα στον υπολογιστή τον δεκαδικό -23 και όταν τον ζήτησα οκταδικό μου τον έδειξε 177751. Με πόσα bits κάνει πράξεις ο υπολογιστής;"
Βρήκαμε παραπάνω την απάντηση : 16.

Το πρόβλημα με τον ταχυδρόμο

Όταν θέλω να εξηγήσω σε κάποιον με τι ασχολείται η Πληροφορική, συνήθως χρησιμοποιώ το σχετικά γνωστό πρόβλημα του ταχυδρόμου.

Πληροφορική : από ορισμένα δεδομένα, με κατάλληλη επεξεργασία, παίρνουμε χρήσιμα αποτελέσματα που τα ονομάζουμε πληροφορίες . Τα αποτελέσματα που αναζητούμε καθορίζουν ποια από τα στοιχεία που γνωρίζουμε μπορούν να χρησιμοποιηθούν ως δεδομένα.

Η Πληροφορική είναι η επιστήμη που μας δίνει τις μεθόδους και τα εργαλεία για να συλλέγουμε /αποθηκεύουμε /αποστέλλουμε δεδομένα.

Η Πληροφορική καθορίζει τις μεθόδους και τα εργαλεία επεξεργασίας των δεδομένων. Οι μέθοδοι, που συνήθως είναι επαναληπτικές, μπορεί να δημιουργούν ενδιάμεσα δεδομένα.

Η Πληροφορική καθορίζει τις μεθόδους και τα εργαλεία αποθήκευσης /παρουσίασης /αποστολής των αποτελεσμάτων. Η μελέτη των αποτελεσμάτων μπορεί να εμπλουτίσει την Πληροφορική με νέες μεθόδους και νέα εργαλεία, χάρη στην επινοητικότητα και την ευστροφία των μελετητών.

Αν δεν υπάρχουν γνωστές μέθοδοι για να λύσουμε ένα πρόβλημα, φροντίζουμε να επινοήσουμε μια νέα διαδικασία που να το λύνει. Η διαδικασία μπορεί να είναι ανέφικτο να χρησιμοποιηθεί σε άλλα είδη προβλημάτων. Ο στόχος μας είναι πάντοτε η λύση των προβλημάτων, όχι μόνο η εφαρμογή γνωστών διαδικασιών σε κάποια δεδομένα.

Και τώρα,

Πρόβλημα 01 : [Το πρόβλημα του ταχυδρόμου] :

Ένας ταχυδρόμος μοιράζει γράμματα σε μια γειτονιά κυκλοφορώντας με το ποδήλατό του. Ξαφνικά βλέπει ότι έξω από ένα μέχρι πρόσφατα ξενοίκιαστο σπίτι υπάρχει ένα φορτηγό και εργάτες μεταφέρουν έπιπλα από το φορτηγό στο σπίτι ακολουθώντας τις οδηγίες μιάς κυρίας.

Ο ταχυδρόμος θέλει να πιάσει γνωριμία με όλους τους κατοίκους και πλησιάζοντας ρωτάει την κυρία :

[Είσαστε η νέα νοικάρισα του σπιτιού; Ωραία γειτονιά!]

[Μάλιστα] απαντά η κυρία [και την διαλέξαμε επειδή μας αρέσει].

Η κυρία δεν φαίνεται ότι έχει όρεξη για κουβέντα.

Ο ταχυδρόμος είναι περίεργος και δεν τα παρατάει εύκολα. Ξαφνικά βλέπει για μια στιγμή στον διάδρομο μέσα στο σπίτι ένα κοριτσάκι που περνάει τρέχοντας από το ένα δωμάτιο σε ένα άλλο. Λέει λοιπόν

[Βλέπω έχετε μια κορούλα!]

[Δεν έχω μία. Έχω τρεις κόρες] απαντάει η κυρία.

[Να σας ζήσουν! Πόσων χρόνων είναι;]. Προφανώς ο ταχυδρόμος είναι περίεργος και η κυρία θέλει να τον ξεφορτωθεί με τρόπο, οπότε του λέει

[Οι ηλικίες τους, που είναι ακέραιοι αριθμοί, έχουν γινόμενο τριανταέξι. Το άθροισμα των ηλικιών είναι ίσο με τον αριθμό του απέναντι σπιτιού].

Ο ταχυδρόμος, που του αρέσει πολύ να λύνει γρίφους, βλέπει τον αριθμό του απέναντι σπιτιού και αρχίζει να σκέφτεται έντονα και μεθοδικά. Ξαφνικά φαίνεται ότι δυσκολεύεται και λέει στην κυρία.

[Έχω κολλήσει. Μήπως μπορείτε να με βοηθήσετε λιγάκι;]

[Ευχαρίστως!] του λέει η κυρία. [Η μεγαλύτερη κόρη μου είναι ξανθιά!]

[Α! τότε εντάξει!] λέει χαρούμενος ο ταχυδρόμος, [οι ηλικίες είναι τάδε, τάδε και τάδε!].

Μπορείτε τώρα, με βάση τα στοιχεία του προβλήματος να προσδιορίσετε τις τρεις ηλικίες;

Σας βεβαιώνω ότι το πρόβλημα λύνεται, και η επίλυσή του μου δίνει την ευκαιρία να δείξω πόσο χρήσιμη είναι η μεθοδολογία της Πληροφορικής.

---

Ακολουθεί η λύση του προβλήματος του ταχυδρόμου

Ακέραιοι είναι αριθμοί, όπως -2, -1, 0, 1, 2…
Θα μπορούσε μια ηλικία να είναι αρνητική; [Όχι].
Θα μπορούσε κάποια ηλικία να είναι μηδέν; [Όχι, αφού το γινόμενό τους είναι 36].
Φτιάχνουμε όλες τις τριάδες ακεραίων που έχουν γινόμενο 36, και δίπλα βάζουμε το άθροισμά τους (ο αριθμός του απέναντι σπιτιού, που τον είδε ο ταχυδρόμος) :
1 + 1 + 36 = 38
1 + 2 + 18 = 21
1 + 3 + 12 = 16
1 + 4 + 9 = 14
1 + 6 + 6 = 13
2 + 2 + 9 = 13
2 + 3 + 6 = 11
3 + 3 + 4 = 10
Αν ο ταχυδρόμος έβλεπε στο απέναντι σπίτι αριθμό 16 θα έλεγε [ηλικίες 1, 3, 12].
Αν έβλεπε αριθμό 15, θα έλεγε [το πρόβλημα δεν λύνεται].
Τι είπε; Είπε ότι κόλλησε.
Γιατί κόλλησε; Επειδή ο απέναντι αριθμός ήταν 13, (ο μόνος που αντιστοιχεί ως άθροισμα δύο τριάδων).
Είπε ότι θέλει μικρή βοήθεια και η κυρία είπε [Η μεγαλύτερη…], δηλαδή ότι υπάρχει μία μεγαλύτερη. (Θυμηθείτε! Μας ενδιαφέρουν μόνο τα στοιχεία που έχουν σχέση με τις ηλικίες που ψάχνουμε!)
Άρα η σωστή απάντηση για τις ηλικίες είναι 2, 2 και 9.

Συγχαρητήρια σε όσους το λύσατε μόνοι σας!