Hanoi Tower algoritmusa: Python, C++ Kód
Sarah Chen
Mi a hanoi torony?
A Hanoi Tower egy matematikai kirakós játék, amely három rúdból és számos, egymásra helyezett korongból áll. Brahma-toronyként vagy Lucas-toronyként is ismert, ahogy Edouard Lucas francia matematikus bemutatta még 1883-ban. Ez a rejtvény az aranykorongok három rúd közötti mozgatásával kapcsolatos legendákon alapul.
Ez a kirakó három rúdból és változó számú egymásra helyezett korongból áll. Ezeket a rudakat ciklikus tornyoknak tervezték. Tehát a nagyobb átmérőjű korongok alulra, a kisebbek pedig felülre kerülnek.
Kezdetben három csapot vagy rudat kapunk. És az egyikben (A, a példában látható) az összes lemez egymásra van rakva. Célunk, hogy egy teljes korongköteget mozgassunk az egyik rúdról (A) a másikra (C) néhány speciális szabály betartásával.
Íme a rejtvény kezdeti beállítása -
És ez a végső cél...
A Hanoi Tower szabályai
Íme néhány alapvető szabály a Hanoi-toronyra vonatkozóan:
- A kirakós játék kezdeti állapota, az összes korong egy rúdba kerül.
- A végső állapot az, hogy az első rúd összes lemeze a második vagy a harmadik rúdra kerül.
- Bármikor áthelyezhetünk egy lemezt egyik rúdról a másikra.
- Csak a legfelső korongot tudjuk elmozdítani a rúdról.
- Egy lemezt nem lehet másik lemez fölé helyezni, amely kisebb.
Az eredeti legenda 64 lemez áthelyezéséről szólt. A papok a szabályoknak megfelelően egy-egy korongot mozgathattak. A legenda szerint volt egy jóslat, amely szerint a világ vége lesz, ha be tudják fejezni az aktust. Az időbonyolultság részben megmutatjuk, hogy egy n lemezből álló Tower of Hanoi beállítás 2^n – 1 lépésbe kerülne.
Tehát, ha a papoknak 1 másodpercre lenne szüksége a korongok mozgatásához, akkor a rejtvény megfejtéséhez szükséges teljes idő 2^64 – 1 másodperc vagy 584,942,417,356 26 7 15 év, XNUMX nap, XNUMX óra és XNUMX másodperc.
Algoritmus a Tower of Hanoi számára
A Hanoi Tower megoldásának egyik általános módja a rekurzív algoritmus. Először is el kell döntenünk, hogy két rúd vagy csap lesz a forrás és a cél, és a tartalék csap segéd vagy segéd lehet.
Í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.
- Ezután helyezze át az n-edik lemezt a forrás peg-ről a célpontra.
- Végül helyezze át a többi n-1 lemezt a segédcsapról a célcsapra.
Megjegyzések: Ha egyetlen lemezünk van, azt közvetlenül áthelyezhetjük a forrásból a célba.
Hogyan kell megoldani a Tower of Hanoi puzzle-t
Szemléltessük az algoritmust három lemezre, és tekintsük az A-t a forrásnak, a B-t a segítőnek és a C-t a célnak.
Step 1) Kezdetben az összes lemez az A ponton lesz egymásra rakva.
Ezen a ponton:
Forrás = Peg A
Célhely = Peg C
Segítő = Peg B
Most át kell helyeznünk a felső n-1 lemezt a forrásból a segédbe.
Jegyzet: Bár egyszerre csak egy lemezt tudunk mozgatni, ez a problémánkat 3 lemezes problémáról 2 lemezes problémára szakítja, ami egy rekurzív hívás.
Step 2) Mivel rekurzív hívást hívunk az A pontról, és a cél a B kapcsoló, a C kapcsolót fogjuk használni segítőként.
Vegyük észre, hogy ismét az első szakaszban vagyunk ugyanazon Hanoi torony problémájában két lemez esetében.
Most n-1-et vagy egy lemezt kell áthelyeznünk a forrásból a segédbe, a legkisebb lemezt mozgatva az A-ról a C-be.
Ezen a ponton:
Forrás = A pont
Célhely = B pont
Segítő = C csap
Step 3) Ezután az algoritmusunk szerint az n-edik vagy a 2. lemezigényt át kell vinni a célba vagy a B pontba.
Ezen a ponton:
Forrás = A pont
Célhely = B pont
Segítő = C csap
Step 4) Most mozgatjuk az n-1 lemezt vagy egy lemezt a segítőről vagy a C kapcsolóról a rendeltetési helyre vagy a B csatlakozóba az algoritmusunk harmadik szakaszának megfelelően.
Ezen a ponton:
Forrás = A pont
Célhely = B pont
Segítő = C csap
Step 5) A rekurzív hívás befejezése után az algoritmus első szakaszában visszatérünk a korábbi beállításunkhoz.
Step 6) Most, a második szakaszban, áthelyezzük a forrásunkat a célunkra, amely a 3. lemezt a C pontra mozgatja az A pontról.
Ezen a ponton:
Forrás = A pont
Célhely = C pont
Segítő = B csap
Step 7) Most ezt láthatjuk
d a maradék lemezek áthelyezése a segédről (B csatlakozó) a célállomásra (C pont). Ebben az esetben a kiindulási forrást vagy az A-t használjuk segítségül.
Step 8) Mivel nem tudunk egyszerre két lemezt mozgatni, rekurzív hívást fogunk hívni az 1. lemezhez. Az utolsó lépésnek megfelelően algoritmus, a cél ebben a lépésben az A pont.
Ezen a ponton:
Forrás = B pont
Célhely = A pont
Segítő = C csap
Step 9) Rekurzív hívásunk most befejeződött. Ezután áthelyezzük a 2-es lemezt a forrásból a rendeltetési helyére.
Ezen a ponton:
Forrás = B pont
Célhely = C pont
Segítő = A csap
Step 10) Ezután a maradék n-1-et vagy 1-es lemezünket a segítőből a célba helyezzük.
Ezen a ponton:
Forrás = A pont
Célhely = C pont
Segítő = B csap
Pszeudo kód 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;
}
teljesítmény
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ő- és térkomplexitása:
1) Időbeli összetettség:
Ha visszatekintünk az algoritmusunkra, láthatjuk, hogy kétszer vezetünk be rekurzív hívást (n-1) lemezekre. Az (n-1) lemezre vonatkozó rekurzív hívások további ((n-1)-1)-re bonthatók, és így tovább, amíg csak egy lemezt kell mozgatni.
Három lemezhez -
- A 3. lemez kétszer hívja meg a kettes lemez rekurzív függvényét.
- A 2. lemez kétszer hívja meg az XNUMX. lemez rekurzív függvényét.
- Az 1. lemez konstans időn belül mozoghat, és három lemez esetén a megoldási idő.
= 2*(Két lemez megoldásának ideje) + állandó A 3. lemez mozgatásának ideje
= 2*(2*megoldási idő egy lemezhez + állandó 2. lemez mozgatásának ideje) + állandó 3. lemez mozgatásának ideje
= (2*2) (állandó idő az 1. lemez mozgatásához) + 2*konstans idő a 2. lemez mozgatásához + állandó idő a 3. lemez mozgatásához
n lemez esetén a következőképpen írható:
(2n 1 XNUMX * állandó idő az 1 + 2 lemez mozgatásáhozn 2 XNUMX * állandó idő a 2. lemez mozgatásához + ….
Ez a geometriai progresszió O(2n 1 XNUMX), Vagy O(2n), ami exponenciális.
2) A tér összetettsége
A Hanoi-torony térbonyolultsága 0(n). Ez azért van, mert tárolnunk kell a lemezek sorrendjét. Amikor a rekurziót használjuk, az a veremet használja. A köteg maximális mérete pedig „n” lehet. Ezért lesz a térkomplexitás O(n).
