Zadání:

Vytvořte program pro řešení úlohy Hanojských věží

Mezi klasické matematické problémy patří problém Hanojských věží: stará vietnamská hra, k níž se váže legenda. Při stvoření světa bylo na jednu ze tří diamantových jehel Velkého chrámu v Benaresu umístěno 64 disků. Od té doby kněží tyto disky přerovnávají na cílovou jehlu, přičemž

• v daném okamžiku se přenáší jen jeden disk
• nikdy nesmí být umístěn větší disk na menším
Až se kněžím podaří disky přenést, chrám se zboří a svět s třeskem zmizí. Protože disků je 64, dává to naději, že to tak hned nebude.
Máme k dispozici tři jehly (A,B,C) a určitý počet disků s různým průměrem a s otvorem uprostřed, které se mohou na jehly nasazovat. Na počátku jsou všechny disky navlečeny na jedné z jehel (A) tak, že tvoří věž, směrem vzhůru se zužující. Úkolem je přemístit disky na jehlu (C) s použitím jehly (B), přičemž musíme dodržovat tato pravidla:
• v každém kroku můžeme přemístit pouze jeden disk, a to vždy z jehly na jehlu (disky nelze odkládat mimo jehly)
• není možné položit větší disk na menší
Pro tuto úlohu existuje i nerekursivní postup řešení. Ale rekursivní postup, založený na rozkladu úlohy na úlohy menší (s nižšími hodnotami parametrů) je zde velmi názorný a jednoduchý.

Rekursivní řešení založíme na tom, že problém s N disky bude řešen, když:

• přeneseme N - 1 horních disků z A na B s použitím C jako odkládací jehly
• pak přeneseme největší disk zbylý na A, na jehlu C
• a konečně přerovnáme věž s N - 1 disky z B na C s použitím A jako odkládací jehly

{Program pro generovani tahu v uloze o hanojskych vezich.
 Zadava se pocet disku. Presun probiha z veze cislo 1 na vez cislo 3
 s uzitim pomocne veze cislo 2.}


uses crt;


const Koncovky: array[1..5] of string[1]=('','y','y','y','u');


var Odkud,         {Cislo puvodni veze}
    Kam,           {Cislo konecne veze}
    Pomocna,       {Cislo pomocne veze}
    Pocet:byte;    {Pocet disku}
    Koncovka:string[1];


procedure Tah(Odkud,Kam:byte);
{Procedura vypise, odkud budeme tahnout a kam}
begin {Tah}
  writeln('Tah z ',Odkud,' na ',Kam)
end; {Tah}


Procedure PosunVez(Vyska:byte;var Odkud,Kam,Pomocna:byte);
{Rekurzivni procedura pro reseni ulohy hanojskych vezi}
begin {PosunVez}
  if Vyska>0 then begin
    PosunVez(Vyska-1,Odkud,Pomocna,Kam);
    Tah(Odkud,Kam);
    PosunVez(Vyska-1,Pomocna,Kam,Odkud);
  end; {if}
end; {PosunVez}


begin
  clrscr;
  Odkud:=1;
  Kam:=3;
  Pomocna:=2;
  writeln('Hanojske veze');
  writeln;
  repeat
    {$I-}   {Vypnuti konroly V/V operaci}
    repeat
      write('Zadejte pocet disku v intervalu <0,4> (0 ukonci program): ');
      readln(Pocet);
      Koncovka:=Koncovky[Pocet];
    until (IOResult=0)and(Pocet in [0..4]);
    {$I+}   {Zapnuti konroly V/V operaci}
    if Pocet<>0 then begin
      clrscr;
      writeln('HANOJSKE VEZE - tahy pro ',Pocet,' disk',Koncovka);
      writeln('____________________________________');
      PosunVez(Pocet,Odkud,Kam,Pomocna);
      writeln;
    end; {if}
  until Pocet=0;
end.