====== Hanojské věže ======

http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe

  * Máme N disků na první věži
  * V jednotlivých krocích přenášíme jeden disk z vrcholu některé věže na vrchol jiné věže
  * Nesmíme položit větší disk na menší
  * Cílem je přemístit všechny disky na třetí věž

  * Velikost disků: 1, 2, ... N
  * Levou věž označíme **A**, prostřední **B**, pravou **C**

===== Datové struktury ====

Datová struktura **Vez** obsahuje

  * výšku věže **v** = počet disků, v = 0 ... prázdná věž, v = N ... zcela zaplněná 
  * pole **p** obsahující velikosti jednotlivých disků
  * **p [0]** je dole
  * **p [v-1]** je vrchol věže (pokud **v** není nulové)

Globální proměnné **A**, **B**, **C** typu **Vez**.

<code C++>
const int N = 5; // pocet disku

struct Vez
{
    int v;      // vyska veze
    int p [N];  // velikosti disku, p[0] je dole, p[v-1] je vrchol
};

Vez A, B, C;
</code>

===== Prázdné věže =====

Volání funkce **nuluj (B)** a **nuluj (C)** nastaví nulovou výšku věží. \\
Pro přehlednější ladění vynulujeme i celé pole **p**, ale pro běh programu to není nezbytné.

Parametr typu **X** typu **Vez** předáváme odkazem (**&**), neboť chceme změnit původní proměnné **B** a **C**.

<code C++>
void nuluj (Vez & X)
{
   X.v = 0; // nulova vyska

   for (int i = 0; i<N; i++)
        X.p [i] = 0; // pro ladeni - vse vynulujeme
}
</code>

===== Naplnění levé věže =====

Funkce **init (A)** naplní věž N disky.

Nastavíme výšku **X.v** na hodnotu *N*. \\
Pole **X.p** naplníme hodnotami N, N-1, ..., 2, 1. \\
Spodní disk velikosti N uložíme do **X.p[0]**. \\
Na vrchol dáme disk velikosti 1, tj. nastavíme **X.p[N-1]** na jedničku.

<code C++>
void init (Vez & X)
{
    X.v = N; // N disku
    for (int i = 0; i<N; i++)
        X.p [i] = N-i; // dole p[0] = N, ..., nahore p[N-1] = 1
}
</code>


===== Zobrazení =====

Funkce **zobraz** vytiskne jednu věž. \\
//Parametr zde nemusí být předáván odkazem (**&**), ale je zbytečné vytvářet kopii celé datové struktury.//

<code C++>
void zobraz (Vez & X)
{
    for (int i = 0; i < X.v; i++)
        cout << X.p[i];
    for (int i = X.v; i <= N; i++)
        cout << ' '; // dopln mezerami
}
</code>

Funkce **tiskni** zobrazí tři věže oddělené dvojtečkami.

<code C++>
void tiskni (Vez & X, Vez & Y, Vez & Z)
{
    zobraz (X);
    cout << " : ";
    zobraz (Y);
    cout << " : ";
    zobraz (Z);
    cout << endl;
}
</code>

Takto by měl vypadat výstup celého programu. 
  * Disk 1 dáme na pravou věž
  * Disk 2 na prostřední věž
  * Disk 1 z pravé věže na prosřední

<code>
54321  :        :       
5432   :        : 1     
543    : 2      : 1     
543    : 21     :       
54     : 21     : 3     
541    : 2      : 3     
541    :        : 32    
54     :        : 321   
5      : 4      : 321   

...

3      : 2      : 541   
3      : 21     : 54    
       : 21     : 543   
1      : 2      : 543   
1      :        : 5432  
       :        : 54321 
</code>

===== Přenos jednoho disku =====

Funkce **krok** přenese jeden disk z vrcholu věže **X** na vrchol věže **Y**.

  * Do proměnné **h** uložíme disk z vrcholu věže **X**
  * Snížíme věž **X**
  * Zvýšíme věž **Y**
  * Na vrchol **Y** přidáme disk **h** 

