On 7 Aug 98 at 2:03, Nagy Gabor  > wrote:
> A masik jatekpalyazat:
> Van meg egy logikai jatek, a Hanoi torony. Alapesetben 3 ruddal es 10
> koronggal. Ezt ugye 2^10-1 lepesben lehet atrakni. De mi van, ha nem 3,
> hanem 4,5..n, es n-nel tobb korong van? Ezt hogyan szamolod ki?
Egyfele megoldas:
Tegyuk fel, hogy n korong van, es 2+m rud (vagyis van egy kezdo rud,
cel rud, meg m darab segedrud). Ekkor csinalhatjuk ugy (rekurziv
megkozelites), hogy a felso n-m korongot atpakoljuk az egyik
segedrudra, a maradek m-bol pedig m-1-et egyesevel az m-1 darab ures
segedrudra, a legalsot meg a helyere, aztan az m-1-et a tetejere,
vegul az n-m magas oszlopot rekurzivan szinten atrakjuk a helyere.
Ez eddig egyszeru, altalanositottam az eredeti Hanoi megoldasat,
aholis m=3D1 volt. (Az indukcios felteteleket nem irtam most le, azt
hiszem, nem kell veluk szaporitanom a betuket...)
Ahhoz, hogy ez a lepesek szamaban mit jelent, fogalmazzuk kicsit at a
megoldast: Vegulis a fenti rekurzio soran azt fogjuk csinalni, hogy
egy adagkent kezelunk m darab egymas alatti korongot. Tehat olyan,
mintha n/m darab vastag korongunk lenne az eredeti Hanoi
felallassal, tehat 3 ruddal. A tobbi (m-1 darab) segedrudat pedig
arra hasznaljuk, hogy a vastag korong logikailag egyszeri mozgatasat
vegrehajtsuk fizikai mozgatassal: a mozgatando m korong folso m-1
tagjat szetszorjuk a rudakra, aztan atrakjuk a helyere az also
m-ediket, majd a tetejere a szetszort korongokat. Igy egy logikai
lepes 2*m-1 fizikai mozgatast jelent.
Ezek utan mar konnyen belathato, hogy egy ilyen m+2 rudas Hanoi
megoldasa (2*m-1)*(2^(n/m)-1) lepest vesz igenybe (ezzel az
algoritmussal). Persze csak akkor, ha n oszthato m-mel :)
4 rud eseteben (m=3D2) pl. erre egyszerusodik: 3*2^(n/2)-3
(3 rud eseten (m=3D1) termeszetesen 2^n-1 -re egyszerusodik)
Persze ha m >=3D n, akkor nem kell semmi rekurzio, 2*n-1 lepes eleg.
Az a gyanum, a fenti algoritmusnal van jobb megoldas is. Abbol
gondolom, hogy az m-1 darab segedrud igy alig van kihasznalva, max 1
korong van allandoan rajta, sose tobb. Probaltam kigondolni olyan
algoritmust is, ami jobban kihasznalja a segedrudakat azzal, hogy
tobb korongot is rarak, ki is jott egy 'megoldas', ami valami
2^logaritmikus lepesszamot adott, ami 4 rud esetere (m=3D2) egy
egyszeru n^2-es nagysagrendu lepesszamot hozott, aztan rajottem,
hogy rossz az egesz, mert a mozgatasok kozben kerulhetett nagyobb
korong kisebb tetejere :(
Szoval en is varom azok megoldasat, akik kitartobbak nalam :)
István
-- Istvan Marosi -- http://www.sch.bme.hu/~marosi --
-- Recosoft Ltd. -- mailto: --
|
