Αλγόριθμος Tower of Hanoi: Python, C++ Κώδικας

Τι είναι ο Πύργος του Ανόι;

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

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

Αρχικά, μας δίνονται τρία μανταλάκια ή ράβδοι. Και ένα από αυτά (Α, φαίνεται στο παράδειγμα) έχει όλους τους δίσκους στοιβαγμένους. Στόχος μας είναι να μετακινήσουμε μια ολόκληρη στοίβα δίσκων από τη μια ράβδο (Α) στην άλλη (C) ακολουθώντας ορισμένους συγκεκριμένους κανόνες.

Εδώ είναι η αρχική ρύθμιση του παζλ-

Και αυτός είναι ο τελικός στόχος -

Κανόνες του Πύργου του Ανόι

Ακολουθούν ορισμένοι βασικοί κανόνες για τον Πύργο του Ανόι:

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

Ο αρχικός μύθος αφορούσε τη μετακίνηση 64 δίσκων. Οι ιερείς μπορούσαν να μετακινήσουν έναν δίσκο τη φορά σύμφωνα με τους κανόνες. Σύμφωνα με το μύθο, υπήρχε μια προφητεία ότι ο κόσμος θα τελείωνε αν μπορούσαν να ολοκληρώσουν την πράξη. Στην ενότητα χρονικής πολυπλοκότητας, θα δείξουμε ότι μια ρύθμιση Tower of Hanoi με n δίσκους θα κόστιζε 2^n – 1 κίνηση.

Έτσι, εάν οι ιερείς μπορούσαν να χρειαστούν 1 δευτερόλεπτο για να μετακινήσουν τους δίσκους, ο συνολικός χρόνος που θα χρειαζόταν για να λύσουν το παζλ θα ήταν 2^64 – 1 δευτερόλεπτο ή 584,942,417,356 χρόνια, 26 ημέρες, 7 ώρες και 15 δευτερόλεπτα.

Αλγόριθμος για τον Πύργο του Ανόι

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

Εδώ είναι τα βήματα για να λύσετε το παζλ του Πύργου του Ανόι:

Μετακινήστε τους επάνω δίσκους n-1 από τον πείρο προέλευσης στον βοηθητικό πείρο.
Στη συνέχεια, μετακινήστε τον nο δίσκο από τον δεσμό προέλευσης στον δεσμό προορισμού.
Τέλος, μετακινήστε τους υπόλοιπους δίσκους n-1 από το βοηθητικό μανταλάκι στο μανταλάκι προορισμού.

Σημείωση: Εάν έχουμε έναν μόνο δίσκο, μπορούμε να τον μετακινήσουμε απευθείας από την πηγή στον προορισμό.

Πώς να λύσετε το παζλ Tower of Hanoi

Ας παρουσιάσουμε τον αλγόριθμο για τρεις δίσκους και ας θεωρήσουμε το peg A ως πηγή, το peg B ως βοηθητικό και το peg C ως προορισμό

Βήμα 1) Αρχικά, όλοι οι δίσκοι θα στοιβάζονται στο μανταλάκι Α.

Σε αυτό το στάδιο:

Πηγή = Peg A
Προορισμός = μανταλάκι Γ
Βοηθός = Παγκάκι Β

Τώρα, πρέπει να μετακινήσουμε τους επάνω δίσκους n-1 από την πηγή στο βοηθητικό πρόγραμμα.

Σημείωση: Αν και μπορούμε να μετακινήσουμε μόνο έναν δίσκο κάθε φορά, αλλάζει το πρόβλημά μας από πρόβλημα 3 δίσκων σε πρόβλημα 2 δίσκων, το οποίο είναι μια αναδρομική κλήση.

Βήμα 2) Καθώς καλούμε μια επαναλαμβανόμενη κλήση από το μανταλάκι Α και ο προορισμός είναι το μανταλάκι Β, θα χρησιμοποιήσουμε το μανταλάκι Γ ως βοηθητικό.

Παρατηρήστε ότι βρισκόμαστε ξανά στο πρώτο στάδιο για τον ίδιο πύργο του Ανόι πρόβλημα για δύο δίσκους.

Τώρα πρέπει να μετακινήσουμε το n-1 ή έναν δίσκο από την πηγή σε βοηθητικό, μεταφέροντας τον μικρότερο δίσκο από τον πείρο Α στο μανταλάκι Γ.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Α
Προορισμός = μανταλάκι Β
Βοηθός = μανταλάκι Γ

Βήμα 3) Στη συνέχεια, σύμφωνα με τον αλγόριθμό μας, οι ανάγκες του nου ή του 2ου δίσκου θα πρέπει να μεταφερθούν στον προορισμό ή το peg B.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Α
Προορισμός = μανταλάκι Β
Βοηθός = μανταλάκι Γ

Βήμα 4) Τώρα, θα μετακινήσουμε τους δίσκους n-1 ή τον δίσκο ένα από το βοηθητικό ή το μανταλάκι C στον προορισμό ή το μανταλάκι Β σύμφωνα με το τρίτο στάδιο του αλγορίθμου μας.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Α
Προορισμός = μανταλάκι Β
Βοηθός = μανταλάκι Γ

Βήμα 5) Μετά την ολοκλήρωση της επαναλαμβανόμενης κλήσης, θα επιστρέψουμε στην προηγούμενη ρύθμιση όταν το πρώτο στάδιο του αλγορίθμου.