<code C++>
void krok (Vez & X, Vez & Y) // presun disku z veze X na nez Y
{
    int h;
    h = X.p [X.v-1]; // cislo disku z vrcholu veze X
    X.p [X.v-1] = 0; // pro ladeni - vynulujeme
    X.v = X.v - 1;  // zmensime vysku veze X

    Y.v = Y.v + 1; // zvysime vez Y
    Y.p [Y.v-1] = h; // na vrchol pridame disk h
}
</code>

Nebo totéž s kontrolami zda **X** není prázdná, \\
**Y** není přeplněná, \\
a zda neklademe větší disk na menší.

<code C++>
void krok (Vez & X, Vez & Y) // presun disku z veze X na nez Y
{
    int h;
    assert (X.v > 0); // zkontroluj zda je vez neprazdna

    h = X.p [X.v-1]; // cislo disku z vrcholu veze X
    X.p [X.v-1] = 0; // pro ladeni - vynulujeme
    X.v = X.v - 1;  // zmensime vysku veze X

    assert (Y.v < N); // zkontroluj zda vez neni prilis vysoka
    if (Y.v > 0)
    {
        assert (h < Y.p [Y.v-1]); // zda h je mensi nez soucasny vrchol
    }

    Y.v = Y.v + 1; // zvysime vez Y
    Y.p [Y.v-1] = h; // na vrchol pridame disk h
}
</code>




===== Přenos několika disků =====

Funkce **hraj** přenese **k** disků. \\
Věže předáme odkazem jako parametry **X**, **Y**, a **Z**. \\
Přesouvat budeme z věže **X**, **Y** bude pomocná věž na odkládání disků, **Z** je cílová věž.

Pokud **k** je větší než 1, rekurzivně zavoláme stejnou funkci **hraj** \\
pro přenos **k** disků z věže **X** na původně pomocnou věž **Y**, \\
pro tento přenos bude jako pomocná věž použita původně cílová věž **Z**.

<code C++>
void hraj (Vez & X, Vez & Y, Vez & Z, int k)
</code>

<code C++>
   if (k > 1) 
   {
      hraj (X, Z, Y, k-1);
   }
</code>

Např. pro N=10, pokud X byla v počátečním stavu, Y a Z prázdné.

{{zalg:veze-start.png?640}}

Pro k=6, přeneseme 5 disků z X do Y. 

{{zalg:veze-zaciname.png?640}}

Potom funkcí **krok** přeneseme jeden disk z **X** na cílovou věž **Z**

<code C++>
    krok (X, Z); // 1 disk, X --> Z
</code>

{{zalg:veze-rozehrano.png?640}}

Nakonec přeneseme **k-1** disků z **Y** na **Z**

<code C++>
    if (k > 1) 
        hraj (Y, X, Z, k-1);
</code>

{{zalg:veze-preneseno.png?640}}

<code C++>
void hraj (Vez & X, Vez & Y, Vez & Z, int k)
{
    if (k > 1) hraj (X, Z, Y, k-1); // k-1 disku, X --> Y, Z je pomocna vez
    krok (X, Z); // 1 disk, X --> Z
    tiskni (A, B, C); // vytiskneme jeden krok
    if (k > 1) hraj (Y, X, Z, k-1); // k-1 disku, Y --> Z, X je pomocna vez
}
</code>

//X,Y,Z bude vždy nějakou permutací skutečných věží A,B,C// \\
//Pro tisk použijeme globální proměnné A,B,C aby věže byly zobrazeny ve svém opravdovém pořadí//

//Pod horními **k** prvky mohou být ve všech věžích "na dně" další větší disky.//


===== Funkce main =====

Vytiskneme počáteční stav. \\
Zavoláme funkci **hraj** s původními věžemi **A**, **B**, **C**. \\
Přeneseme **N** disků z **A** na **C**.

<code C++>
int main (int argc, char * argv [])
{
    init (A); // vez A - N disku
    nuluj (B); // veze B a C jsou prazdne
    nuluj (C);

    tiskni (A, B, C); // pocatecni stav
    hraj (A, B, C, N); // A --> C, B je pomocna vez, preneseme N disku
}
</code>


===== Složitost =====

  * funkce **krok** ... **O(1)**

  * funkce **hraj (k)**  ... **(2^k)-1** volání funkce **krok**

Označme  h(k) počet volání funkce **krok** v průběhu funce **hraj (k)**. \\
h(1) = 1 \\
h(k) = h(k-1) + 1 + h(k-1) \\
Indukcí dokážeme h(k) = (2^k) - 1

Přenos **N** disků ... **O(2^N)**



===== Celý program =====

http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/blob/master/veze/veze.cpp

<code C++>
#include <iostream>
#include <cassert>
using namespace std;

const int N = 5; // pocet disku

struct Vez
{
    int v;      // vyska veze
    int p [N];  // velikosti disku, p[0] je dole, p[v-1] je vrchol
};

Vez A, B, C;

void nuluj (Vez & X)
{
   X.v = 0; // nulova vyska

   for (int i = 0; i<N; i++)
        X.p [i] = 0; // pro ladeni - vse vynulujeme
}

void init (Vez & X)
{
    X.v = N; // N disku
    for (int i = 0; i<N; i++)
        X.p [i] = N-i; // dole p[0] = N, ..., nahore p[N-1] = 1
}

void zobraz (Vez & X)
{
    for (int i = 0; i < X.v; i++)
        cout << X.p[i];
    for (int i = X.v; i <= N; i++)
        cout << ' '; // dopln mezerami
}

void tiskni (Vez & X, Vez & Y, Vez & Z)
{
    zobraz (X);
    cout << " : ";
    zobraz (Y);
    cout << " : ";
    zobraz (Z);
    cout << endl;
}

void krok (Vez & X, Vez & Y) // presun disku z veze X na nez Y
{
    int h;
    assert (X.v > 0); // zkontroluj zda je vez neprazdna

    h = X.p [X.v-1]; // cislo disku z vrcholu veze X
    X.p [X.v-1] = 0; // pro ladeni - vynulujeme
    X.v = X.v - 1;  // zmensime vysku veze X

    assert (Y.v < N); // zkontroluj zda vez neni prilis vysoka
    if (Y.v > 0)
    {
        assert (h < Y.p [Y.v-1]); // zda h je mensi nez soucasny vrchol
    }

    Y.v = Y.v + 1; // zvysime vez Y
    Y.p [Y.v-1] = h; // na vrchol pridame disk h
}

void hraj (Vez & X, Vez & Y, Vez & Z, int k)
// presun z veze X na vez Z, vez Y bude pomocna vez
// preneseme k disku z vrcholu veze X
{
    if (k > 1) hraj (X, Z, Y, k-1); // k-1 disku, X --> Y, Z je pomocna vez
    krok (X, Z); // 1 disk, X --> Z
    tiskni (A, B, C); // vytiskneme jeden krok
    if (k > 1) hraj (Y, X, Z, k-1); // k-1 disku, Y --> Z, X je pomocna vez
}

int main (int argc, char * argv [])
{
    init (A); // vez A - N disku
    nuluj (B); // veze B a C jsou prazdne
    nuluj (C);

    tiskni (A, B, C); // pocatecni stav
    hraj (A, B, C, N); // A --> C, B je pomocna vez, preneseme N disku

    cout << "O.K." << endl;
    return 0;
}
</code>


===== Zobrazení pomocí Qt =====

Pro ilustraci http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/tree/master/veze-qt

{{zalg:veze.png?800}}

Vlevo dole nastavíme počet věží, stiskeme tlačítko "Run". \\
Posuvníkem (scroll barem) si můžeme prohlížet jednotlivé kroky. \\
V pravém dolním rohu se zobrazuje počet kroků (2^N)-1 zvětšený o jeden výchozí stav (2^N).