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

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

Δοκιμάστε να λύσετε το πρόβλημα των πύργων του Ανόι για 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 του βιβλίου.