Hanojski stolpi: Razlika med redakcijama

dodanih 4.154 zlogov ,  pred 13 leti
+
m (dp)
(+)
'''Hanojski stolpi''' oziroma '''problem Hanojskega stolpa''' je [[igra]] ali [[uganka]] s področja [[razvedrilna matematika|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 [[premer]]a.
[[Slika:Tower_of_Hanoi.jpeg|thumb|right|320px|Pribor za igro hanojskih stolpov z osmimi ploščicami]]
[[Slika:Tower_of_Hanoi_4.gif|thumb|right|320px|Rešitev za 4 ploščice]]
 
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žec|stožca]]. Cilj igre je premakniti celotni kupček ploščploščic na drug kupček ploščploščic (končni stolp) z najmanjšim možnim številom premikovpotez, 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 ==
 
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]].<ref name="Klavzar">Klavžar.</ref> Obstaja legenda o [[Indija|indijskem]] templju, ki ima veliko sobo s tremi obrabljenimi drogovi, ki jih obkroža 64 [[zlato|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 [[rekurzija|rekurzivna]] in je zato znana tudi kot šolski primer pri [[računalnik|računalniškem]] [[programiranje|programiranju]].
 
Če bi bila legenda resnična in če bi lahko duhovniki premikali ploščice s hitrostjo 1 na [[sekunda|sekundo]], bi bil za najmanjše možno število premikovpotez ploščic potreben [[čas]] 2<sup>64</sup>−1 sekund, oziroma približno 584.542 [[milijarda|milijard]] [[leto|let]]. [[Vesolje]] je trenutno staro okrog [[starost Vesolja|13,7 milijard let]].
 
Obstaja več različic legende. Po nekaterih je tempelj samostan, duhovniki pa so manihi. Tempelj ali samostan se lahko nahaja v različnih delih sveta, med njimi tudi v [[Hanoj]]u v [[Vietnam]]u, in je lahko povezan s katerikoli 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 premikpotezo 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 z rekurzijo ===
 
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 [[simetrija|simetričen]] za [[permutacija|permutacije]] imen stolpov ([[simetrična grupa|simetrična grupa S<sub>''3''</sub>]]). Č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 h1, moramo največjo ploščico enkrat v zaporedju potez premakniti s stolpa f na drug stolp, po možno 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 premi 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 [[naravno število|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čna indukcija|matematične indukcije]] se lahko preprosto pokaže, da zgornji postopek vsebuje najmanjše število možnih potez, in da je to tudi edina rešitev s tem najmanjšim številom potez. Z [[rekurenčna enačba|rekurenčno enačbo]] se lahko izračuna natančno število potez rešitve: <math>2^{h} - 1</math>. Pri tem koraka 1 in 3 potrebujeta <math>T_{h-1}</math> potez, korak 2 pa eno, kar da <math>T_{h} = 2T_{h-1} + 1</math>.
 
Algoritem je moč lepo zapisati v različnih [[programski jezik|programskih jezikih]] kot so: [[Scheme]], [[Haskell]], [[SML]], [[programski jezik C|C]], [[programski jezik Java|Java]], [[Python (programski jezik)|Python]] ali [[PL/I]].
 
=== Java ===
}
}
</source>
 
=== Rešitev s poljubnega začetnega položaja ===
 
V C:
 
<source lang='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);
}
}
</source>
 
V [[programski jezik paskal|paskalu]]:
<source lang="pascal">
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;
</source>
 
== Nerekurzivna rešitev ==
 
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 premikupotezi ''m'', enaka številu kolikokrat je ''m'' deljiv z 2. Zato se v vsakemvsaki lihemlihi premikupotezi 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 lihliho stolpvišino stolpa in prek stolpov f, r, t, f, r, t, itd. za sodsodo višino stolpstolpa. Ta ugotovitev da naslednji algoritem, ki je preprostejši za premislek od rekurzivnega.
 
== Opombe==
{{refsez}}
 
== Viri ==
 
* {{navedi revijo |author={{aut|[[Sandi Klavžar|Klavžar, Sandi]]}} |year=2007 |title=Požrešno zaporedje brez ponavljanj in problem Hanojskega stolpa |journal=[[Obzornik za matematiko in fiziko|Obzornik mat, fiz.]] |volume=54 |issue=5 |pages=str. 145-150.}}
 
{{math-stub}}