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

(Πηγή: Βιβλίο Μαθητή, Πληροφορική Γ΄ Γυμνασίου, Κεφάλαιο 1 «Αλγοριθμική», σελ. 9-10. Το κεφάλαιο (§1.1 Εισαγωγή + §1.2 Αναδρομικοί αλγόριθμοι) δεν έχει δικό του «Ερωτήσεις» υποκεφάλαιο στο ΠΕΡΙΕΧΟΜΕΝΑ, άρα δεν υπάρχει προϋπάρχον lyseis αρχείο από τη Φάση 1 για το Κεφάλαιο 1. Οι 2 «Δραστηριότητα 1-2» παρακάτω είναι τοπικά αριθμημένα κουτιά ενσωματωμένα μέσα στη θεωρία του §1.2. Οι εκφωνήσεις είναι αυτούσιες από το σχολικό βιβλίο.)

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

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

Οι πύργοι του Ανόι. Το πρόβλημα των πύργων του Ανόι είναι χαρακτηριστικό παράδειγμα αναδρομής και θεωρείται από τα θεμελιώδη προβλήματα στην επιστήμη της Πληροφορικής. Έχετε μια μικρή συλλογή από δίσκους και τρεις στύλους (Α, Β, Γ) πάνω στους οποίους μπορείτε να τους τοποθετήσετε. Οι δίσκοι είναι όλοι τοποθετημένοι στον αριστερό στύλο Α σε αύξουσα σειρά ανάλογα με το μέγεθός τους (ο μικρότερος είναι πάνω) και πρέπει να μετακινηθούν στον Γ. Ο Β μπορεί να χρησιμοποιηθεί ως βοηθητικός στύλος. Κανένας δίσκος δεν μπορεί να τοποθετηθεί πάνω από δίσκο που είναι μικρότερος από αυτόν. Μόνο ένας δίσκος μπορεί να μετακινηθεί κάθε φορά.

Βήμα 1: Να λύσετε το πρόβλημα των πύργων του Ανόι για τρεις δίσκους.

Βήμα 2: Να γράψετε έναν αλγόριθμο για μια ιδεατή γλώσσα προγραμματισμού στην οποία η μόνη επιτρεπτή εντολή είναι η Μετακίνησε (αρχή, προορισμός), η οποία μετακινεί τον πάνω δίσκο από τον στύλο αρχή στον στύλο προορισμός. Το πρόγραμμά σας θα μετακινεί τους τρεις δίσκους από τον στύλο Α στον στύλο Γ μέσω του Β. (Το βιβλίο δίνει πίνακα «Μετακίνησε_3_δίσκους (Α, Γ)» με τις δύο πρώτες γραμμές έτοιμες: Μετακίνησε(Α, Γ) και Μετακίνησε(Α, Β).)

Βήμα 3: Να γράψετε έναν αντίστοιχο αλγόριθμο για την περίπτωση των τεσσάρων δίσκων. Παρατηρείτε κάποια σχέση μεταξύ του προβλήματος των τριών και αυτού των τεσσάρων δίσκων; Αν μπορούσατε να χρησιμοποιήσετε την εντολή Μετακίνησε_3_δίσκους (Χ, Υ) για την υλοποίηση του αλγορίθμου Μετακίνησε_4_δίσκους (Χ, Υ), τι θα άλλαζε στην περιγραφή του αλγορίθμου; Όμοια χρησιμοποιήστε τον αλγόριθμο Μετακίνησε_4_δίσκους (Χ, Υ), για να λύσετε το πρόβλημα των 5 δίσκων.

Βήμα 4: Μπορείτε να γενικεύσετε για την περίπτωση των Ν δίσκων; Πόσες κινήσεις πιστεύετε ότι θα χρειαστούν για: α) 3 δίσκους β) 4 δίσκους γ) 5 δίσκους δ) 64 δίσκους;

