Hanojski stolpi: Razlika med redakcijama

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_''3'']]). Č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žnomož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 premi 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 h ploščic z začetnega stolpa f na končni stolp t in pomožni stolp r so: