Hanojski stolpi
Hanojski stolpi oziroma problem Hanojskega stolpa je igra ali uganka s področja razvedrilne matematike. Za igro so potrebne tri palice (trije kupčki), na katere zlagamo (ali natikamo) okrogle ploščice različnih velikosti. Število ploščic je poljubno, vse pa morajo biti različnega premera.
Igra se začne tako, da so ploščice v kupčku na začetnem stolpu urejene od vrha do tal v vrstnem redu od najmanjše do največje, tako da ima kup obliko stožca. Cilj igre je premakniti celotni kupček ploščic na drug kupček ploščic (končni stolp) z najmanjšim možnim številom potez, z upoštevanjem pravil:
- naenkrat lahko premaknemo samo eno ploščico in
- na vrh manjše ploščice ne smemo postaviti večje.
Izvor igre uredi
Igro je izumil francoski matematik Édouard Lucas leta 1883 in o njej v reviji Science et Nature napisal članek, ki je izšel naslednje leto 1884.[1] Obstaja legenda o indijskem templju, ki ima veliko sobo s tremi obrabljenimi drogovi, ki jih obkroža 64 zlatih ploščic. Brahmani premikajo te ploščice glede na pravila igre. Po legendi bo po zadnjem premiku ploščice konec sveta. Uganka je zaradi tega znana tudi kot brahmanski stolpi. Ni znano ali si je Lucas sam izmislil legendo ali ga je le navdahnila. To nalogo (igro) lahko rešujemo na več načinov. Najbolj znana rešitev je rekurzivna in je zato znana tudi kot šolski primer pri računalniškem programiranju.
Če bi bila legenda resnična in če bi lahko duhovniki premikali ploščice s hitrostjo 1 na sekundo, bi bil za najmanjše možno število potez ploščic potreben čas 264−1 sekund, oziroma približno 584,542 milijard let. Vesolje je trenutno staro okrog 13,7 milijard let.
Obstaja več različic legende. Po nekaterih je tempelj samostan, duhovniki pa so menihi. Tempelj ali samostan se lahko nahaja v različnih delih sveta, med njimi tudi v Hanoju v Vietnamu, in je lahko povezan s katerokoli religijo. V nekaterih različicah so vključeni še drugi elementi. Na primer dejstvo, da so bili stolpi narejeni na začetku sveta, ali pa da imajo duhovniki, oziroma menihi za potezo na razpolago le en dan.
Morda je na ime vplival 33,4 m visok stolp v Hanoju, zgrajen leta 1812, na katerem danes visi nacionalna vietnamska zastava.
Rešitev uredi
Večina različic v obliki igrače ima 8 ploščic. Igra se nepoznavalcem zdi nemogoča, čeprav je rešljiva s preprostim algoritmom.
Rešitev z rekurzijo uredi
Kakor v mnogih matematičnih ugankah je iskanje rešitve lažje z rešitvijo rahlo splošnejšega problema: kako premakniti ploščice stolpov višine h (height) z začetnega stolpa f (from) na končni stolp t (to), kjer je r preostali tretji stolp, in velja še t ≠ f. Problem je simetričen za permutacije imen stolpov (grupa simetrij S3). Če je znana rešitev za premike s stolpa f na stolp t, potem se lahko s preimenovanjem stolpov uporabi ista rešitev za vsako drugo izbiro začetnega in končnega stolpa. Če je stolp le en sam (ali, če ga sploh ni), je problem trivialen. Če je h=1, potem je poteza ena s stolpa f na stolp t. Če je h>1, moramo največjo ploščico enkrat v zaporedju potez premakniti s stolpa f na drug stolp, po možnosti na stolp t. Edino stanje, ki dovoljuje to potezo, je kadar so vse druge manjše ploščice na stolpu r. Zato mora vseh prvih h-1 manjših ploščic iti s stolpa f na r. Nato se premakne največja ploščica in nazadnje h-1 manjših ploščic s stolpa r na končni stolp t. Prisotnost največje ploščice ne ovira drugih premikov h-1 manjših ploščic in se ga lahko trenutno prezre. Sedaj se problem prevede na premik h-1 ploščic z enega stolpa na drug, najprej s stolpa f na r, in nato s stolpa r na t; enak postopek je moč izvesti tudi s preimenovanjem stolpov. Uporabi se lahko enaka strategija za prevedbo problema h-1 na h-2, h-3 in tako naprej, dokler ne preostane le ena ploščica. To je rekurzija. Ta algoritem je moč prikazati na naslednji način. Ploščice po naraščajočem vrstnem redu velikosti z naravnimi števili štejemo od 0. Tako je ploščica 0 najmanjša, ploščica h-1 pa največja. Poteze h ploščic z začetnega stolpa f na končni stolp t in pomožni stolp r so:
- korak 1: če je h>1, potem prestavimo h-1 manjših ploščic s stolpa f na stolp r,
- korak 2: sedaj se lahko največja ploščica h-1 prestavi s stolpa f na stolp t,
- korak 3; če je h>1, potem ponovimo postopek in premaknemo h-1 manjših ploščic s stolpa r na stolp t.
S pomočjo matematične indukcije se lahko preprosto pokaže, da zgornji postopek, imenovan direktna metoda[1], vsebuje najmanjše število možnih potez, in da je to tudi enolična rešitev s tem najmanjšim številom potez. Strogo so to trditev dokazali šele leta 1981. Z rekurenčno enačbo se lahko izračuna natančno število potez rešitve: . Pri tem koraka 1 in 3 potrebujeta potez, korak 2 pa eno, kar da . Zaporedje premikov ploščic v optimalni rešitvi problema z n ploščicami je enako prvim členom zaporedja (OEIS A001511):
- 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, ...
To zaporedje je požrešno zaporedje brez ponavljanj. Zaporedje je brez ponavljanj, če ne vsebuje podzaporedja zaporednih členov, oziroma kvadratov. Požrešno zaporedje brez ponavljanj enolično skonstruiramo tako, da na vsakem koraku izberemo najmanjše možno število, ki ne da kvadrata. [2] Takšno zaporedje ima več drugih lastnosti. Splošni člen je na primer Hammingova razdalja med n in n-1 (dvojiško).
Algoritem je moč lepo zapisati v različnih programskih jezikih kot so: Scheme, Haskell, SML, C, Java, Python ali PL/I.
Java uredi
Rešitev hanojskih stolpov rekurzivno v jeziku Java:
// Hanoi.java
public class Hanoi {
public static void main(String[] args) {
int n = 3;
hanoi(n,'A','B','C'); // prestavljamo z A na C; B je pomozna palica
}
private static void hanoi(int n, char a, char b, char c) {
if (n==1) {
System.out.println("Premakni obroc s palice "+a+" na palico "+c);
} else {
hanoi(n-1,a,c,b);
hanoi(1,a,b,c);
hanoi(n-1,b,a,c);
}
}
}
Rešitev s poljubnega začetnega položaja uredi
V C:
int conf[HEIGHT]; /* Element conf[d] da trenutni položaj ploščice d. */
void move(int d, int t) {
/* premik ploščice d na stolp t */
conf[d] = t;
}
void hanoi(int h, int t) {
if (h > 0) {
int f = conf[h-1];
if (f != t) {
int r = 3 - f - t ;
hanoi(h-1, r);
move(h-1, t);
}
hanoi(h-1, t);
}
}
V paskalu:
procedure Hanoi(n: integer; from, to, by: char);
Begin
if (n=1) then
writeln('Move the plate from ', from, ' to ', to)
else begin
Hanoi(n-1, from, by, to);
Hanoi(1, from, to, by);
Hanoi(n-1, by, to, from);
end;
End;
Rešitev z iteracijo uredi
Java uredi
Rešitev hanojskih stolpov iterativno v jeziku Java:
// Hanoi.java
import java.util.*;
class Zahtevek {
public int n;
public char a,b,c;
public Zahtevek(int n, char a, char b, char c) {
this.n=n;
this.a=a;
this.b=b;
this.c=c;
}
}
public class Hanoi {
public static void main(String[] args) {
hanoi(3,'A','B','C'); // prestavljamo z A na C; B je pomozna palica
}
private static void izpisiSklad(Stack s) {
Iterator i = s.iterator();
System.out.println("SKLAD:");
while (i.hasNext()) {
Zahtevek z = (Zahtevek) i.next();
System.out.printf("%d %s %s %s\n", z.n, z.a, z.b, z.c);
}
System.out.println();
}
private static void hanoi(int n, char a, char b, char c) {
Stack s=new Stack();
s.push(new Zahtevek(n,a,b,c));
while (!s.empty()) {
izpisiSklad(s);
Zahtevek z=(Zahtevek)s.pop(); // Eksplicitna pretvorba v zahtevek
n=z.n;
a=z.a;
b=z.b;
c=z.c;
if (n==1) {
System.out.println("Premakni obroc s palice "+a+" na palico "+c);
} else { // Zahtevki v obratnem vrstnem redu obdelovanja
s.push(new Zahtevek(n-1,b,a,c));
s.push(new Zahtevek(1,a,b,c));
s.push(new Zahtevek(n-1,a,c,b));
}
}
}
}
Nerekurzivna rešitev uredi
Seznam premikov ploščic, ki jih da rekurzivni algoritem, kaže več značilnosti. Če štejemo premike od 1, je številka ploščice, ki jo je treba premakniti v potezi m, enaka številu kolikokrat je m deljiv z 2. Zato se v vsaki lihi potezi prestavi najmanjša ploščica (označena z 1). Videti se tudi da, da se najmanjša ploščica premika prek stolpov f, t, r, f, t, r, itd. za liho višino stolpa in prek stolpov f, r, t, f, r, t, itd. za sodo višino stolpa. Ta ugotovitev da naslednji algoritem, ki je preprostejši za premislek od rekurzivnega.
Poteze si sledijo izmenoma:
- premik najmanjše ploščice na stolp, s katerega pred tem ni premaknjena.
- premik druge ploščice, kjer preostane le ena možnost.
Pri prvi potezi gre najmanjša ploščica na stolp t, če je h lih, in na stolp r, če je sod. Če je število ploščic sodo, bodo prve poteze:
|
|
|
|
|
Pri tem velja tudi:
- ploščice, katerih zaporedna številka je soda, se premikajo v enakem smislu kot najmanjša ploščica.
- ploščice, katerih zaporedna številka je liha, se premikajo v nasprotnem smislu.
- če je h sod, so preostali tretji stolpi v zaporednih potezah: t, r, f, t, r, f, itd.
- če je h lih, so preostali tretji stolpi v zaporednih potezah: r, t, f, r, t, f, itd.
Dvojiške rešitve uredi
Položaje ploščic se lahko določi tudi bolj neposredno iz dvojiške (osnova 2) predstavitve številke poteze, kjer je začetno stanje #0 in vse številke 0, in končno stanje #2n−1 z vsemi številkami enakimi 1 z naslednjimi pravili:
- za vsako ploščico obstaja ena dvojiška števka (bit).
- skrajni levi bit predstavlja največjo ploščico. Vrednost 0 označuje, da je največja ploščica na začetnem stolpu, vrednost 1 pa kaže na to, da je ploščica na končnem stolpu.
- niz bitov se bere od leve proti desni, in za določtev položaja odgovarjajoče ploščice se lahko vzame katerikoli bit.
- bit z enako vrednostjo kot predhodni pomeni da je odgovarjajoča ploščica na predhodni ploščici na istem stolpu.
- zaporedje samih enic ali ničel pomeni, da so odgovarjajoče ploščice vse na istem stolpu.
- bit z različno vrednostjo od predhodnega pomeni, da je odgovarjajoča ploščica levo ali desno od predhodne. Ali je levo ali desno, določa pravilo:
- naj je začetni stolp na levi, končni pa na desni.
- pri tem velja tudi, da se desni stolp lahko nahaja »levo« od levega stolpa, in podobno za levi stolp.
- naj je n število večjih ploščic, ki so na istem stolpu kot od njih prva večja ploščica. Pri tem se prišteje 1, če je največja ploščica na levem stolpu. Če je n sod, je ploščica na levem stolpu, če pa je lih, se ploščica nahaja na desnem stolpu.
Za igro z osmimi ploščicami je na primer:
- poteza#
- največja ploščica je 0, zato je na levem (začetnem) stolpu.
- vse preostale ploščice so tudi 0, in so zato na največji ploščici. Zaradi tega so vse ploščice na začetnem stolpu.
- poteza#
- največja ploščica je 1, zato je na desnem (končnem) stolpu.
- tudi vse druge ploščice so 1, in so zato na njej. Zaradi tega so vse ploščice na končnem stolpu in igra je končana.
- poteza#
- največja ploščica je 1, zato je na desnem (končnem) stolpu.
- druga ploščica je tudi 1 in je na njej na desnem stolpu.
- tretja ploščica je 0, zato je na drugem stolpu. Ker je n lih, je na stolpu desno, oziroma na srednjem.
- četrta ploščica je 1, zato je na drugem stolpu od predhodne. Ker je n še vedno lih, je na stolpu desno, oziroma na desnem.
- tudi peta ploščica je 1 in je na predhodni ploščici na desnem stolpu.
- šesta ploščica je 0 in je zato na drugem stolpu. Ker je n sedaj sod, je na stolpu levo, oziroma na srednjem.
- sedma in osma ploščica sta tudi 0, tako da sta na šesti ploščici na srednjem stolpu.
m-to potezo je moč lepo najti iz dvojiške predstavitve m z bitno operacijo. S skladnjo v C je m-ta poteza s stolpa (m&m-1)%3 na stolp ((m|m-1)+1)%3, kjer se ploščice premikajo s stolpa 0 (f) na 1 (t) ali 2 (r), glede na to ali je njihovo število sodo ali liho. Številka ploščice, ki jo je treba premakniti, se lahko določi z vrednostjo kolikokrat je zaporedna številka poteze m deljiva z 2, oziroma s številom ničelnih bitov na desni, kjer je prva poteza 1, ploščice pa so označene zaporedoma naraščajoče 0, 1, 2, itd.
int main(void) {
int m, n, p, t;
printf("\nStevilo ploscic:");
scanf("%d", &n);
for (m=1; m<(1<<n); m++) {
if (m%2) { /* Zaporedna stevilka poteze ni deljiva z 2. */
p=0;
}
else { /* Je deljiva - kolikokrat? */
t=m;
while (t%2 != 1) {
p++;
t/=2;
}
}
printf("\n%5d. %3d: %d na %d", m, p, (m&m-1)%3, ((m|m-1)+1)%3 );
}
}
Rešitev z Grayjevo kodo uredi
Dvojiški sestav Grayjevih kod da drugo rešitev problema. V Grayjevem sistemu so števila predstavljena dvojiško vendar ne s pozicijskim številskim sistemom. Grayjeva koda deluje na predpostavki, da se vsaka vrednost razlikuje od predhodne za natančno en spremenjen bit. Število bitov v Grayjevi kodi je pomembno in vodeče ničle so obvezne z razliko od pozicijskih sistemov.
Če štejemo v Grayjevi kodi z velikostjo bitov enaki številu ploščic v določeni igri hanojskih stolpov in začnemo z 0, potem se spremenjeni bit v vsaki potezi odgovarja ploščici, ki jo je treba premakniti, kjer najmanjši bit predstavlja najmanjšo ploščico, največji bit pa največjo.
Ta postopek določa katero ploščico premikamo, ne pa tudi kam jo premikamo. Za najmanjšo ploščico sta vedno dve možnosti. Za preostale ploščice pa je evdno le ena možnost, razen kadar so vse ploščice na istem stolpu, vendar v tem primeru je treba premakniti najmanjšo ploščico ali pa smo to že storili. Na srečo je pravilo, ki pravi kam je treba premakniti najmanjšo ploščico. Naj je f začetni stolp, t končni in r preostali tretji pomožni. Če je število ploščic liho, najmanjša ploščica kroži po stolpih po vrstenm redu: f→t→r→f→t→r, itd. Če je število ploščic sodo, je vrstni red obrnjen: f→r→t→f→r→t, itd.
Sklici in opombe uredi
Viri uredi
- Klavžar, Sandi (2007). »Požrešno zaporedje brez ponavljanj in problem Hanojskega stolpa«. Obzornik za matematiko in fiziko. Zv. 54, št. 5. str. 145–150.