Σκέψη / Μεθοδολογία: Η κλασική αναδρομική λύση στηρίζεται στον κανόνα: για να μετακινήσουμε Ν δίσκους από τον Χ στον Υ (βοηθητικός ο Ζ) αρκεί να (1) μετακινήσουμε τους πάνω Ν−1 δίσκους Χ→Ζ, (2) μετακινήσουμε τον μεγαλύτερο δίσκο Χ→Υ, (3) μετακινήσουμε τους Ν−1 δίσκους Ζ→Υ — ίδια λογική «λύσε το πρόβλημα με τη λύση ενός μικρότερου ίδιου προβλήματος» με τη θεωρία του §1.1/§1.2. Η ακολουθία κινήσεων επαληθεύτηκε εκτελώντας πραγματικό αναδρομικό πρόγραμμα Hanoi σε Python — οι δύο πρώτες παραγόμενες κινήσεις (Α→Γ, Α→Β) ταυτίζονται ακριβώς με τις δύο έτοιμες γραμμές του πίνακα του βιβλίου.

Λύση:

Βήμα 1 (3 δίσκοι, ονομάζουμε 1=μικρός, 2=μεσαίος, 3=μεγάλος):

Σύνολο 7 κινήσεις· στο τέλος και οι 3 δίσκοι βρίσκονται σωστά ταξινομημένοι στον Γ.

Βήμα 2 — Συμπληρωμένος πίνακας «Μετακίνησε_3_δίσκους (Α, Γ)» (οι δύο πρώτες γραμμές ήταν ήδη δοσμένες):

Μετακίνησε_3_δίσκους (Α, Γ)
1. Μετακίνησε (Α, Γ)   ← δοσμένο
2. Μετακίνησε (Α, Β)   ← δοσμένο
3. Μετακίνησε (Γ, Β)
4. Μετακίνησε (Α, Γ)
5. Μετακίνησε (Β, Α)
6. Μετακίνησε (Β, Γ)
7. Μετακίνησε (Α, Γ)

Οι 7 εντολές αντιστοιχούν ακριβώς στις 7 κινήσεις του Βήματος 1 (η εντολή Μετακίνησε() πάντα μετακινεί «τον πάνω δίσκο» — δεν χρειάζεται να δηλώνουμε ρητά ποιον δίσκο μετακινούμε).

Βήμα 3 — Σχέση 3 και 4 δίσκων: Το πρόβλημα των 4 δίσκων περιέχει μέσα του το πρόβλημα των 3 δίσκων! Αν έχουμε ήδη έτοιμο το υποπρόγραμμα Μετακίνησε_3_δίσκους(Χ, Υ) (που πάντα χρησιμοποιεί σιωπηρά τον τρίτο στύλο ως βοηθητικό), τότε:

Μετακίνησε_4_δίσκους (Α, Γ)
(α) Μετακίνησε_3_δίσκους (Α, Β)   ← οι πάνω 3 δίσκοι Α→Β, βοηθητικός ο Γ
(β) Μετακίνησε (Α, Γ)             ← ο 4ος (μεγάλος) δίσκος απευθείας Α→Γ
(γ) Μετακίνησε_3_δίσκους (Β, Γ)   ← οι 3 δίσκοι Β→Γ, βοηθητικός τώρα ο Α

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

Ομοίως για 5 δίσκους, χρησιμοποιώντας το έτοιμο Μετακίνησε_4_δίσκους:

Μετακίνησε_5_δίσκους (Α, Γ)
(α) Μετακίνησε_4_δίσκους (Α, Β)
(β) Μετακίνησε (Α, Γ)
(γ) Μετακίνησε_4_δίσκους (Β, Γ)

Βήμα 4 — Γενίκευση για Ν δίσκους:

Μετακίνησε_Ν_δίσκους (Χ, Υ)     [Ζ = ο τρίτος, βοηθητικός στύλος]
  αν Ν = 1 τότε
      Μετακίνησε (Χ, Υ)
  αλλιώς
      Μετακίνησε_(Ν−1)_δίσκους (Χ, Ζ)
      Μετακίνησε (Χ, Υ)
      Μετακίνησε_(Ν−1)_δίσκους (Ζ, Υ)

Αν Τ(Ν) = πλήθος κινήσεων για Ν δίσκους: Τ(1) = 1 και Τ(Ν) = 2·Τ(Ν−1) + 1 (δύο φορές η λύση Ν−1 δίσκων, συν 1 κίνηση για τον μεγάλο δίσκο) ⟹ Τ(Ν) = 2^Ν − 1.

Απάντηση (Βήμα 4):

