Πληροφορική Γ Γυμνασίου

Πύργοι του Ανόι

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

Δοκιμάστε να λύσετε το πρόβλημα των πύργων του Ανόι για 3 δίσκους πατώντας στον παρακάτω σύνδεσμο:

https://www.silvergames.com/el/tower-of-hanoi

Αν έχετε λύσει το πρόβλημα κάνοντας μόνο 7 κινήσεις, καταγράψτε τις στη σελ. 9 του βιβλίου.

Μπορείτε να δοκιμάσετε να λύσετε το πρόβλημα αυξάνοντας σε 4 τους δίσκους; Αν το καταφέρετε κάνοντας μόνο 15 κινήσεις, είστε εξαιρετικοί. Αν όχι, δεν πειράζει. Σημασία έχει ότι το λύσατε.

Στην ιστοσελίδα https://gkanamaria.sites.sch.gr/?p=480 μπορείτε να δείτε ότι η ομορφιά της αναδρομικής λύσης για τους Πύργους του Ανόι κρύβει μια εκθετική πολυπλοκότητα. Ο ελάχιστος αριθμός κινήσεων είναι 2^N – 1, όπου Ν είναι ο αριθμός των δίσκων. Χρησιμοποιήστε τον slider για να δείτε πώς ο αριθμός των κινήσεων αυξάνεται δραματικά με κάθε επιπλέον δίσκο.

Πόσες κινήσεις πιστεύετε ότι θα χρειαστούν για 5 δίσκους και για 64 δίσκους. Χρησιμοποιήστε την αριθμομηχανή για να απαντήσετε και σημειώστε τα αποτελέσματά σας στο κάτω μέρος της σελ. 9 του βιβλίου.

Δημιουργία fractals

Πειραματιστείτε δημιουργώντας τα δικά σας fractals κάνοντας κλικ στον παρακάτω σύνδεσμο

https://sciencevsmagic.net/fractal/#0140,0225,4,3,0,0,2

Επιλέξτε σχήμα, color, random, animate, trails και δείτε τα εντυπωσιακά fractals που δημιουργούνται.

"Παγώστε" την εικόνα σε κάποιο σχήμα που σας άρεσε, πατώντας ξανά στο πλήκτρο animate. Στη συνέχεια πατήστε το πλήκτρο Printscreen (PrtSc) και αποθηκεύστε ένα στιγμιότυπο στον φάκελο Εικόνες του υπολογιστή σας. Στη συνέχεια, αναρτήστε το μαζί με το όνομά σας στο padlet που θα σας υποδειχθεί στο μάθημα.

Spiral με αναδρομή

Κάνοντας κλικ πάνω στο σπιράλ, μπορείτε να δείτε το πρόγραμμα σε scratch που το δημιουργεί.

Το τρίγωνο Sierpinski

(Πηγή: https://gkanamaria.sites.sch.gr/?p=480)

Το Τρίγωνο Sierpinski είναι ένα πολύ γνωστό fractal, το οποίο περιέχει τον εαυτό του. Ξεκινάμε με ένα απλό τρίγωνο. Μετά, το χωρίζουμε σε τέσσερα μικρότερα τρίγωνα και αφαιρούμε το μεσαίο. Τώρα, έχουμε τρία μικρά τρίγωνα, που το καθένα μοιάζει ακριβώς με το αρχικό μεγάλο. Η διαδικασία αυτή επαναλαμβάνεται ξανά και ξανά, σε κάθε ένα από τα μικρότερα τρίγωνα. Αυτό ακριβώς είναι η αναδρομή: η επανάληψη της ίδιας διαδικασίας σε μικρότερη κλίμακα, ξανά και ξανά. Αυξάνοντας το «βάθος» στην εφαρμογή, απλά δείχνουμε πόσες φορές επαναλαμβάνεται αυτή η διαδικασία. Όσο μεγαλύτερο το βάθος, τόσο περισσότερο «βαθιά» βλέπουμε την αναδρομή.

Στην ιστοσελίδα https://gkanamaria.sites.sch.gr/?p=480 πειραματιστείτε με την εφαρμογή δημιουργίας του τριγώνου Sierpinski δοκιμάζοντας να αυξήσετε σταδιακά το βάθος.

Αναδρομή και το φαινόμενο Droste

(Πηγή: https://gkanamaria.sites.sch.gr/?p=480)

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

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

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

Ένα παράδειγμα οπτικής αναδρομής είναι το φαινόμενο Droste. Στο λήμμα Droste effect στη wikipedia μπορείτε να δείτε κάποια παραδείγματα εικόνων που η καθεμία περιέχει τον εαυτό της. Κάντε κλικ πάνω στις εικόνες για να τις δείτε σε μεγαλύτερη διάσταση.