Algoritam kule Hanoi: Python, C++ Code
Sarah Chen
โก Pametni saลพetak
Algoritam Hanojske kule je klasiฤna rekurzivna zagonetka koja pomiฤe hrpu diskova izmeฤu tri klina, a da pritom nikada ne stavlja veฤi disk na manji, ลกto jasno ilustrira princip "zavadi pa vladaj".
ล to je toranj u Hanoju?
Hanojski toranj je matematiฤka zagonetka koja se sastoji od tri ลกtapa i snopa diskova sve manje veliฤine postavljenih jedan na drugi. Poznat je i kao Brahmin toranj ili Lucasov toranj, buduฤi da ga je francuski matematiฤar Edouard Lucas predstavio 1883. godine. Zagonetka se temelji na legendama o pomicanju zlatnih diskova izmeฤu tri ลกtapa.
Ova zagonetka ima tri ลกtapa i promjenjiv broj naslaganih diskova. ล tapovi su rasporeฤeni kao cikliฤki tornjevi, tako da su veฤi diskovi naslagani na dnu, a manji diskovi na vrhu.
U poฤetku imamo tri klina ili ลกipke. Na jednoj od njih (klina A u primjeru) sloลพeni su svi diskovi. Cilj je premjestiti cijeli snop s jedne ลกipke (A) na drugu (C) poลกtujuฤi nekoliko specifiฤnih pravila.
Evo poฤetne postavke slagalice:
Problem kule u Hanoju
I ovo je konaฤni cilj:
Pravila tornja u Hanoju
Evo osnovnih pravila za Hanojski toranj:
- U poฤetnom stanju slagalice, svi diskovi su sloลพeni na ลกtap jedan.
- U konaฤnom stanju, svi diskovi s prve ลกipke sloลพeni su na drugu ili treฤu ลกipku.
- Samo jedan disk se moลพe pomicati s jedne ลกipke na drugu u bilo kojem trenutku.
- Samo se gornji disk na ลกipki moลพe pomicati.
- Disk se ne moลพe postaviti na manji disk.
Izvorna legenda govorila je o pomicanju 64 diska. Sveฤenici su mogli pomicati jedan disk odjednom prema pravilima. Prema legendi, postojalo je proroฤanstvo da ฤe svijet propasti ako uspiju dovrลกiti ฤin. U odjeljku o vremenskoj sloลพenosti pokazat ฤemo da postavka Hanojske kule od n diskova zahtijeva 2^n โ 1 poteza.
Dakle, ako bi sveฤenicima trebala 1 sekunda za pomicanje jednog diska, ukupno vrijeme za rjeลกavanje zagonetke bilo bi 2^64 โ 1 sekunda, ili otprilike 584,942,417,356 godina, 26 dana, 7 sati i 15 sekundi.
Algoritam za Hanojski toranj
Najฤeลกฤi naฤin rjeลกavanja Hanojskog tornja je rekurzivni algoritam. Prvo, biramo dva ลกtapa kao izvor i odrediลกte; rezervni klin djeluje kao pomoฤni ili pomagaฤ.
Evo koraka za rjeลกavanje zagonetke Hanojskog tornja:
- Pomaknite gornjih n-1 diskova s โโizvornog klina na pomoฤni klin.
- Premjesti n-ti disk s izvornog klina na odrediลกni klin.
- Premjestite preostalih n-1 diskova s โโpomoฤnog klina na odrediลกni klin.
Biljeลกka: Ako imamo jedan disk, moลพemo ga premjestiti izravno od izvora do odrediลกta.
Kako rijeลกiti zagonetku Tower of Hanoi
Ilustrirajmo algoritam za tri diska. Razmotrimo klin A kao izvor, klin B kao pomoฤnik i klin C kao odrediลกte.
Korak 1) U poฤetku su svi diskovi sloลพeni na klin A.
U ovoj fazi: Izvor = Peg A, Odrediลกte = Peg C, Pomoฤnik = Peg B.
Sada moramo premjestiti gornjih n-1 diskova iz izvora u pomoฤnik.
Biljeลกka: Iako moลพemo pomicati samo jedan disk odjednom, ovaj korak svodi naลก problem s 3 diska na problem s 2 diska, koji se rjeลกava rekurzivnim pozivom.
Korak 2) Dok vrลกimo rekurzivni poziv iz pega A s pegom B kao odrediลกtem, koristimo peg C kao pomoฤnika.
Primijetite da smo se vratili u prvu fazu za isti problem Hanojske kule, ali sada za dva diska. Pomiฤemo n-1 (tj. jedan) disk od izvora do pomoฤnika, ลกto pomiฤe najmanji disk s klina A na klin C.
U ovoj fazi: Izvor = peg A, Odrediลกte = peg B, Pomoฤnik = peg C.
Korak 3) Prema algoritmu, n-ti (2.) disk se sada prenosi na odrediลกte, peg B.
U ovoj fazi: Izvor = peg A, Odrediลกte = peg B, Pomoฤnik = peg C.
Korak 4) Sada premjeลกtamo n-1 disk (disk jedan) s pomoฤnog klina C na odrediลกni klin B, slijedeฤi treฤu fazu algoritma.
U ovoj fazi: Izvor = peg A, Odrediลกte = peg B, Pomoฤnik = peg C.
Korak 5) Nakon zavrลกetka rekurzivnog poziva, vraฤamo se na prethodnu postavku iz prve faze algoritma.
Korak 6) U drugoj fazi, premjeลกtamo disk 3 s izvornog klina A na odrediลกni klin C.
U ovoj fazi: Izvor = peg A, Odrediลกte = peg C, Pomoฤnik = peg B.
Korak 7) Sljedeฤi zadatak je premjestiti preostale diskove iz pomoฤnika (kolica B) u odrediลกte (kolica C). Ovaj put ฤemo koristiti originalni izvor (kolica A) kao pomoฤnika.
Korak 8) Buduฤi da ne moลพemo pomicati dva diska odjednom, rekurzivno pozivamo za disk 1. Prema naลกem algoritam, odrediลกte u ovom koraku je klin A.
U ovoj fazi: Izvor = peg B, Odrediลกte = peg A, Pomoฤnik = peg C.
Korak 9) Naลก rekurzivni poziv je zavrลกen. Sada premjeลกtamo disk 2 iz izvora u odrediลกte.
U ovoj fazi: Izvor = peg B, Odrediลกte = peg C, Pomoฤnik = peg A.
Korak 10) Zavrลกavamo premjeลกtanjem preostalog n-1 diska (disk 1) iz pomoฤnog ureฤaja u odrediลกte.
U ovoj fazi: Izvor = peg A, Odrediลกte = peg C, Pomoฤnik = peg B.
Nadimak Code za Hanojski toranj
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
Programski kod u 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; }
Izlaz:
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
Programski kod u 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')
Izlaz:
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
Sloลพenost Hanojskog tornja
Evo vremenske i prostorne sloลพenosti Hanojskog tornja:
1) Vremenska sloลพenost:
Osvrฤuฤi se na algoritam, dva puta po pozivu izvrลกavamo rekurzivni poziv za (n-1) diskova. Svaka (n-1) rekurzija se rastavlja na ((n-1)-1) rekurzija i tako dalje, sve dok ne doฤemo do osnovnog sluฤaja s jednim diskom.
Za tri diska:
- Disk 3 dva puta poziva rekurzivnu funkciju za disk 2.
- Disk 2 dva puta poziva rekurzivnu funkciju za disk 1.
- Disk 1 se kreฤe u konstantnom vremenu, ลกto daje vrijeme za rjeลกavanje za tri diska.
Izraลพeno kao ponavljanje:
= 2 ร (Vrijeme rjeลกavanja za dva diska) + konstantno vrijeme pomicanja diska 3
= 2 ร (2 ร vrijeme rjeลกavanja za jedan disk + konstantno vrijeme pomicanja diska 2) + konstantno vrijeme pomicanja diska 3
= (2 ร 2) ร konstantno vrijeme pomicanja diska 1 + 2 ร konstantno vrijeme pomicanja diska 2 + konstantno vrijeme pomicanja diska 3
Za n diskova, ovo postaje:
2n-1 ร konstantno vrijeme za pomicanje diska 1 + 2n-2 ร konstantno vrijeme za pomicanje diska 2 + โฆ.
Ova geometrijska progresija se zbraja u O(2n โ 1), ลกto se pojednostavljuje na O(2n), eksponencijalna vremenska sloลพenost.
2) Sloลพenost prostora:
Prostorna sloลพenost Hanojskog tornja je O(n). Rekurzija koristi stog poziva, a maksimalna dubina stoga jednaka je n, broju diskova. Zato je prostorna sloลพenost O(n).
