Algoritmizácia a programovanie - Slovne popísané algoritmy - Hanojské veže :)

Tlačiť

Logická hra Hanojská veža má jednoduché pravidlá. Hra začína postavením pyramídy z hracích kotúčov na jednu z troch drevených tyčiek. Úlohou hráča je presunúť celú pyramídu na inú tyčku, avšak pri dodržaní nasledovných pokynov:
· v jednom ťahu (na jedenkrát) je možné premiestniť iba jeden kotúč,
· väčší kotúč nesmie byť nikdy položený na menší.
Nájdite postup riešenia s najmenším možným počtom presunov pre 3, 4, 5, 6 a 7 kotúčov.

 

 

Ak chceme vežu premiestniť z jednej tyče na inú využitím najmenšieho možného počtu ťahov, je dôležité zvoliť si hneď na začiatku, ktorá z dvoch „prázdnych“ tyčí bude cieľovou. Druhá prázdna tyč nám poslúži ako tyč „odkladacia“. Ak máme zvolenú cieľovú a odkladaciu tyč, môžeme začať s presúvaním veže. Treba mať na pamäti, že väčší kotúč nikdy nesmieme položiť na menší. Keď začíname hrať, najväčší kotúč je celkom dole, na ňom  sú umiestnené ďalšie kotúče. Naším cieľom teda bude odstrániť z najväčšieho kotúča všetky ostatné kotúče tak, aby sme ho mohli premiestniť. Najväčší kotúč však možno premiestniť jedine vtedy, ak máme cieľovú tyč prázdnu, t.j. nespočíva na nej nijaký kotúč. Znamená to, že skôr než premiestnime najväčší kotúč, ostatné kotúče musia byť umiestnené na odkladacej tyči. Ako to dosiahnuť? Pokúsme sa o to najprv s počtom kotúčov 3. Predstavme si, že veža, ktorú máme premiestniť, je na začiatku hry umiestnená na prvej tyči zľava. Zvoľme si tretiu kotúč tyč zľava ako cieľovú a tyč v strede (t.j. druhú zľava) ako odkladaciu. Prvý kotúč, ktorý presúvame, je, samozrejme, najmenší. Uvedomme si, že dva menšie kotúče musíme (skôr ako presunieme najväčší kotúč) umiestniť na odkladaciu tyč. Aby sme neporušili pravidlá hry, na odkladacej tyči musia byť kotúče umiestnené takto: druhý najväčší kotúč dole, na ňom najmenší kotúč. Najrýchlejšie to dosiahneme, ak najmenší kotúč umiestnime najprv na tretiu tyč zľava, teda cieľovú. Potom na odkladaciu tyč presunieme druhý najväčší kotúč. Vzápätí naň môžeme položiť najmenší kotúč, ktorý dovtedy spočíval na cieľovej tyči. Ak tak urobíme, dva menšie kotúče máme umiestnené na odkladacej tyči a cieľovú tyč máme prázdnu. Presunieme na prázdnu cieľovú tyč najväčší kotúč. Teraz už naň stačí položiť len dva menšie kotúče. Najprv druhý najväčší kotúč, potom najmenší kotúč. Na druhom najväčšom kotúči (ktorý spočíva na odkladacej tyči) je však položený najmenší kotúč. Ak chceme druhý najväčší kotúč premiestniť, musíme ho „uvoľniť“, odstrániť z neho najmenší kotúč. Urobíme to tak, že najmenší kotúč preložíme na prvú tyč zľava, teda tú, na ktorej stála pôvodná veža (a ktorý je teraz úplne prázdny). Druhý najväčší kotúč je teraz „voľný“, možno ho presunúť. Položíme ho na najväčší kotúč na cieľovej tyči. Najmenší kotúč je voľný. Položíme ho na druhý najväčší kotúč na cieľovej tyči. Všetky tri kotúče sú na cieľovej tyči! Zvíťazili sme! Rovnako postupujeme aj pri väčšom počte kotúčov. Najprv treba „uvoľniť“ najväčší kotúč a zabezpečiť, aby bola cieľová tyč prázdna. Odkladacou je síce len jedna tyč, pamätajme však, že kotúč si môžeme (po logickej úvahe dospejeme k záveru, že nielen môžeme, ale musíme) v určitých situáciách načas „odložiť“ aj na cieľovú tyč (prípadne tyč, na ktorej spočívala pôvodná veža). Dôležité je nezabudnúť, že cieľová tyč musí byť prázdna len v prípade, ak sa na ňu chystáme premiestniť najväčší kotúč.

 

Riešenie úlohy pre 3 kotúče

Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.

Spolu bolo vykonaných 7 (= 23-1)presunutí.

 

Program Hanojské veže

 

Riešenie úlohy pre 4 kotúče

Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.

Spolu bolo vykonaných 15 (= 24-1) presunutí.

 

Riešenie úlohy pre 5 kotúčov

Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.

Spolu bolo vykonaných 31 (= 25-1) presunutí.

 

Riešenie úlohy pre 6 kotúčov

Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 3.

Spolu bolo vykonaných 63 (= 26-1) presunutí.

 

Riešenie úlohy pre 7 kotúčov

Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 3 na tyč 1.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 1 na tyč 2.
Presuň kotúč z tyče 3 na tyč 2.
Presuň kotúč z tyče 1 na tyč 3.
Presuň kotúč z tyče 2 na tyč 1.
Presuň kotúč z tyče 2 na tyč 3.
Presuň kotúč z tyče 1 na tyč 3.

Spolu bolo vykonaných 127 (= 27-1) presunutí.

Hodnotenie užitočnosti článku:


    EP je spat Prehlad Fyzika Prehlad Informatika Treti pilier Fotograf_krojov On-line kurzy Ako sa učiť a ako učiť Dejiny sveta Dejiny Slovenska

     

    O VŠETKÝCH KURZOCH 

     

    · Simulácie z fyziky 
    · O Slovensku po slovensky 
    · Slovenské kroje
    · Kurz národopisu
    · Diela maliarov
    · Kontrolné otázky, Domáce úlohy, E-testy - Priemysel
    · Odborné obrázkové slovníky
    · Poradňa žiadaného učiteľa
    · Rýchlokurz Angličtiny
    . Rozprávky (v mp3)
    · PREHĽADY (PRIBUDLO, ČO JE NOVÉ?)
    Seriály:
    · História sveta (1÷6)
    · História Slovenska (1÷5)
    · História módy (1÷5).

                                       
    Členstvo na portáli
    Mám účet a chcem sa prihlásiť Prihlásiť sa
    Nemám účet, ale chcel by som ho získať Registrovať sa
    Poznámka pre autora

    Ak ste na stránke našli chybu, dajte nám vedieť

    Newsletter

    Nenechajte si ujsť žiadny nový článok

    @

    Copyright © 2013-2021 Wesline, s.r.o. Všetky práva vyhradené. Mapa stránky ako tabuľka | Kurzy | Prehľady