Hanojski stolpi: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
pravopis |
|||
Vrstica 23:
=== 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 ([[grupa simetrij]] 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 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 [[naravno število|naravnimi števili]] štejemo od 0. Tako je ploščica 0 najmanjša, ploščica h-1 pa največja. Poteze
* 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,
Vrstica 165:
* premik druge ploščice, kjer preostane le ena možnost.
Pri prvi potezi gre najmanjša ploščica na stolp t, če je
{|
|
Vrstica 215:
* 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
* če je
=== Dvojiške rešitve ===
| |||