Hanoiko Dorreak
Wikipedia(e)tik
Hanoiko Dorreak hiru hagatxo bertikaldun eta jokoaren komplexutasuna determinatzen duten disko kopuru inderterminatu bat duen joko bat da. Ez daude bi disko berdinik, handitik txikira jartzen dira lehen hagatxoan eta ezin da inoiz disko handi bat txikiago baten gainean jarri. Jokoa disko guztiak lehen hagatxotik hirugarrenera handitik txikira pasatzean datza.
Izena Hanoi hiritik datorkio.
[aldatu] Kondaira
Benareseko tenplu batean munduaren zentrua seinalatzen zuen kupula bat aurkitzen zen. Bertan diamantezko hiru orratz zituen erretilu bat zegoen. Goiz euritsu batean, erregeak urrezko 64 disko jartzeko agindu zuen, neurriaren arabera ordenatuta, handiena erretiluaren oinarrian eta txikiena gainontzeko disko guztien gainean.
Ondoren, tenpluko apaizek diskoak orratzetan zehar mugitzen saiatu ziren, eman zitzaizkien arauei jarraituz: "Txanda duen apaizak disko bat mugi dezake bakarrik, eta ezin du diametro handiagodun disko bat txikiagoa duen beste baten gainean jarri". Beste kondaira baten arabera, Jainkoak sortu zuen jokoa eta apaizek askatzea lortzen dutenean, mundua amaitu egingo da.
Jokoa askatzeko mugimendu kopuru minimoa 264-1 da. Apaizek segunduko mugimendu bat egingo baluke, 64 diskoak 585 milioi urte barru egongo lirakete hirugarrengo hagatxoan.
Hanoiko Dorreen erreza da askatzen, baina egin beharreko pausu kopurua exponentzialki igotzen da diskoen kopuruak gora egiten duen bezala.
Problema hau askotan programazioaren eremuan planteatu ohi izan da, gehienbat errekurtsibitatea azaltzeko.
[aldatu] Ebazpena
| Oharra: Atal honek argumentua edo amaiera argitzen du. |
Hiru diskodun dorreen ebazpena. 
Lau diskodun dorreen ebazpena. 
