Αλγόριθμος Tower of Hanoi: Python, C++ Code

⚡ Έξυπνη Σύνοψη

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

🗼 Ρύθμιση παζλ: Τρεις πάσσαλοι και n δίσκοι στοιβαγμένοι σε μειούμενο μέγεθος στον πάσσαλο προέλευσης, περιμένοντας να μετακινηθούν στον πάσσαλο προορισμού μέσω ενός βοηθητικού πάσσαλου.
📜 κανόνες: Μόνο ένας δίσκος κινείται κάθε φορά, μόνο ο πάνω δίσκος οποιουδήποτε πασσάλου μπορεί να κινηθεί και ένας μεγαλύτερος δίσκος δεν μπορεί να ακουμπήσει σε έναν μικρότερο δίσκο.
🔁 Αναδρομική Ιδέα: Μετακινήστε n-1 δίσκους στον βοηθό πάσσαλο, μετακινήστε τον μεγαλύτερο δίσκο στον πάσσαλο προορισμού και, στη συνέχεια, μετακινήστε τους n-1 δίσκους από τον βοηθό στον προορισμό.
️ Χρόνος πολυπλοκότητας: Η επίλυση n δίσκων απαιτεί κινήσεις 2^n – 1, δίνοντας μια εκθετική χρονική πολυπλοκότητα O(2^n) που αυξάνεται πολύ γρήγορα καθώς το n αυξάνεται.
🧠 Διαστημική πολυπλοκότητα: Η στοίβα αναδρομής χωράει έως και n πλαίσια ταυτόχρονα, επομένως η πολυπλοκότητα χώρου της αναδρομικής λύσης είναι O(n).
️ εφαρμογές: Διδασκαλία αναδρομής, σχημάτων εναλλαγής αντιγράφων ασφαλείας, μετακίνησης δεδομένων βάσει στοίβας, ρομποτικής αλληλούχισης και κατανόησης του σχεδιασμού αλγορίθμου «διαίρει και βασίλευε».

Περισσότερα

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

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

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

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

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

Πρόβλημα του Πύργου του Ανόι

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

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

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

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

Ο αρχικός μύθος αφορούσε την κίνηση 64 δίσκων. Οι ιερείς μπορούσαν να κινούν έναν δίσκο κάθε φορά σύμφωνα με τους κανόνες. Σύμφωνα με τον μύθο, υπήρχε μια προφητεία ότι ο κόσμος θα τελείωνε αν κατάφερναν να ολοκληρώσουν την πράξη. Στην ενότητα της χρονικής πολυπλοκότητας, θα δείξουμε ότι ένα σκηνικό 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, Προορισμός = Peg C, Βοηθός = Peg B.

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

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

Βήμα 2) Καθώς πραγματοποιούμε μια αναδρομική κλήση από το peg A με προορισμό το peg B, χρησιμοποιούμε το peg C ως βοηθό.

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

Σε αυτό το στάδιο: Πηγή = peg A, Προορισμός = peg B, Βοηθός = peg C.

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

Σε αυτό το στάδιο: Πηγή = peg A, Προορισμός = peg B, Βοηθός = peg C.

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

Σε αυτό το στάδιο: Πηγή = peg A, Προορισμός = peg B, Βοηθός = peg C.

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

Βήμα 6) Στο δεύτερο στάδιο, μετακινούμε τον δίσκο 3 από τον πείρο προέλευσης A στον πείρο προορισμού C.

Σε αυτό το στάδιο: Πηγή = peg A, Προορισμός = peg C, Βοηθός = peg B.

Βήμα 7) Η επόμενη εργασία είναι να μετακινήσουμε τους υπόλοιπους δίσκους από τον βοηθό (peg B) στον προορισμό (peg C). Αυτή τη φορά θα χρησιμοποιήσουμε την αρχική πηγή (peg A) ως βοηθό.

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

Σε αυτό το στάδιο: Πηγή = peg B, Προορισμός = peg A, Βοηθός = peg C.

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

Σε αυτό το στάδιο: Πηγή = peg B, Προορισμός = peg C, Βοηθός = peg A.

Βήμα 10) Ολοκληρώνουμε μετακινώντας τον υπόλοιπο n-1 δίσκο (δίσκο 1) από τον βοηθό στον προορισμό.

Σε αυτό το στάδιο: Πηγή = peg A, Προορισμός = peg C, Βοηθός = peg B.

Παρατσούκλι Code για τον Πύργο του Ανόι

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 δύο φορές.
Ο δίσκος 2 καλεί την αναδρομική συνάρτηση για τον δίσκο 1 δύο φορές.
Ο δίσκος 1 κινείται σε σταθερό χρόνο, δίνοντας τον χρόνο για την επίλυση τριών δίσκων.

Εκφράζεται ως επανάληψη:

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

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

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

Για n δίσκους, αυτό γίνεται:

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

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

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

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

Συχνές Ερωτήσεις

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

Ο ελάχιστος αριθμός κινήσεων για n δίσκους είναι 2^n – 1. Τρεις δίσκοι χρειάζονται 7 κινήσεις, τέσσερις δίσκοι χρειάζονται 15 και δέκα δίσκοι χρειάζονται 1,023 κινήσεις.

Η χρονική πολυπλοκότητα είναι O(2^n) επειδή κάθε επιπλέον δίσκος διπλασιάζει το έργο. Η επαναληπτική εξίσωση T(n) = 2T(n-1) + 1 λύνει την εξίσωση 2^n – 1, η οποία είναι εκθετική.

Η πολυπλοκότητα χώρου είναι O(n) επειδή η στοίβα κλήσεων αναδρομής περιέχει ένα πλαίσιο για κάθε δίσκο που υποβάλλεται σε επεξεργασία. Το μέγιστο βάθος αναδρομής φτάνει το n, επομένως η βοηθητική μνήμη που απαιτείται είναι γραμμική ως προς τον αριθμό των δίσκων.

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

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

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

Ναι. GitHub Copilot, ChatGPT και Gemini δημιουργία αναδρομικών λύσεων του Πύργου του Ανόι στο Python, C++και JavaΟι προγραμματιστές θα πρέπει να επαληθεύουν τις βασικές περιπτώσεις και τη σειρά των ορισμάτων.

Αλγόριθμος Tower of Hanoi: Python, C++ Code

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

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

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

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

Παρατσούκλι Code για τον Πύργο του Ανόι

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

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

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

Συχνές Ερωτήσεις

Συνοψίστε αυτήν την ανάρτηση με:

Εγγραφείτε στο ενημερωτικό δελτίο

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

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

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

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

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

Παρατσούκλι Code για τον Πύργο του Ανόι

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

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

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

Συχνές Ερωτήσεις

Συνοψίστε αυτήν την ανάρτηση με:

Εγγραφείτε στο ενημερωτικό δελτίο