Προγραμματισμός < < Προκλήσεις Προγραμματισμού: Ανακαλύπτοντας τους Πύργους του Ανόι - Ανδρείκελα

Η πρόκληση αυτή σας βοηθά να χρησιμοποιήσετε τα ταλέντα προγραμματισμού για να γράψετε ένα πρόγραμμα Java που θα τυπώσει τα βήματα που απαιτούνται για την επίλυση ενός παζλ του Towers of Hanoi, δεδομένου του αριθμού των δίσκων.

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

Το παζλ ξεκινάει με όλους τους δίσκους που στοιβάζονται σε έναν από τους γόμφους, με το μεγαλύτερο δίσκο στο κάτω μέρος και το μικρότερο στην κορυφή. Το αντικείμενο του παζλ είναι να μετακινήσετε τη στοίβα των δίσκων σε έναν από τους άλλους γομφίους, ακολουθώντας μόνο δύο απλούς κανόνες: (1) μπορείτε να μετακινήσετε μόνο ένα δίσκο τη φορά και (2) δεν μπορείτε ποτέ να τοποθετήσετε μεγαλύτερο δίσκο κορυφή ενός μικρότερου.

Το παρακάτω σχήμα δείχνει την λύση για μια στοίβα τριών δίσκων. Όπως μπορείτε να δείτε, η λύση απαιτεί επτά κινήσεις:

Μετακινήστε το δίσκο 1 από το Peg 1 στο Peg 3.
Μετακινήστε το δίσκο 2 από το Peg 1 στο Peg 2.
Μετακινήστε το δίσκο 1 από το Peg 3 στο Peg 2.
Μετακινήστε το δίσκο 3 από το Peg 1 στο Peg 3.
Μετακινήστε το δίσκο 1 από το Peg 2 στο Peg 1.
Μετακινήστε το δίσκο 2 από το Peg 2 στο Peg 3.
Μετακινήστε το δίσκο 1 από το Peg 1 στο Peg 3.

Μετά από αυτά τα επτά βήματα, η στοίβα των δίσκων θα είναι στο Peg 3.

Η λύση για το πύργο του Ανόι παζλ με τρία δίσκους.

Το γρίφο παίρνει ενδιαφέρον όταν αρχίζετε να προσθέτετε δίσκους στην αρχική θέση. Με τρεις δίσκους, το παζλ απαιτεί μόνο 7 κινήσεις για την επίλυση. Με τέσσερις δίσκους απαιτούνται 15 κινήσεις. Με πέντε δίσκους, θα χρειαστείτε 31 κινήσεις. Έξι δίσκοι απαιτούν 64 κινήσεις.

Εάν παρακολουθείτε τα μαθηματικά, ο αριθμός των κινήσεων που απαιτούνται για την επίλυση του παζλ αυξάνει εκθετικά καθώς ο αριθμός των δίσκων αυξάνεται. Συγκεκριμένα, ο αριθμός των κινήσεων που απαιτούνται για την κίνηση δίσκων n είναι 2 ⁿ - 1. Για παράδειγμα, μια στοίβα 20 δίσκων θα απαιτήσει 2 ²⁰ . αυτό είναι πάνω από ένα εκατομμύριο κινήσεις!

Ένας ενδιαφέροντος θρύλος συνδέεται με το παζλ: Σε ένα ναό στο Ανόι, οι μοναχοί εργάζονται σε ένα παζλ του Πύργου του Ανόι με 64 δίσκους από τη δημιουργία της γης. Όταν τελειώσουν, ο κόσμος θα τελειώσει. Ευτυχώς, έχουμε πολύ χρόνο να περιμένουμε: Εάν οι μοναχοί μπορούν να μετακινήσουν έναν δίσκο ανά δευτερόλεπτο, θα είναι άλλα 580 δισεκατομμύρια περίπου χρόνια πριν τελειώσουν το παζλ.

Η πρόκλησή σας είναι απλή: Γράψτε ένα πρόγραμμα Java που θα τυπώσει τα βήματα που απαιτούνται για την επίλυση ενός παζλ του Πύργους του Ανόι με δεδομένο τον αριθμό των δίσκων. Το πρόγραμμα θα πρέπει πρώτα να προτρέψει τον χρήστη για τον αριθμό των δίσκων. Στη συνέχεια θα πρέπει να εμφανίζονται τα βήματα, ένα ανά γραμμή.Κάθε βήμα θα πρέπει να υποδεικνύει ποιο πείρο για να μετακινήσετε ένα δίσκο και ποιο πείρο για να μετακινήσετε το δίσκο. Τα βήματα πρέπει επίσης να είναι αριθμημένα διαδοχικά.

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

