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.

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;

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.

void nuluj (Vez & X)
{
   X.v = 0; // nulova vyska
 
   for (int i = 0; i<N; i++)
        X.p [i] = 0; // pro ladeni - vse vynulujeme
}

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.

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
}

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.

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
}

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

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

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í

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

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

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
}

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

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
}

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.

void hraj (Vez & X, Vez & Y, Vez & Z, int k)

   if (k > 1) 
   {
      hraj (X, Z, Y, k-1);
   }

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

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

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

    krok (X, Z); // 1 disk, X --> Z

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

    if (k > 1) 
        hraj (Y, X, Z, k-1);

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
}

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.

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
}

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

#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;
}

Zobrazení pomocí Qt

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

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).

Hanojské věže