Βήμα 6) Τώρα, στο δεύτερο στάδιο, θα μετακινήσουμε την πηγή μας στον προορισμό μας, ο οποίος είναι η μετακίνηση του δίσκου 3 στο μανταλάκι C από τον πείρο Α.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Α
Προορισμός = μανταλάκι Γ
Βοηθός = μανταλάκι Β

Βήμα 7) Τώρα μπορούμε να το δούμε αυτό

d είναι να μετακινήσετε τους εναπομείναντες δίσκους από το βοηθητικό πρόγραμμα (στήριγμα Β) στον προορισμό (στήριγμα C). Θα χρησιμοποιήσουμε την αρχική πηγή ή το μανταλάκι Α ως βοηθητικό σε αυτή την περίπτωση.

Βήμα 8) Καθώς δεν μπορούμε να μετακινήσουμε δύο δίσκους ταυτόχρονα, θα καλέσουμε μια αναδρομική κλήση για δίσκο 1. Σύμφωνα με το τελευταίο βήμα και αλγόριθμος, ένας προορισμός σε αυτό το βήμα είναι το μανταλάκι Α.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Β
Προορισμός = μανταλάκι Α
Βοηθός = μανταλάκι Γ

Βήμα 9) Η επαναληπτική κλήση μας ολοκληρώθηκε τώρα. Στη συνέχεια μετακινούμε τον δίσκο 2 από την πηγή του στον προορισμό του.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Β
Προορισμός = μανταλάκι Γ
Βοηθός = μανταλάκι Α

Βήμα 10) Στη συνέχεια μεταφέρουμε το υπόλοιπο n-1 ή το δίσκο 1 από τον βοηθό στον προορισμό.

Σε αυτό το στάδιο:

Πηγή = μανταλάκι Α
Προορισμός = μανταλάκι Γ
Βοηθός = μανταλάκι Β

Ψευδοκώδικας για τον Πύργο του Ανόι

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

Κωδικός προγράμματος μέσα C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

Παραγωγή

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Κωδικός προγράμματος μέσα Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

Παραγωγή:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Πολυπλοκότητα του Πύργου του Ανόι

Εδώ είναι η χρονική και χωρική πολυπλοκότητα του Πύργου του Ανόι:

1) Χρονική πολυπλοκότητα:

Αν κοιτάξουμε πίσω στον αλγόριθμό μας, μπορούμε να δούμε ότι εισάγουμε μια αναδρομική κλήση για δίσκους (n-1) δύο φορές. Αυτές οι αναδρομικές κλήσεις για δίσκους (n-1) μπορούν να αναλυθούν σε άλλους ((n-1)-1) και ούτω καθεξής μέχρι να έχουμε μόνο έναν δίσκο για να μετακινηθεί.

Για τρεις δίσκους-

Ο δίσκος 3 καλεί μια αναδρομική συνάρτηση για το δίσκο δύο δύο φορές.
Ο δίσκος 2 καλεί μια αναδρομική συνάρτηση για το δίσκο δύο φορές.
Ο δίσκος 1 μπορεί να κινηθεί μέσα σε σταθερό Χρόνο και Χρόνος επίλυσης για τρεις δίσκους.

= 2*(Χρόνος επίλυσης για δύο δίσκους) + σταθερός Χρόνος μετακίνησης δίσκου 3

= 2*(2*χρόνος επίλυσης για έναν δίσκο + σταθερή Χρόνος μετακίνησης δίσκου 2) + σταθερός Χρόνος μετακίνησης δίσκου 3

= (2*2) (σταθερός χρόνος για τη μετακίνηση του δίσκου 1) + 2*σταθερός χρόνος για τη μετακίνηση του δίσκου 2 + σταθερός χρόνος για τη μετακίνηση του δίσκου 3

Για n δίσκους, μπορεί να γραφτεί ως -

(2^n-1* σταθερός χρόνος για τη μετακίνηση του δίσκου 1 + 2^n-2 * σταθερός χρόνος μετακίνησης δίσκου 2 + ….

Αυτή η γεωμετρική πρόοδος θα έχει ως αποτέλεσμα το O(2^n-1) ή Ο (2ⁿ), που είναι εκθετική.

2) Πολυπλοκότητα χώρου

Η διαστημική πολυπλοκότητα του Πύργου του Ανόι είναι 0(n). Αυτό συμβαίνει γιατί πρέπει να αποθηκεύσουμε τη σειρά των πλακών. Όταν χρησιμοποιούμε την αναδρομή, χρησιμοποιεί τη στοίβα. Και το μέγιστο μέγεθος της στοίβας μπορεί να είναι "n". Γι' αυτό η πολυπλοκότητα του χώρου γίνεται O(n).

Μπορεί να σας αρέσει:

Τι είναι ο Πύργος του Ανόι;

Κανόνες του Πύργου του Ανόι

Αλγόριθμος για τον Πύργο του Ανόι

Πώς να λύσετε το παζλ Tower of Hanoi

ΣΧΕΤΙΚΑ ΑΡΘΡΑ

Ψευδοκώδικας για τον Πύργο του Ανόι

Κωδικός προγράμματος μέσα C++

Κωδικός προγράμματος μέσα Python

Πολυπλοκότητα του Πύργου του Ανόι