Hanoi Tower algoritmusa: Python, C++ Code

Mi a hanoi torony?

A Hanoi-torony egy matematikai rejtvény, amely három rúdból és egymásra helyezett, egyre kisebb méretű korongokból álló halomból áll. Brahma tornyaként vagy Lucas-toronyként is ismert, mivel a francia matematikus, Edouard Lucas 1883-ban mutatta be. A rejtvény az aranykorongok három rúd közötti mozgatásáról szóló legendákon alapul.

Ez a kirakós játék három rudat és változó számú egymásra helyezett korongot tartalmaz. A rudak ciklikus tornyokként vannak elrendezve, így a nagyobb korongok alul, a kisebbek pedig felül vannak egymásra halmozva.

Kezdetben adottak vagyunk három csapnak vagy rudnak. Az egyikre (a példában az A csapra) az összes korongot egymásra helyezzük. A cél az, hogy a teljes halmot az egyik rúdról (A) a másikra (C) helyezzük át, néhány konkrét szabály betartása mellett.

Íme a puzzle kezdeti felállása:

Hanoi Tower probléma

És ez a végső cél:

A Hanoi Tower szabályai

Íme a Hanoi-torony alapvető szabályai:

• A kirakós kezdeti állapotában az összes korong az egyes rúdra van halmozva.
• Végső állapotban az egyes rúd összes korongja a kettes vagy a harmadik rúdra kerül.
• Egyszerre csak egy korong tud átmozdulni az egyik rúdról a másikra.
• Csak a rúd legfelső korongja mozgatható.
• Egy lemezt nem lehet egy kisebb lemezre helyezni.

Az eredeti legenda 64 korong mozgatásáról szólt. A papok a szabályok szerint egyszerre csak egy korongot mozgathattak. A legenda szerint volt egy jóslat, miszerint a világ vége lesz, ha végrehajtják a műveletet. Az időbonyolultság részben bemutatjuk, hogy egy n korongból álló Hanoi-torony beállítás 2^n – 1 lépést igényel.

Tehát, ha a papoknak 1 másodpercre lenne szükségük egy korong mozgatásához, a rejtvény megoldásának teljes ideje 2^64 – 1 másodperc lenne, azaz nagyjából 584 942 417 356 év, 26 nap, 7 óra és 15 másodperc.

Algoritmus a Tower of Hanoi számára

A Hanoi-torony megoldásának leggyakoribb módja a rekurzív algoritmus. Először két rudat választunk forrásként és célként; a tartalék csap segéd- vagy segítőként működik.

Íme a lépések a Hanoi Tower rejtvény megoldásához:

• Helyezze át a felső n-1 lemezeket a forráscsapról a segédcsapra.
• Mozgasd az n-edik korongot a forráspontról a célpontra.
• Helyezd át a maradék n-1 korongot a segédpöcögről a célpöcögőre.

Jegyzet: Ha egyetlen lemezünk van, akkor azt közvetlenül a forrásból a célhelyre mozgathatjuk.

Hogyan kell megoldani a Tower of Hanoi puzzle-t

Szemléltessük az algoritmust három korong esetén. Tekintsük az A csapot forrásként, a B csapot segítőként, a C csapot pedig célként.

Step 1) Kezdetben az összes korongot az A csapra helyezzük.

Ebben a szakaszban: Forrás = A szeg, Cél = C szeg, Segítő = B szeg.

Most át kell helyeznünk a felső n-1 lemezt a forrásból a segédbe.

Jegyzet: Bár egyszerre csak egy lemezt mozgathatunk, ez a lépés a 3 lemezes problémánkat 2 lemezes problémára redukálja, amelyet egy rekurzív hívás kezel.

Step 2) Mivel rekurzív hívást indítunk az A pegről, a B peg a cél, a C peg-et használjuk segítőként.

Figyeljük meg, hogy visszaértünk az első szakaszhoz ugyanannál a Hanoi-torony problémánál, de most két koronggal. n-1 (azaz egy) korongot mozgatunk a forrásból a segítőbe, amely a legkisebb korongot mozgatja az A csapról a C csapra.

