Ενότητα 08 – Δραστηριότητες – Σελίδα 93-96 – ΠΛΗΡΟΦΟΡΙΚΗ Α΄ ΓΥΜΝΑΣΙΟΥ – Απαντήσεις – Λύσεις – ΠΛΗΡΟΦΟΡΙΚΗ Α΄ ΓΥΜΝΑΣΙΟΥ

(Πηγή: Βιβλίο Μαθητή, Πληροφορική Α΄ Γυμνασίου, Κεφάλαιο 8 «Αλγοριθμική», σελ. 93-96. Οι 6 «Δραστηριότητα 1-6» παρακάτω είναι τοπικά αριθμημένα κουτιά ενσωματωμένα μέσα στη θεωρία των §8.2 και §8.3 (καμία δεν βρέθηκε στα §8.1 και §8.4). Οι εκφωνήσεις είναι αυτούσιες από το σχολικό βιβλίο.)

Δραστηριότητες Κεφαλαίου 8

Δραστηριότητα 1 (σελ. 93)

Μετρήστε ακριβώς 6 λίτρα αν έχετε στη διάθεσή σας ένα δοχείο των 5 λίτρων, ένα των 7 λίτρων και μια πηγή με άφθονο νερό. Μπορείτε μόνο να γεμίζετε μέχρι πάνω και να αδειάζετε εντελώς τα δοχεία όσες φορές θέλετε.

Σκέψη / Μεθοδολογία: Ίδιος τύπος προβλήματος με το λυμένο Παράδειγμα 2 της §8.2 (εκεί: δοχεία 5 & 3 λίτρων, στόχος 1 λίτρο), με το ίδιο σύνολο εντολών {Γέμισε(Ν), Άδειασε(Ν), Μετακίνησε(Μ,Ν)}. Περιγράφουμε κάθε κατάσταση με το ζεύγος (a, b) = (λίτρα στο δοχείο των 5, λίτρα στο δοχείο των 7) και αναζητούμε τη συντομότερη ακολουθία εντολών.

Λύση:

Κατάσταση (a, b) = (λίτρα στο δοχείο 5L, λίτρα στο δοχείο 7L). Αρχική κατάσταση: (0, 0).

Με έλεγχο όλων των δυνατών καταστάσεων προκύπτει ότι τα 10 βήματα είναι ο ελάχιστος δυνατός αριθμός.

Απάντηση: Μετά από 10 βήματα, το δοχείο των 7 λίτρων καταλήγει με ακριβώς 6 λίτρα νερού.

Πρόσεξε:

• Υπάρχουν και άλλες σωστές ακολουθίες (π.χ. ξεκινώντας με Γέμισε(5)), αλλά χρειάζονται περισσότερα βήματα (12)· γι' αυτό η λύση σημειώνεται ενδεικτική.
• Τα 6 λίτρα δεν μπορούν ποτέ να βρεθούν στο δοχείο των 5 λίτρων (χωρητικότητα 5 < 6) — μόνο στο δοχείο των 7.
• Ο γρίφος λύνεται επειδή ΜΚΔ(5,7)=1: με δύο δοχεία πρώτων μεταξύ τους χωρητικοτήτων μπορούμε να πετύχουμε οποιαδήποτε ακέραια ποσότητα από 0 έως 7 λίτρα.

Δραστηριότητα 2 (σελ. 93)

Έχετε τρεις κανάτες, μία των 10 λίτρων, μία των 7 λίτρων και μία των 3 λίτρων. Αυτή που χωράει 10 λίτρα είναι γεμάτη και οι άλλες δύο άδειες. Πώς μπορείτε να βάλετε σε μία από τις κανάτες ακριβώς 5 λίτρα νερό, χωρίς ζυγαριά, κάνοντας μόνο μεταφορές νερού από τη μία στην άλλη;

Σκέψη / Μεθοδολογία: Σε αντίθεση με τη Δραστηριότητα 1, εδώ η συνολική ποσότητα νερού είναι σταθερή (10 λίτρα, μοιρασμένα στις τρεις κανάτες) — επιτρέπονται μόνο μεταφορές μεταξύ κανατών. Περιγράφουμε την κατάσταση ως (x, y, z) = (λίτρα στην κανάτα 10L, 7L, 3L) με x+y+z=10 και αναζητούμε τη συντομότερη ακολουθία μεταφορών.

Λύση:

Κατάσταση (x, y, z) = (λίτρα στην κανάτα 10L, 7L, 3L). Αρχική κατάσταση: (10, 0, 0).

Με έλεγχο όλων των δυνατών καταστάσεων προκύπτει ότι οι 8 μεταφορές είναι ο ελάχιστος αριθμός.