Εδώ είναι ένα δείγμα της εξόδου της κονσόλας που θα έπρεπε να δημιουργήσει το πρόγραμμά σας:

Πόσοι δίσκοι; (0 έως τέλος) 3 1: 1 έως 3 2: 1 έως 2 3: 3 έως 2 4: 1 έως 3 5: 2 έως 1 6: 2 έως 3 7: 1 έως 3 Πόσοι δίσκοι; (0 έως τέλος) 0

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

Ο αναδρομικός προγραμματισμός μπορεί να είναι δύσκολος, οπότε εδώ είναι μερικές συμβουλές για τη λύση αυτού του παζλ:

Το παζλ αποτελείται από τρία μανταλάκια. Ένα από αυτά περιέχει την αρχική στοίβα των δίσκων. ονομάστε αυτό το σύνδεσμο πηγή προέλευσης . Ένας από τους δύο υπόλοιπους μανταλάκια είναι ο σύνδεσμος στον οποίο θέλετε να μετακινήσετε τη στοίβα των δίσκων. καλέστε αυτό το τερματισμό του στόχου πρόσδεσης . Ο τρίτος σύνδεσμος είναι διαθέσιμος για να χρησιμοποιείτε ως ενδιάμεσο μπουτόν για την προσωρινή αποθήκευση των δίσκων καθώς τα μετακινείτε. Καλέστε αυτό το σύνδεσμο με το ανταλλακτικό πείρο .
Η αναδρομική μέθοδος σας θα πρέπει να δέχεται τρεις παραμέτρους: τον αριθμό των δίσκων που πρέπει να μετακινηθούν, τον πηγαίο κώδικα και τον στίχο στόχου. Χρησιμοποιήστε τις ακέραιες τιμές 1, 2 και 3 για να αναπαριστάτε τους πείρους.
Η βασική ιδέα για την επίλυση του παζλ αναδρομικά είναι η εξής: Για να μετακινήσετε μια στοίβα δίσκων από ένα πείρο προέλευσης σε ένα πείρο στόχου απαιτούνται τρία βήματα:
1. Μετακινήστε όλους τους δίσκους στη στοίβα, εκτός από τον κάτω δίσκο εφεδρική γόμωση.
2. Μετακινήστε το μεγαλύτερο δίσκο στην αρχική στοίβα στο στόχο στόχου.
3. Μετακινήστε τη στοίβα που μετακινήσατε στο Βήμα 1 από τον εφεδρικό κύλινδρο στο στόμιο στόχου.
Φυσικά, οι κανόνες παζλ σας επιτρέπουν να μετακινήσετε μόνο ένα δίσκο τη φορά, έτσι δεν μπορείτε να ολοκληρώσετε τα βήματα 1 και 3 της διαδικασίας που δίνονται εδώ απλά να σηκώσετε τη στοίβα και να την μετακινήσετε. Εκεί που εισέρχεται η επανάληψη. Για τα βήματα 1 και 3, ονομάζετε την μέθοδο αναδρομικά, κάθε φορά που καθορίζετε λιγότερους δίσκους που πρέπει να μετακινηθούν και κάθε φορά που χρησιμοποιείτε τον προηγούμενο στίχο στόχου ως εφεδρικό στύλο.
Αναρωτιέστε γιατί η αναδρομική μέθοδος δεν χρειάζεται να δεχτεί τον εφεδρικό σύνδεσμο ως επιχείρημα; Επειδή μπορείτε να το υπολογίσετε εύκολα, λαμβάνοντας υπόψη τις πηγές προέλευσης και στόχων. Δεδομένου ότι υπάρχουν μόνο τρεις μανταλάκια, αριθμημένα 1, 2 και 3, το άθροισμα των τριών μανταλάκια είναι 6 (1 + 2 + 3). Λαμβάνοντας υπόψη τους πείρους πηγής και στόχου, μπορείτε να υπολογίσετε τον εφεδρικό κύλινδρο αφαιρώντας τον πείρο προέλευσης και το στόχο από το 6. Για παράδειγμα, αν ο πείρος προέλευσης είναι 1 και ο στόχος στόχου είναι 3, ο εφεδρικός στρόφαλος πρέπει να είναι 2 επειδή

6 - 3 - 1 = 2.