Ebben a szakaszban: Forrás = A szeg, Cél = B szeg, Segítő = C szeg.

Step 3) Az algoritmus szerint az n-edik (2.) lemezt most áthelyezik a célállomásra, a B pontra.

Ebben a szakaszban: Forrás = A szeg, Cél = B szeg, Segítő = C szeg.

Step 4) Most az n-1-es lemezt (az első lemezt) a C segédpegről a B célpegre mozgatjuk, az algoritmus harmadik lépését követve.

Ebben a szakaszban: Forrás = A szeg, Cél = B szeg, Segítő = C szeg.

Step 5) A rekurzív hívás befejezése után visszatérünk az algoritmus első szakaszában korábban beállított értékhez.

Step 6) A második szakaszban a 3-as lemezt áthelyezzük az A forráspontról a C célpontra.

Ebben a szakaszban: Forrás = A szeg, Cél = C szeg, Segítő = B szeg.

Step 7) A következő feladat a maradék lemezek áthelyezése a segédprogramból (B peg) a célprogramba (C peg). Ezúttal az eredeti forrásprogramot (A peg) fogjuk segédprogramként használni.

Step 8) Mivel egyszerre nem mozgathatunk két lemezt, rekurzív hívást végzünk az 1. lemezre. A mi álláspontunk szerint algoritmus, a cél ebben a lépésben az A csap.

Ebben a szakaszban: Forrás = B szeg, Cél = A szeg, Segítő = C szeg.

Step 9) A rekurzív hívásunk befejeződött. Most áthelyezzük a 2. lemezt a forrásból a célhelyre.

Ebben a szakaszban: Forrás = B szeg, Cél = C szeg, Segítő = A szeg.

Step 10) A maradék n-1 lemez (1. lemez) segítőből célállomásra mozgatásával fejezzük be.

Ebben a szakaszban: Forrás = A szeg, Cél = C szeg, Segítő = B szeg.

Pszeudo Code a Hanoi-toronyhoz

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

Programkód be 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;
}

output:

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

Programkód be 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')

output:

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

A Hanoi-torony összetettsége

Íme a Hanoi-torony időbeli és térbeli komplexitása:

1) Időbeli összetettség:

Visszatekintve az algoritmusra, hívásonként kétszer hívunk meg rekurzívan (n-1) lemezt. Minden (n-1) rekurzió ((n-1)-1) rekurzióra bontódik fel, és így tovább, amíg el nem érjük az egylemezes alapesetet.

Három lemez esetén:

• A 3. lemez kétszer hívja meg az 2. lemez rekurzív függvényét.
• A 2. lemez kétszer hívja meg az 1. lemez rekurzív függvényét.
• Az 1. lemez konstans időben mozog, így van idő három korong megoldására.

Ismétlődésként kifejezve:

= 2 × (két korong megoldási ideje) + a 3. korong mozgatásának konstans ideje

= 2 × (2 × egy lemez megoldási ideje + a 2. lemez mozgatásának konstans ideje) + a 3. lemez mozgatásának konstans ideje

= (2 × 2) × az 1. lemez mozgatásához szükséges állandó idő + 2 × a 2. lemez mozgatásához szükséges állandó idő + a 3. lemez mozgatásához szükséges állandó idő

n lemez esetén ez így alakul:

2^{n 1 XNUMX} × állandó idő az 1. + 2. lemez mozgatásához^{n 2 XNUMX} × a 2. lemez mozgatásához szükséges állandó idő + ….

Ez a geometriai sorozat összege O(2ⁿ – 1), ami a következőre egyszerűsödik: O(2ⁿ), exponenciális időbonyolultság.

2) Térbeli komplexitás:

A Hanoi-torony térbonyolultsága O(n). A rekurzió a hívási vermet használja, és a verem maximális mélysége n, a korongok száma. Ezért a térbonyolultság O(n).

GYIK