Τετάρτη, 26 Δεκεμβρίου 2012

Ο πύργος του Ανόι



Στόχος του παιχνιδιού είναι να μεταφέρετε όλους τους δίσκους από τον πάσαλο στον οποίο βρίσκονται σε κάποιον άλλο με έναν όμως βασικό περιορισμό: κατά την μετακίνηση ενός δίσκου θα πρέπει να τον τοποθετήσετε πάνω σε κάποιον άλλο με μεγαλύτερες διαστάσεις.
 
Το παιχνίδι περιγράφει γλαφυρά η παρακάτω ιστορία:
« Στο μεγαλόπρεπο Ναό του Benares ,ακριβώς στο κέντρο του ναού είναι στερεωμένο ένα μεταλλικό ορθογώνιο πλαίσιο , πάνω στο πλαίσιο ήταν στερεωμένοι τρεις μεταλλικοί στύλοι ύψους δυο μέτρων ο καθένας .Στον ένα από αυτούς τους στύλους κατά την δημιουργία του κόσμου τοποθετήθηκαν 64 χρυσοί κυκλικοί δίσκοι διαφορετικής διαμέτρου . Οι δίσκοι είναι τοποθετημένοι κατά τέτοιο τρόπο ώστε στην βάση του στύλου να βρίσκεται ο δίσκος με την μεγαλύτερη διάμετρο και οι υπόλοιποι διατάσσονται κατά φθίνουσα σειρά από την μεγαλύτερη διάμετρο στην μικρότερη.(βλέπε σχήμα) Αυτός ο στύλος ονομάζεται ο πύργος του Βράχμα και μέρα -νύχτα οι μοναχοί του μοναστηριού μεταφέρουν τους κυκλικούς δίσκους από τον ένα στύλο στον άλλο, ακολουθώντας τους δυο απαράβατους νομούς του Βράχμα, οι όποιοι απαιτούν ότι ο μοναχός δεν πρέπει να μετακινεί παραπάνω από ένα δίσκο την φορά ,καθώς επίσης δεν επιτρέπεται για κανένα λόγο να τοποθετήσει δίσκο μεγαλύτερης διαμέτρου πάνω σε κυκλικό δίσκο μικρότερης διαμέτρου . Ο Θρύλος λέει ότι όταν όλοι οι δίσκοι μεταφερθούν από τον ένα δίσκο στο άλλο ο κόσμος θα μετατραπεί σε σταχτή και σκόνη.»

Το πρόβλημα να βρεθεί ο αριθμός των κινήσεων που απαιτούνται για την μεταφορά και των 64 δίσκων . Φυσικά και δεν υπάρχει λόγος ανησυχίας αποδεικνύεται ότι για την μεταφορά ν+1 δίσκων απαιτούνται 2^ν-1 κινήσεις ,άρα για το συγκεκριμένο παράδειγμα αν κάθε κίνηση έχει χρόνο 1 δευτερολέπτου απαιτούνται 2^64 -1 κινήσεις , ισοδύναμο χρονικά με 500.000.000.000 χρόνια . Οι πύργοι του Ανόι είναι δημοφιλής άσκηση σε εισαγωγικά μαθήματα προγραμματισμού καθώς απαιτείται συγκεκριμένος αλγόριθμος για την επίλυση του προβλήματος. 
Αναδημοσίευση από: http://mathhmagic.blogspot.gr

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου