Hanojski stolpi: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m →Izvor igre: dp |
m →Rešitev: tn |
||
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 ([[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
* 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,
|