Back

ⓘ Kulla e Hanoit eshte nje loje matematikore ose nje engime. Ajo perbehet nga tri shufra, dhe nje numer disqesh te madhesive te ndryshme te cilat mund te zhvendos ..




Kulla e Hanoit
                                     

ⓘ Kulla e Hanoit

Kulla e Hanoit eshte nje loje matematikore ose nje engime. Ajo perbehet nga tri shufra, dhe nje numer disqesh te madhesive te ndryshme te cilat mund te zhvendosen nga nje shufer ne tjetren. Fillimisht ato jane te vendosura ne shtyllen e pare, te renditura nga me e madhja deri te me e vogla ne krye, duke marre nje forme konike.

Objektivi i lojes eshte te levizet i tere pirgu ne nje shtylle tjeter, duke percjell disa rregulla te thjeshta:

  • Asnje disk nuk mund te vendoset mbi nje disk me te vogel.
  • Secila levizje duhet te marre nje disk qe ndodhet ne maje dhe ta vendos mbi nje pirg tjeter p.sh. nje disk mund te levizet nese eshte me i larti disk ne pirg.
  • Vetem nje disk mund te levizet ne nje kohe.

Me tri disqe, engima mund te zgjidhet ne shtate levizje. Numri minimal i levizjeve qe duhen per te zgjidhur nje Kulle te Hanoit eshte 2 n - 1, ku n eshte numri i disqeve.

                                     

1. Origjina

Kjo loje u zbulua nga matematikani francez Édouard Lucas ne vitin 1883. Ekziston nje rrefim mbi nje tempull indian ne Kashi Vishwanath i cili permban nje dhome te madhe me tri mesazhe te fshehura kohore ne te, te rrethuara nga 64 disqe te arta. Prifterinjte e Brahminit, duke vepruar sipas urdherave te profecise antike, i kane levizur keto disqe, ne koordinim me rregullat e pandryshueshme te Brahmas, qe nga ajo kohe. Engima eshte e njohur edhe me emrin Kulla e Brahmas. Sipas legjende, kur te kryhet levizja e fundit, bota do te marre fund. Nuk eshte e qarte nese Lucasi e shpiku kete legjende apo u inspirua nga ajo.

Nese legjenda do te ishte e vertete, dhe nese prifterinjte jane te gjendje te levizin disqet ne shkalle prej 1 per sekond, duke perdorur numrin me te vogel te levizjeve, do te duheshin 2 64 −1 sekonda ose 585 miliarde vite ose 18.446.744.073.709.551.615 levizje per tu perfunduar, qe jane rreth 27 here mosha aktuale e diellit.

Ekzistojne disa variante te kesaj legjende. Per shembull, ne disa tregime, tempulli eshte nje manastir dhe levizet nga murgjit. Tempulli ose manastiri mund te jete ne vende te ndryshme te botes - duke perfshire Hanoin, Vietnamin, dhe mund te lidhet me cilindo religjion. Ne disa versione, perfshihen elemente te tjera, si fakti se kulla eshte krijuar ne fillim te botes, ose se prifterinjte ose murgjit mund te bejne vetem nje levizje ne dite.

                                     

2. Zgjidhja

Engima mund te luhet me çfaredo numri te disqeve, megjithese shumica e versioneve jane me shtate ose nente. Numri minimal i levizjeve per zgjidhjen e engimes eshte 2 n - 1, ku n eshte numri i disqeve.

                                     

2.1. Zgjidhja Zgjidhja perseritese

Nje zgjidhje e thjeshte per engimen ne version te thjeshte: bej levizje ne mes te diskut me te vogel dhe atij jo me te vogel. Kur levizet disku me i vogel, zhvendose ne pozicionin e ardhshem ne drejtim te njejte djathtas nese numri fillestar i disqeve eshte tek, majtas nese eshte çift. Nese nuk ka pozicion kulle ne drejtimin e zgjedhur, levize diskun ne fundin e kundert, por pastaj vazhdo te levizesh ne drejtimin korrekt. Per shembull, ju keni filluar me tri disqe, ju keni levizur diskun me te vogel ne fund, dhe pastaj keni vazhduar ne drejtimin majtas. Kur vie radha per levizje te diskut jo me te vogel, ekziston vetem nje levizje e lejuar. Kjo do te perfundoje lojen ne numer te vogel levizjesh.

                                     

2.2. Zgjidhja Paraqitje me e thjeshte e zgjidhjes perseritese

