Hanoiko Dorreak

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu
Hanoiko dorreak

Hanoiko Dorreak hiru hagatxo bertikaldun eta jokoaren konplexutasuna determinatzen duten disko kopuru indeterminatu 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.

Kondaira[aldatu | aldatu iturburu kodea]

Benareseko tenplu batean munduaren zentroa seinalatzen zuen kupula bat zegoen. 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 handiagoa duen 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 segundoko mugimendu bat egingo baluke, 64 diskoak 585 milioi urte barru egongo lirateke hirugarrengo hagatxoan.

Hanoiko Dorreen erreza da askatzen, baina egin beharreko pauso kopurua esponentzialki igotzen da diskoen kopuruak gora egiten duen bezala.

Problema hau askotan programazioaren eremuan planteatu ohi izan da, gehienbat errekurtsibitatea azaltzeko.

Ebazpena[aldatu | aldatu iturburu kodea]

Oharra: Atal honek istorio osoa edo amaiera argitzen du.

Hiru diskodun dorreen ebazpena. Tower of Hanoi.gif

Lau diskodun dorreen ebazpena. Tower of Hanoi 4.gif

Commonsen badira fitxategi gehiago, gai hau dutenak: Hanoiko Dorreak Aldatu lotura Wikidatan