(Εμπλουτιστικό στοιχείο, εκτός ζητούμενης απάντησης: με 1 κίνηση/δευτερόλεπτο, οι 64 δίσκοι του θρύλου των Πύργων του Ανόι/Πύργου του Βραχμά θα χρειάζονταν περίπου 585 δισεκατομμύρια χρόνια — πολύ περισσότερο από την ηλικία του σύμπαντος.)

Πρόσεξε:

• Η εντολή Μετακίνησε(αρχή, προορισμός) δεν δηλώνει ρητά ποιον δίσκο μετακινεί — πάντα μετακινεί «τον πάνω δίσκο» του στύλου-αρχή· η ΣΕΙΡΑ των εντολών καθορίζει έμμεσα ποιος δίσκος κινείται κάθε φορά.
• Η σειρά επίλυσης επιβεβαιώθηκε από τις δύο ΗΔΗ δοσμένες γραμμές του βιβλίου· άλλες έγκυρες ελάχιστες ακολουθίες υπάρχουν (π.χ. συμμετρικά μέσω Β), αλλά μόνο η παραπάνω συμφωνεί με τις δύο δοσμένες πρώτες γραμμές.
• Το 2^Ν−1 είναι το ελάχιστο δυνατό πλήθος κινήσεων.

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

Το τρίγωνο Sierpinski. Το τρίγωνο Sierpinski είναι ένα fractal που κατασκευάζεται με τον εξής αναδρομικό αλγόριθμο: Πρώτα χωρίζουμε ένα τρίγωνο σε τρία μαύρα τρίγωνα με ένα κενό τρίγωνο στη μέση. Στη συνέχεια σε κάθε ένα από τα τρία μαύρα τρίγωνα εφαρμόζουμε τον ίδιο αλγόριθμο κ.ο.κ. Ένα ενδιαφέρον ερώτημα είναι πότε τερματίζει αυτός ο αλγόριθμος; Να εφαρμόσετε τον παραπάνω αλγόριθμο με χαρτί και μολύβι σχεδιάζοντας ένα τρίγωνο Sierpinski. Πόσα βήματα καταφέρατε να εκτελέσετε;

Σκέψη / Μεθοδολογία: Πρακτική/προσωπική δραστηριότητα — δεν υπάρχει μοναδική «σωστή» ζωγραφιά ή αριθμός βημάτων. Δίνουμε όμως τεκμηριωμένη περιγραφή κάθε επιπέδου (με το πραγματικό πλήθος τριγώνων, τύπος 3^ν) και την ΑΚΡΙΒΗ απάντηση στο θεωρητικό ερώτημα «πότε τερματίζει;» — που ΕΧΕΙ μοναδική σωστή απάντηση, ίδιας λογικής με τη «βάση της αναδρομής» της §1.2.

Λύση:

Κατασκευή βήμα-βήμα: σε κάθε επίπεδο, μέσα σε ΚΑΘΕ υπάρχον μαύρο τρίγωνο ενώνουμε τα μέσα των 3 πλευρών του και αδειάζουμε (αφήνουμε λευκό) το κεντρικό, ανάποδο τριγωνάκι που προκύπτει — τα υπόλοιπα 3 μικρότερα τρίγωνα παραμένουν μαύρα και υφίστανται την ίδια διαδικασία στο επόμενο επίπεδο.

Πρακτικό όριο με χαρτί/μολύβι: για αρχικό τρίγωνο πλευράς ~16 εκ., στο επίπεδο 4 υπάρχουν ήδη 81 τριγωνάκια πλευράς ~1 εκ., και στο επίπεδο 5 τα 243 τριγωνάκια έχουν πλευρά μόλις μισό εκατοστό — το πάχος της γραμμής του μολυβιού (~0,5-1 χιλιοστό) γίνεται πια συγκρίσιμο με το ίδιο το σχήμα, οπότε η χειροκίνητη σχεδίαση σταματάει πρακτικά γύρω στο επίπεδο 4-5.

Δειγματική απάντηση μαθητή (ενδεικτική): «Σχεδίασα αρχικά τρίγωνο πλευράς 16 εκ. Κατάφερα να ολοκληρώσω καθαρά 4 επίπεδα (81 τριγωνάκια)· στο 5ο τα τριγωνάκια ήταν τόσο μικρά (κάτω από 1 εκ.) που δεν χωρούσε άλλο κενό τρίγωνο στη μέση τους — σταμάτησα εκεί.»

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

Πρόσεξε:

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