Percjell hapat ne raste te caktuar, per levizja ne mes te diskut me te vogel dhe atij njehere me te madh se ai, si me poshte:

Per numer tek te disqeve:

  • beje levizjen e lejuar ne mes te kujave A dhe C
  • perseriti hapat e pare derisa te perfundohet
  • beje levizjen e lejuar ne mes te kujave A dhe B
  • beje levizjen e lejuar ne mes te kunjave B dhe C

Per numer çift te disqeve:

  • beje levizjen e lejuar ne mes te kujave A dhe C
  • beje levizjen e lejuar ne mes te kujave C dhe D
  • beje levizjen e lejuar ne mes te kujave A dhe B
  • perseriti hapat e pare derisa te perfundohet

Ne secilin rast jane kryer 2 n -1 levizje.

                                     

3. Paraqitja grafike

Loja mund te paraqitet nga nje graf i padrejtuar, ku nyjat paraqesin grupimet e disqeve dhe brinjet paraqesin levizjet. Per nje disk, grafiku eshte trekendesh:

Grafiku per dy disqe perbehet nga tre trekendesha te vendosur ne nje trekendesh me te madh:

Nyjet ne kulmet me te skajshme te trekendeshit paraqesin grupimet te gjithe disqeve ne te njejten kunj.

Per h+1 disqe, merret grafiku i h disqeve dhe zevendesohet secili trekendesh i vogel me graf per dy disqe.

Per tri disqe grafiku eshte ky:

  • quajme kunjat a, b dhe c
  • renditim pozitat e disqeve nga majtas djathtas ne renditje ashtu qe madhesia e tyre rritet

Faqet e trekendeshit me te skajshem paraqesin rruget me te shkurtra te levizjes se nje kulle nga nje kunj ne tjetren. Brinja ne mes te fuqes se trekendeshit me te madh paraqet nje levizje te diskut me te madh. Brinja ne mes te faqeve te secilit trekendesh te ardhshem paraqet nje levizje te secilit disk me te vogel. Faqet e trekendeshtave te vegjel paraqesin levizjet e disqeve me te vogla.

Rruga me e gjate jo-perseritese per tri disqe mund te vizualizohet duke larguar brinjet e paperdorura:

Qarku Hamiltonian per tri disqe eshte:

Grafiku qartazi tregon se:

  • Ne mes te seciles pale te grupimeve arbitrare te disqeve ekzistojne nje ose dy rruge te ndryshme te gjata qe nuk kalojne neper vetvete.
  • N 1 = 2
  • Nga secili grupim arbitrar i disqeve, ekzisojne nje ose dy rruge te ndryshme te gjata qe nuk kalojne neper vetvete per te levizur te gjitha disqet ne tri kunja.
  • Per secilin grupim arbitrar te disqeve, ekziston saktesisht nje rruge e shkurter per te levizur gjithe disqet ne njeren nga tri shtyllat.
  • Per shembull: N 8 ≈ 1.5456×10 795
  • N h +1 = N h 2 + N h 3.
  • Le te jete N h numr i rrugeve qe nuk kalojne neper vetveve per levizjen e kulles prej h-disqesh nga nje kunj ne tjetren. Atehere
  • Ne mes te seciles pale te grupimeve arbitrare te disqeve ekzistojne nje ose dy rruge te shkurtra.


                                     

4. Aplikimi

Kulla e Hanoit perdoret shpesh ne kerkime psikologjike ne zgjidhjen e problemeve. Ekziston nje variant i kesaj detyre e quajtur Kulla e Londres per diagnoza neuropsikologjike dhe tretmane te funksioneve ekzekutive.

Kulla e Hanoit eshte e famshme per mesimin e algoritmave rekursive per studentet qe fillojne te mesojne programimin.

Kulla e Hanoit u perdor po ashtu si test nga neuropsikologet ne perpjekje per te vleresuar deficitet e nje pjeseje te trurit.

Ne vitin 2010, hulumtuesit publikuan rezultatet e nje eksperimenti ku gjeten se specia e milingonave Linepithema humile mund ta zgjidhte ne menyre te suksesshme versionin 3-disqsh te Kulles se Hanoit.

                                     

5. Lidhje te jashtme

  • Tower of Hanoi: online game
  • Tower of Hanoi at DMOZ
  • Weisstein, Eric W., "Tower of Hanoi", MathWorld.
  • Tower of Hanoi Variant Game: Pyramid Mover
  • Tower of Hanoi: Code in Lisp

Users also searched:

...
...
...