Απάντηση: Μετά από 8 μεταφορές, η κανάτα των 7 λίτρων καταλήγει με ακριβώς 5 λίτρα νερό.

Πρόσεξε:

• Η λύση σημειώνεται ενδεικτική επειδή υπάρχουν και άλλες σωστές, αλλά μακρύτερες, ακολουθίες μεταφορών (π.χ. ξεκινώντας με μεταφορά από την κανάτα των 10 στην κανάτα των 3 λίτρων, χρειάζονται 9 μεταφορές και τα 5 λίτρα καταλήγουν στην κανάτα των 10 λίτρων).
• Σε κάθε μεταφορά μετακινείται πάντα το ελάχιστο ανάμεσα σε «όσο έχει η πηγή» και «όσο χώρο έχει ο προορισμός» — ποτέ δεν επιλέγουμε εμείς ενδιάμεση ποσότητα.
• Το άθροισμα των τριών κανατών παραμένει πάντα 10 λίτρα — χρήσιμος έλεγχος ορθότητας σε κάθε βήμα.

Δραστηριότητα 3 (σελ. 94)

Να καταγράψετε τα βήματα του αλγορίθμου της πρόσθεσης αναλυτικά.

Σκέψη / Μεθοδολογία: Το βιβλίο δίνει ακριβώς πριν τη Δραστηριότητα το λυμένο παράδειγμα κάθετης πρόσθεσης 1999 + 39 = 2038 «με κρατούμενα». Μετατρέπουμε τη γνωστή διαδικασία σε ρητά, εκτελέσιμα βήματα αλγορίθμου και επαληθεύουμε πάνω στο ίδιο παράδειγμα του βιβλίου.

Λύση:

1. Δεδομένα εισόδου: δύο ακέραιοι Α και Β, ευθυγραμμισμένοι από τα δεξιά (μονάδες κάτω από μονάδες κ.ο.κ.), με μηδενικά συμπλήρωσης όπου χρειάζεται.
2. Αρχικοποίηση: κρατούμενο = 0, ξεκινάμε από τη στήλη των μονάδων.
3. Επανάληψη (για κάθε στήλη, από δεξιά προς αριστερά): πρόσθεσε τα δύο ψηφία της στήλης και το τρέχον κρατούμενο.
4. Αν το άθροισμα ≥ 10: γράψε το τελευταίο ψηφίο του αθροίσματος (τις μονάδες του), νέο κρατούμενο = 1. Αλλιώς: γράψε όλο το άθροισμα, νέο κρατούμενο = 0.
5. Προχώρα στην επόμενη στήλη αριστερά, επανέλαβε 3-4 μέχρι να εξαντληθούν τα ψηφία.
6. Αν απομείνει κρατούμενο 1 μετά την τελευταία στήλη, πρόσθεσέ το ως νέο τελευταίο (αριστερότερο) ψηφίο.
7. Έξοδος: το αποτέλεσμα είναι η ακολουθία ψηφίων που γράφτηκαν, από αριστερά προς δεξιά.

Επαλήθευση πάνω στο 1999 + 39: μονάδες 9+9=18 → γράψε 8, κρατ.1 · δεκάδες 9+3+1=13 → γράψε 3, κρατ.1 · εκατοντάδες 9+0+1=10 → γράψε 0, κρατ.1 · χιλιάδες 1+0+1=2 → γράψε 2. Αποτέλεσμα: 2038 — ταυτίζεται με το παράδειγμα του βιβλίου.

Απάντηση: Ο αλγόριθμος περιγράφεται στα 7 βήματα παραπάνω· εφαρμοσμένος στο 1999+39 δίνει σωστά 2038.

Πρόσεξε:

• Αποδεκτή κάθε ισοδύναμη διατύπωση των ίδιων βημάτων — σημειώνεται ενδεικτική.
• Το κρατούμενο είναι το κρισιμότερο σημείο που δεν πρέπει να παραλειφθεί.

Δραστηριότητα 4 (σελ. 94)

Να βάλετε στη σειρά τα βήματα εκτέλεσης μιας απλής συνταγής για μακαρόνια με σάλτσα.

Σκέψη / Μεθοδολογία: Δίνονται 10 βήματα σε τυχαία σειρά. Παρατηρήσαμε ότι δύο από αυτά («Αφού στραγγίσετε τα μακαρόνια, τα βάζετε πίσω στην κατσαρόλα με λάδι και βούτυρο και ανακατεύετε» και «Στραγγίστε τα μακαρόνια και στη συνέχεια σερβίρετε στα πιάτα») περιγράφουν εναλλακτικά, αλληλοαποκλειόμενα τελειώματα της ίδιας συνταγής. Επιλέξαμε την πληρέστερη εκδοχή ως κύρια αλυσίδα.

Λύση (σωστή σειρά):

1. Γεμίστε την κατσαρόλα με νερό από τη βρύση.
2. Τοποθετήστε την κατσαρόλα στο μάτι της κουζίνας.
3. Ανοίξτε το μάτι της κουζίνας.
4. Περιμένετε μέχρι να βράσει το νερό.
5. Βάλτε τα μακαρόνια στην κατσαρόλα.
6. Βράζετε τα μακαρόνια για 8 λεπτά.
7. Κλείστε το μάτι της κουζίνας.
8. Αφού στραγγίσετε τα μακαρόνια, τα βάζετε πίσω στην κατσαρόλα με λάδι και βούτυρο και ανακατεύετε.
9. Σερβίρετε τα μακαρόνια με σάλτσα ντομάτας και από πάνω ρίχνετε πιπέρι.

Η δέκατη πρόταση («Στραγγίστε τα μακαρόνια και στη συνέχεια σερβίρετε στα πιάτα») περιγράφει συνοπτικά ακριβώς τα ίδια βήματα 8-9 και δεν προστίθεται ξεχωριστά, αφού θα σήμαινε διπλό στράγγισμα/σερβίρισμα του ίδιου φαγητού.

Απάντηση: Γέμισε την κατσαρόλα με νερό → τοποθέτησέ την στο μάτι → άναψε το μάτι → περίμενε το βράσιμο → βάλε τα μακαρόνια → βράσε 8 λεπτά → σβήσε το μάτι → στράγγισε, βάλε πίσω με λάδι/βούτυρο, ανακάτεψε → σερβίρισε με σάλτσα και πιπέρι.

Πρόσεξε:

• Το γέμισμα με νερό γίνεται στη βρύση, άρα προηγείται της τοποθέτησης της κατσαρόλας στο μάτι.
• Οι δύο διατυπώσεις στράγγισης/σερβιρίσματος είναι εναλλακτικά τελειώματα της ίδιας συνταγής· η λύση ακολουθεί την πιο αναλυτική εκδοχή.

Δραστηριότητα 5. Κρυπτανάλυση (σελ. 96)

Χωριστείτε σε ομάδες των 3-4 ατόμων στην τάξη. Επιλέξτε το μυστικό κλειδί της κρυπτογράφησης και κρυπτογραφήστε με αυτό μια φράση. Στη συνέχεια, να γράψετε στον πίνακα το κρυπτογραφημένο μήνυμα. Ο στόχος είναι να βρείτε τα κλειδιά των άλλων ομάδων και να αποκρυπτογραφήσετε τα μηνύματά τους. Να καταγράψετε αναλυτικά τη στρατηγική που θα ακολουθήσετε κατά την κρυπτογράφηση του δικού σας μηνύματος, αλλά και κατά τη διαδικασία της κρυπτανάλυσης των μηνυμάτων των άλλων ομάδων. Πόσο χρόνο πιστεύετε ότι χρειάζεται ένας απλός υπολογιστής για να «σπάσει» τον κώδικα του Καίσαρα; Υπάρχει τρόπος να τον δυσκολέψετε;

Σκέψη / Μεθοδολογία: Ομαδική/βιωματική δραστηριότητα χωρίς μοναδική «σωστή» φράση/κλειδί. Δίνουμε δειγματική στρατηγική, μαζί με την τεκμηριωμένη (μη ενδεικτική στην ουσία) απάντηση για τον χρόνο εξαντλητικής αναζήτησης: το ελληνικό αλφάβητο έχει 24 γράμματα, άρα μόνο 23 μη-τετριμμένα πιθανά κλειδιά ολίσθησης.

Λύση:

• Κρυπτογράφηση: επιλογή μυστικού κλειδιού k (1-23), επιλογή φράσης, ολίσθηση κάθε γράμματος κατά k θέσεις στο 24γράμματο αλφάβητο (με αναδίπλωση), γράφουμε στον πίνακα μόνο το κρυπτόγραμμα.
• Κρυπτανάλυση των άλλων ομάδων: εξαντλητική αναζήτηση — δοκιμάζουμε διαδοχικά όλα τα 23 πιθανά κλειδιά και ελέγχουμε ποιο δίνει νόημα στα ελληνικά.
• Χρόνος εξαντλητικής αναζήτησης: με μόλις 23 πιθανά κλειδιά, ένας υπολογιστής δοκιμάζει όλα σε χρόνο πρακτικά μηδενικό (< 1 χιλιοστό του δευτερολέπτου), ανεξάρτητα από το μήκος του μηνύματος.
• Πώς δυσκολεύουμε την κρυπτανάλυση: αντί για απλή ολίσθηση, γενική αντικατάσταση όπου κάθε γράμμα αντιστοιχίζεται ελεύθερα σε οποιοδήποτε άλλο — τότε ο χώρος κλειδιών γίνεται 24! (πάνω από 6×10²³ πιθανά αλφάβητα), πρακτικά αδύνατο για εξαντλητική αναζήτηση, αν και ευάλωτο σε στατιστική ανάλυση συχνοτήτων.

