Hanojski stolpi: Razlika med redakcijama

dodani 104 zlogi ,  pred 13 leti
m
dp+
(+)
m (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 edinaenolič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>.
 
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]].