Hanojski stolpi: Razlika med redakcijama

Brez spremembe v velikosti ,  pred 4 leti
m
Redakcija 4622314 uporabnika SportiBot (pogovor) razveljavljena
(pravopis)
m (Redakcija 4622314 uporabnika SportiBot (pogovor) razveljavljena)
=== 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 kh 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,
* premik druge ploščice, kjer preostane le ena možnost.
 
Pri prvi potezi gre najmanjša ploščica na stolp t, če je kh lih, in na stolp r, če je sod. Če je število ploščic sodo, bodo prve poteze:
{|
|
* 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 kh sod, so preostali tretji stolpi v zaporednih potezah: t, r, f, t, r, f, itd.
* če je kh lih, so preostali tretji stolpi v zaporednih potezah: r, t, f, r, t, f, itd.
 
=== Dvojiške rešitve ===
153.767

urejanj