i
i
“1208-Pezdir-posploseni” — 2010/7/21 — 9:33 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 22 (1994/1995)
Številka 1
Strani 10–16
Ciril Pezdir:
POSPLOŠENI HANOJSKI STOLP
Ključne besede: matematika, računalništvo, programiranje, rekurzije.
Elektronska verzija: http://www.presek.si/22/1208-Pezdir.pdf
c© 1994 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
POsPLOSENI HANOJSKI STOLP
Hanojski stolp verjetno večina bralcev že pozna (slika spodaj) . Vendar se v
prispevku ne bomo ukvarjali le z osnovno verzijo hanojskega stolpa, temveč
bomo nalogo nekoliko posplošili.
Najprej pa nekaj uvodnih besed za tiste , ki se boste s tem stolpom
srečali prvič. Kot je razvidno z zgornje slike, hanojski stolp sestavljajo okrogle
ploščice različnih velikosti, zložene na položaju z oznako A. Naloga zahteva ,
da prestavimo stolp z n ploščicami na položaj C, pri čem e r si lahko pomagamo
s pomožnim položajem B . Pri prestavljanju pa moramo upoštevati naslednji
pravili:
1. na vsaki ploščici lahko ležijo le manjše ploščice;
2. hkrati lahko prestavimo le po eno vrhnjo ploš čice.
Najprej poskusimo prestaviti stolp z majhnim številom ploščic , potem
pa število ploščic povečujmo. Pri večjem številu ploščic izgubimo pregled in
nalogi nismo več kos brez papirja in svinčnika . Program, napisan v pascalu ,
nam pomaga prestaviti stolp z veliko ploščicami:
program Hanojski.stolp:
var n: integer; { velikost stolpa }
procedure Prestavi(izvor, pomozni , cilj: char; n: integer) ;
{ Prestavi n plo š čic s polo taja izvor na polože] cilj, }
{ pri čemer si pomaga spomotnim polotajem pomozni.
begin
if n>O then begin
Prestavi(izvor, cilj, pomozni, n-L) :
writeln('Prestavi plos cico spolozaja ' ,izvor, na polozaj ' ,cilj .' . ') ;
Prestavi(pomozni, izvor, cilj, n-L):
end ;
end ;
11
begin { glavni program }
write(,Vnesi velikost stolpa: ') ; readln(n);
Prestavi(, A', 'B ', 'C' , n) ;
end.
Način reševanja naloge je rekurziven. Vidimo, da podprogram Prestavi
kliče sam sebe, vendar z drugačnimi parametri . Delovanje pod programa lahko
razložimo takole:
A 8 c
t==j
I I
I I
Prestaviti želimo stolp z ' n ploščicami s položaja A na položaj C preko
pomožnega položaja B; klic Prestavi('A', 'B' , ' C' , n) v glavnem programu.
f=?,
I I
ABe
Potem prestavimo spodnjo ploš čice na ciljni položaj; izpis writeln('Pre-
stavi ploscico s polozaja ', i z vor,' na polozaj ', c il j,' . ') v podpro-
gramu .
A B c
Nazadnje stolp z n - 1 ploščicami prestavimo s pomožnega na ciljni
položaj ; klic Prestavi(pomozni, izvor , cilj, n-1) v podprogramu .
Premik stolpa z n - 1 ploščicam i seveda opravimo rekurzivno na enak
način , le izvorn i, ciljni in pomožni položaj so drugače razporejeni. Rekurzijo
končamo, ko nam ni več potrebno prestaviti nobene ploščice.
Izračunajmoše število potrebnih premikov za prestavitev stolpa n ploščic .
Označimo to število z N(n) . Iz podprograma Prestavi zlahka razberemo
N(1) =1 in rekurzivno zvezo
N(n) = N(n - 1) + 1 + N(n - 1) = 2· N(n - 1) + 1.
{ velikos t sto/pa }
{ sk upno šte vilo polo žajev }
{ zatetn i in kon čni po/o:taj }
12
Tako je
N(n) = 2 . N(n - 1) + 1 = 2 · (2 . N(n - 2) + 1) + 1
= 2 . (2 . (2 . N(n - 3) + 1) + 1) + 1
= 2 . (2 . (2 . ... . (2 . (2 . N( l) + 1) + 1) + .. .+ 1) + 1) + 1
=2n - 1 + 2n - 2 + .. .+ 8 + 4 + 2 + 1 = 2n - 1
Zad njo enakost dobimo, če v zvezo an - b" =(a - b)(a n - 1 + a n - 2 b+
+ ...+ ab n-2 + bn- 1 ) vstavimo a = 2 in b =1. To je tudi najmanj še mo žno
število premikov , ka r se da lepo do kaza ti z matemati čno indukcijo .
Pa povečajmo število položajev. Kako si lahko sedaj , z večjim številom
pomožnih položajev pomagamo pri prestavlj anju st o lpa? Navedeni program
poišče reš itev , ki zaradi uporabe dodatnih pomožnih položajev po trebuje
precej ma nj prem ikov kot rešitev , ki jo poišče prej šnji prog ram .
program Posp loseni.hanojski.stolp:
var
n: integer ;
k: integer;
izvor, cilj: integer ;
function Pomozni(i , izvor, cilj: integer): integer;
{ Poi š če stevilko i- tega pom o žnege polo že]e , }
{ t e izvzam em o polo žeje izvor in cilj. }
begin
if i> =i zvor then i:=i +1;
if i>=cilj then i:=i+1;
if ieeizvor then i:= i+1;
Pomozni:=i;
end ;
procedure Prestavi(izvor , cilj, n, k: integer) ;
{ Prestavi n plo š čic s polo žejs izvor na polo že] cilj,
{ pri čemer si pom aga s k-2 pomo žnim i polo žeji. }
var i, ma xPom: integer;
begin
if n>O then begin
Prestavi(izvor, Pomozni(1 , izvor, cilj), n-(k- 2) , k) ;
if n«k-2) then ma xPom := n else maxP om:=k-2;
for i:=2 to ma xPom do
write ln(, P restavi ploscico s po lozaja ' ,izvor ,' na polozaj
Pom ozni (i ,izvor ,cilj) , ' . ' ) :
writeln('Pres tav i ploscico s polozaja ',izvor ,' na polozaj ', cilj ,' . ' );
for i:=ma xPo m downto 2 do
writ eln('Prestavi ploscico s po lozaja ' ,Pomozni(i,izvor,cilj) ,
, na polozaj ' ,cilj,'. ');
P restavi(Pomozni(1, izvor, cilj) , cilj, n-(k-2), k):
end ;
en d ;
13
begin { glavn i program }
writ e('Vnesi stevilo polozajev : ') ; readln( k);
write('Vnesi st evilko zacetnega polo zaja: '): readl n(izvor);
writ e('Vnesi stevilko koncn ega pol ozaja: ' ) ; readl n(cilj) ;
write(,V nesi velikost stolpa : ' ): readln(n) ;
Prestavi(izvor, cilj, n, k) ;
end.
Položaje oštevilčimo s števili od 1 do k . Funkcija Pomozni( i, izvor,
cilj) vrne številko i-tega pomožnega položaja . Le je na primer izvor = 2,
cilj = 4, potem z indeksom itakole naslovimo ostale , to je pomožne, po-
ložaje:
položaji
Izvor
1 2
1
cilj
3 4
2
5
3
k -1 k
k- 3 ' k - 2
Spremenljivka ma x Pom v podprogramu Prestavi predstavlja največj i
indeks pomožnega položaja , ki ga bomo uporabil i. Le je ploščic manj kot je
vseh pomožnih položajev (n < k - 2), potem je max Pom = n, sicer pa je
ma xPom = k - 2.
Delovanje podprograma Prestavi lahko prikažemo na podoben način
kot v prejšnjem primeru.
32
§
I I
I I
I I
O
Prestaviti želimo stolp z n ploščicam i z izvora na cilj; klic
Prestavi(izvor ,cilj ,n ,k)
v glavnem programu .
I
I I
I .f==1J
I I I I
O 2 3 4
To naredimo takole : Najprej prestavi mo stolp z n - (k - 2) ploščicami na
prvi pomožni položaj ; klic Prestavi(izvor, Pomozni(1, izvor, cilj) ,
n- (k-2), k) v podprogramu. Na začetnem položaju ostane še k - 2 (oz iro-
ma n , če je n < k - 2) plošči c.
14
o
E3
I I
2 3 4
V drugem koraku na ostale pomožne položaje (teh je ravno k - 3)
razporedimo po eno ploščice z izvora ; zanka for i: =2 to maxPom do
writeln( 'Prestavi ploscico spolozaja ' , i z vor , ' na polozaj "
Pomozni( i , izvor, cilj) , ' . , ) v podprogramu . Na začetnem po ložaju
tako ostane le še ena ploščica , ciljni položaj pa je še vedno prost ..
o
f=1J
I !
2 3 4
Z izvora prestavimo največjo ploš čice na cilj; izpis writeln ( 'Prestavi
ploscico spolozaja ',izvor,' na polozaj ',cilj,'.') v podpro-
gramu .
r==:j II II
I 1 J I
O 2 3 4
Z ostalih pomožnih po ložajev v obratnem vrstnem redu prestavljamo
ploščice na cilj; zanka for i:=maxPom downto 2 do writeln('Prestavi
ploscico spolozaja' ,Pomozni(i, izvor ,cilj),' napolozaj' ,cilj,
, . ,) v pod programu.
§
I I
I I
o 2 3 4
Stolp s prvega pomožnega položaja prestavimo na cilj; klic Presta-
vi(Pomozni( 1, izvor, cilj), cilj, n-(k-2), k) v podprogramu.
Premik stolpa z n - (k - 2) ploščicam i zopet opravimo na enak način,
le da so izvor , cilj in pomožni po ložaj drugače razporejeni .
Pri vrednosti h k = 3, izvor = 1 in cilj = 3 je delovanje drugega
programa enako prvemu .
15
Preštejmo še število potez, ki jih potrebuje gornji program za rešitev pos-
plošene naloge hanojskega stolpa. Z nekaj sistematičnega dela, pri katerem
nam je računalnik v pomoč, sestavimo naslednjo tabelo, v katero vpišemo
število potez N( k, n) v odvisnosti od števila ploščic n in števila položajev k:
n\k 3 4 5 6
1 1 1 1 1
2 3 3 3 3
3 7 5 5 5
4 15 9 7 7
5 31 13 11 9
6 6321 15 13
7 12729 19 17
8 25545 2721
Iz tabele lahko uganemo tele formule, ki veljajo za poljuben n:
n n
N(3, n) = L 2;-1, N(4, n) = L2; div 2,
;=1 ;=1
n n
N(5, n) =L 2(i+1) div 3, N(6, n) =L 2(;+2) div 4 .
;=1 ;=1
Z natančnim pregledom programa lahko razberemo tudi splošno formulo,
ki velja za poljubna k in n:
n
N(k, n) =L 2(i+k-4)d;v (k-2)
;=1
= 2l+(n-1)d;v(k-2)(k _ 2 + (n -1) mod (k - 2)) - (2k - 5).
Le vstavimo k = 3, dobimo ravno 2n - 1.
Seveda se lahko vprašamo, ali je postopek optimalen glede števila potez ,
ali pa mogoče obstaja postopek , s katerim bi prestavili stolp z manjšim
številom potez . Žal odgovora ne poznam.
Za kanec pa 3c Iegenda, ki sem jo s l i i l  e hanojskem stolpu. Legcnda 
pravi, da jt v Hanoju tempelj, v katerem menihi prestavljajo stolp it 68 plo%c. 
KO bod0 stolp prwtavili, naj bi bilo konec svtta. Poskusitt octniti, kdaj naj bi 
do tega priflo. Koliko Easa pa bi potreboval izjcmno hiter razunalnik? Koliko 
potez na sckundo bi moral narediti, da bi prcstavil tak stolp v sto Ietih? 60 
to kdaj mdno? 
Ciril Pudir