Απάντηση (ενδεικτική): Η απλή κρυπτογράφηση Καίσαρα έχει μόνο 23 πιθανά κλειδιά — «σπάει» σχεδόν ακαριαία από υπολογιστή. Δυσκολεύει σημαντικά με γενική αντικατάσταση αλφαβήτου (24! κλειδιά).

Πρόσεξε:

• Το ερώτημα του χρόνου έχει συγκεκριμένη, τεκμηριωμένη απάντηση — δεν πρέπει να συγχέεται με το ανοιχτό/ομαδικό μέρος (επιλογή φράσης/κλειδιού).
• Η γενική αντικατάσταση παραμένει ευάλωτη σε ανάλυση συχνοτήτων γραμμάτων, δεν είναι «απόλυτα ασφαλής».

Δραστηριότητα 6. Έξοδος από Λαβύρινθο (σελ. 96)

Να περιγράψετε έναν αλγόριθμο για την έξοδο από τον παρακάτω λαβύρινθο, αν υποθέσουμε ότι το κόκκινο βέλος δείχνει την είσοδο και το πράσινο βέλος δείχνει την έξοδο. Μια παλιά στρατηγική που οδηγεί, σχεδόν πάντα, στην έξοδο του λαβυρίνθου είναι ο κανόνας του δεξιού χεριού. Τοποθετούμε το δεξί μας χέρι στον τοίχο, προχωράμε και δεν το αφήνουμε ποτέ. Με αυτόν τον τρόπο, σε κάθε στροφή θα πηγαίνουμε δεξιά. Έτσι, δε θα περάσουμε ποτέ δύο φορές από το ίδιο σημείο και αν υπάρχει έξοδος θα τη βρούμε σίγουρα. Η μόνη προϋπόθεση για να λειτουργήσει αυτός ο κανόνας είναι να μην υπάρχουν κενά στον τοίχο.

Σκέψη / Μεθοδολογία: Το βιβλίο περιγράφει ήδη σε πεζό λόγο τη λύση (κανόνας δεξιού χεριού). Η δραστηριότητα ζητά τη μετατροπή της σε ρητά, εκτελέσιμα βήματα αλγορίθμου — γενικά, ανεξάρτητα από τη συγκεκριμένη εικόνα λαβυρίνθου, αφού ο ίδιος αλγόριθμος λειτουργεί σε κάθε λαβύρινθο χωρίς νησίδες τοίχων.

Λύση:

1. Είσοδος: θέση εισόδου (κόκκινο βέλος) και αρχικός προσανατολισμός με το δεξί χέρι πάνω σε τοίχο.
2. Τοποθέτησε το δεξί σου χέρι σε έναν τοίχο, στην είσοδο, και μην το αποκολλήσεις ποτέ.
3. Επανάληψη (όσο δεν έχεις φτάσει στην έξοδο):
   • Αν υπάρχει πέρασμα ΔΕΞΙΑ → στρίψε δεξιά, προχώρα ένα βήμα.
   • Αλλιώς αν υπάρχει πέρασμα ΜΠΡΟΣΤΑ → προχώρα ευθεία.
   • Αλλιώς αν υπάρχει πέρασμα ΑΡΙΣΤΕΡΑ → στρίψε αριστερά, προχώρα.
   • Αλλιώς (αδιέξοδο) → κάνε μεταβολή 180° και προχώρα.
4. Επανέλαβε μέχρι να φτάσεις στην έξοδο (πράσινο βέλος).
5. Έξοδος του αλγορίθμου: η ακολουθία κινήσεων από την είσοδο μέχρι την έξοδο.

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

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

Πρόσεξε:

• Ο αλγόριθμος είναι γενικός: περιγράφεται χωρίς να χρειάζεται να καταγράψουμε κάθε στροφή της συγκεκριμένης εικόνας· μπορούμε όμως να τον «εκτελέσουμε» με το δάχτυλο πάνω στον λαβύρινθο του βιβλίου, ξεκινώντας από το κόκκινο βέλος, για να δούμε ότι φτάνει στο πράσινο.
• Ο κανόνας δεξιού χεριού δεν εγγυάται τη συντομότερη διαδρομή, μόνο ότι θα βρει κάποια — άλλες λύσεις (π.χ. κανόνας αριστερού χεριού) είναι εξίσου αποδεκτές, γι' αυτό η απάντηση σημειώνεται ενδεικτική.