Hanojski stolpi: Razlika med redakcijama

dodanih 2.172 zlogov ,  pred 13 leti
+
(dp+)
(+)
* 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, imenovan direktna metoda<ref name="Klavzar" />, 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č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>. [[Zaporedje]] premikov ploščic v optimalni rešitvi problema z ''n'' ploščicami je enako prvim <math>2^{h} - 1</math> členom zaporedja {{OEIS|id=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 <math>x_{1}, x_{2}, ..., x_{n} </math> 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. <ref>Klavžar, str. 145.</ref> 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 [[programski jezik|programskih jezikih]] kot so: [[Scheme (programski jezik)|Scheme]], [[Haskell]], [[SML]], [[programski jezik C|C]], [[programski jezik Java|Java]], [[Python (programski jezik)|Python]] ali [[PL/I]].
}
</source>
 
=== Rešitev z Grayjevo kodo ===
 
Dvojiški sestav [[Grayjeva koda|Grayjevih kod]] da drugo rešitev problema. V Grayjevem sistemu so števila predstavljena dvojiško vendar ne s [[številski sistem|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.
 
== Opombe==