Hanojski stolpi: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m →Rešitev z rekurzijo: tn |
dp+ |
||
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 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 h 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,
Vrstica 32:
Algoritem je moč lepo zapisati v različnih [[programski jezik|programskih jezikih]] kot so: [[Scheme (programski jezik)|Scheme]], [[Haskell]], [[SML]], [[programski jezik C|C]], [[programski jezik Java|Java]], [[Python (programski jezik)|Python]] ali [[PL/I]].
==== Java ====
Rešitev hanojskih stolpov rekurzivno v jeziku Java:
Vrstica 55:
</source>
==== Rešitev s poljubnega začetnega položaja ====
V C:
Vrstica 94:
</source>
=== Rešitev z iteracijo ===
==== Java ====
Rešitev hanojskih stolpov iterativno v jeziku Java:
Vrstica 153:
</source>
=== Nerekurzivna rešitev ===
Seznam premikov ploščic, ki jih da rekurzivni algoritem, kaže več značilnosti. Če štejemo premike od 1, je številka ploščice, ki jo je treba premakniti v potezi ''m'', enaka številu kolikokrat je ''m'' deljiv z 2. Zato se v vsaki lihi potezi prestavi najmanjša ploščica (označena z 1). Videti se tudi da, da se najmanjša ploščica premika prek stolpov f, t, r, f, t, r, itd. za liho višino stolpa in prek stolpov f, r, t, f, r, t, itd. za sodo višino stolpa. Ta ugotovitev da naslednji algoritem, ki je preprostejši za premislek od rekurzivnega.
Poteze si sledijo izmenoma:
* premik najmanjše ploščice na stolp, s katerega pred tem ni premaknjena.
* premik druge ploščice, kjer preostane le ena možnost.
Pri prvi potezi gre najmanjša ploščica na stolp t, če je h lih, in na stolp r, če je sod. Če je število ploščic sodo, bodo prve poteze:
{|
|
{| class="wikitable"
| 1. || 0: f → r
|-
| 2. || 1: f → t
|-
| 3. || 0: r → t
|-
| 4. || 2: f → r
|}
|
{| class="wikitable"
| 5. || 0: t → f
|-
| 6. || 1: t → r
|-
| 7. || 0: f → r
|-
| 8. || 3: f → t
|}
|
{| class="wikitable"
| 9. || 0: r → t
|-
| 10. || 1: r → f
|-
| 11. || 0: t → f
|-
| 12. || 2: r → t
|}
|
{| class="wikitable"
| 13. || 0: f → r
|-
| 14. || 1: f → t
|-
| 15. || 0: r → t
|-
| 16. || 4: f → r
|}
|
{|
| rowspan="3" | ...
|}
|}
Pri tem velja tudi:
* 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 h sod, so preostali tretji stolpi v zaporednih potezah: t, r, f, t, r, f, itd.
* če je h lih, so preostali tretji stolpi v zaporednih potezah: r, t, f, r, t, f, itd.
=== Dvojiške rešitve ===
Položaje ploščic se lahko določi tudi bolj neposredno iz [[dvojiški številski sistem|dvojiške]] (osnova 2) predstavitve številke poteze, kjer je začetno stanje #0 in vse številke 0, in končno stanje #2<sup>''n''</sup>−1 z vsemi številkami enakimi 1 z naslednjimi pravili:
* za vsako ploščico obstaja ena dvojiška števka ([[bit]]).
* skrajni levi bit predstavlja največjo ploščico. Vrednost 0 označuje, da je največja ploščica na začetnem stolpu, vrednost 1 pa kaže na to, da je ploščica na končnem stolpu.
* niz bitov se bere od leve proti desni, in za določtev položaja odgovarjajoče ploščice se lahko vzame katerikoli bit.
* bit z enako vrednostjo kot predhodni pomeni da je odgovarjajoča ploščica na predhodni ploščici na istem stolpu.
** zaporedje samih enic ali ničel pomeni, da so odgovarjajoče ploščice vse na istem stolpu.
* bit z različno vrednostjo od predhodnega pomeni, da je odgovarjajoča ploščica levo ali desno od predhodne. Ali je levo ali desno, določa pravilo:
** naj je začetni stolp na levi, končni pa na desni.
** pri tem velja tudi, da se desni stolp lahko nahaja »levo« od levega stolpa, in podobno za levi stolp.
* naj je n število večjih ploščic, ki so na istem stolpu kot od njih prva večja ploščica. Pri tem se prišteje 1, če je največja ploščica na levem stolpu. Če je n sod, je ploščica na levem stolpu, če pa je lih, se ploščica nahaja na desnem stolpu.
Za igro z osmimi ploščicami je na primer:
* poteza#
** največja ploščica je 0, zato je na levem (začetnem) stolpu.
** vse preostale ploščice so tudi 0, in so zato na največji ploščici. Zaradi tega so vse ploščice na začetnem stolpu.
* poteza#
** največja ploščica je 1, zato je na desnem (končnem) stolpu.
** tudi vse druge ploščice so 1, in so zato na njej. Zaradi tega so vse ploščice na končnem stolpu in igra je končana.
* poteza#
** največja ploščica je 1, zato je na desnem (končnem) stolpu.
** druga ploščica je tudi 1 in je na njej na desnem stolpu.
** tretja ploščica je 0, zato je na drugem stolpu. Ker je n lih, je na stolpu desno, oziroma na srednjem.
** četrta ploščica je 1, zato je na drugem stolpu od predhodne. Ker je n še vedno lih, je na stolpu desno, oziroma na desnem.
** tudi peta ploščica je 1 in je na predhodni ploščici na desnem stolpu.
** šesta ploščica je 0 in je zato na drugem stolpu. Ker je n sedaj sod, je na stolpu levo, oziroma na srednjem.
** sedma in osma ploščica sta tudi 0, tako da sta na šesti ploščici na srednjem stolpu.
''m''-to potezo je moč lepo najti iz dvojiške predstavitve ''m'' z [[bitna operacija|bitno operacijo]]. S skladnjo v C je ''m''-ta poteza s stolpa <code>(m&m-1)%3</code> na stolp <code>((m|m-1)+1)%3</code>, kjer se ploščice premikajo s stolpa 0 (f) na 1 (t) ali 2 (r), glede na to ali je njihovo število sodo ali liho. Številka ploščice, ki jo je treba premakniti, se lahko določi z vrednostjo kolikokrat je zaporedna številka poteze m deljiva z 2, oziroma s številom ničelnih bitov na desni, kjer je prva poteza 1, ploščice pa so označene zaporedoma naraščajoče 0, 1, 2, itd.
<source lang='C'>
int main(void) {
int m, n, p, t;
printf("\nStevilo ploscic:");
scanf("%d", &n);
for (m=1; m<(1<<n); m++) {
if (m%2) { /* zaporedna stevilka poteze ni deljiva z 2. */
p=0;
}
else { /* je deljiva - kolikokrat? */
t=m;
while (t%2 != 1) {
p++;
t/=2;
}
}
printf("\n%5d. %3d: %d na %d", m, p, (m&m-1)%3, ((m|m-1)+1)%3 );
}
}
</source>
== Opombe==
| |||