PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C++

Wieże Hanoi Algorytm rekurencyjny Program w C++ Klasa C++ implementacją wieży Program w C++ (animacja) Program w C++ (kolorowanie krążków) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Wieże Hanoi

W łamigłówce o wieżach Hanoi, znanej z popularnej gry logicznej dla dzieci, dane są trzy paliki i n krążków o różnych średni­cach. Na początku wszystkie krążki są nałożone na pierw­szym paliku w kolej­ności malejących średnic (rys.). Zadanie polega na przenie­sieniu wszystkich krążków z pierw­szego palika na trzeci zgodnie z dwiema regułami:

Według tybetańskiej legendy mnisi z świątyni Benares w Hanoi rozwiązują łamigłówkę dla wieży ułożonej przez boga Brahmę z 64 złotych krążków i 3 diamen­towych igieł. Gdy zakończą zadanie, ma nastąpić koniec świata. Ile czasu nam pozostało?

Algorytm rekurencyjny

Algorytm przenoszenia wież jest zaskaku­jąco prosty, jeśli zauważy się, że wieżę złożoną z n krążków można potra­ktować jako mniejszą, złożoną z n–1 krążków, nałożoną na krążek n. Wówczas zadanie przenie­sienia wieży n-krążkowej z palika a na palik c poprzez palik b można opisać w postaci schematu rekuren­cyjnego:

Oczywiście kroki pierwszy i trzeci nie występują w skrajnym przypadku n=1. Przesu­nięcie wieży Hanoi wymaga wtedy jednego przesu­nięcia krążka. W celu udzie­lenia odpowiedzi na pytanie, ile należy wykonać przesu­nięć pojedyn­czych krążków, by rozwiązać łamigłówkę wież Hanoi n-krążkowych, oznaczmy tę liczbę przez kn. Wiadomo, że k1=1, a ponadto z powyż­szego algorytmu wynika, że przesu­nięcie wieży n-krążkowej wymaga dwóch przesu­nięć wieży n–1-krążkowej i jednego przesu­nięcia ostatniego krążka. Łatwo stąd otrzy­mujemy ogólny wzór na liczbę przesu­nięć krążków wieży z n krążkami:

Powróćmy do legendy zakładając, że mnisi przenoszą jeden krążek na sekundę. Z powyż­szego wzoru wynika wówczas, że ułożenie wieży zajmie im 264−1 sekund, co wynosi około 584 mld lat.

Program w C++

Posługując się numerami palików i uwzglę­dniając pomocniczą funkcję przenies, która zdejmuje szczytowy krążek z jednego palika i nakłada go na drugi, możemy przedsta­wiony powyżej algorytm wyrazić w języku C++ w postaci:

void hanoi(int n, int a, int b, int c)
{
    if (n > 1) hanoi(n - 1, a, c, b);
    przenies(a, c);
    if (n > 1) hanoi(n - 1, b, a, c);
}

Pozostaje problem sformułowania funkcji pomocni­czej. W najpro­stszym przypadku wystarczy, by podawała informację, z którego palika jest pobierany krążek i na który jest nakładany, gdyż zawsze dostępny jest tylko krążek położony na wierz­chołku wieży. Pełny program, który wczytuje liczbę krążków i wypisuje ich wszystkie przesta­wienia, może wyglądać następująco:

#include <iostream>

using namespace std;

void przenies(int p, int q)
{
    const char palik[] = { 'a', 'b', 'c' };
    cout << palik[p] << " -> " << palik[q] << endl;
}

void hanoi(int n, int a, int b, int c)
{
    if (n > 1) hanoi(n - 1, a, c, b);
    przenies(a, c);
    if (n > 1) hanoi(n - 1, b, a, c);
}

int main()
{
    int n;
    cout << "Wieże Hanoi\n-----------\nLiczba krążków: ";
    cin >> n;
    if (n > 0)
        hanoi(n, 0, 1, 2);
    else
        cout << "Problem z liczbą krążków.\n";
    return 0;
}

A oto przykładowe wyniki jego wykonania:

Bardziej ambitny program mógłby demonstrować rozwią­zanie zadania, tworząc iluzję ruchu przeno­szonych krążków. Ta technika, nazywana animacją, polega na genero­waniu i wyświe­tlaniu na ekranie w któtkich odstępach czasu obrazów przesuwa­jącego się obiektu, pracu­jącej maszyny, zachodzą­cego zjawiska itp. Jeśli nadal założymy, że przeło­żenie krążka zajmie progra­mowi jedną sekundę, to przy 10 krążkach przesta­wianie wieży będzie trwało 210–1=1023 sekundy, czyli ok. 17 minut. Zatem budując taki program przyjmiemy, że wieża będzie zawierać nie więcej niż 10 krążków.

Klasa C++ implementacją wieży

Układana z krążków wieża Hanoi umożliwia jedynie wstawianie krążka na jej wierz­chołek i zdejmo­wanie go stamtąd. Struktura danych o tej własności nazywana jest w algory­tmice i informa­tyce stosem (ang. stack). Mówimy, że element wstawiamy na wierz­chołek lub szczyt stosu (ang. top) bądź go z niego zdejmujemy, a o ele­mencie, którego nie daje się zdjąć, dopóki nie zdejmie się wszystkich innych elementów, mówimy, że leży na dnie stosu. Operacje wstawiania i usuwania elementu dotyczą zawsze wierz­chołka stosu.

Numery krążków wieży możemy przecho­wywać w 10-elemen­towej tablicy liczb całkowi­tych. Gdy przyj­miemy, że jej początek (element o indeksie zero) reprezen­tuje dno stosu (najwię­kszy krążek), to poło­żenie wierz­chołka przesuwa się w kierunku końca (elementu o inde­ksie 9) w miarę wsta­wiania elementów na stos bądź w kierunku początku w miarę zdejmo­wania ich ze stosu (rys.). Jeśli wieża składa się z n krążków, element o indeksie n–1 jest wierz­chołkiem stosu.

Znaleźliśmy się w sytuacji, w której nie wypada unikać progra­mowania obiekto­wego. Wieża złożona z krążków jest bowiem dosko­nałym obiektem rzeczy­wistym, którego natu­ralnym sposobem opisu w programie kompute­rowym jest progra­mowanie obiektowe, a chcąc jak najlepiej spożytkować możli­wości języka C++, powinniśmy defi­niować klasy obiektów, by uzyskać bardziej przejrzystą wersję kodu programu. Formalnie klasa jest typem stano­wiącym pewnego rodzaju szablon, według którego buduje się obiekty. Elementami składowymi klasy są pola (dane) określa­jące cechy obiektu i metody (funkcje) opisujące jego zacho­wanie. Definicja klasy przypo­mina definicję struktury. Różnica polega na użyciu słowa kluczo­wego class zamiast struct i zadekla­rowaniu, oprócz pól, metod. Poziom dostępu do składników klasy określają specyfi­katory dostępu, np. słowo public oznacza, że wymienione po nim składowe są dostępne w całym programie (publiczne), a private, że są dostępne tylko w klasie, w której zostały zdefinio­wane (prywatne). Brak specyfi­katora dostępu oznacza, że składowe klasy są prywatne.

Definicja klasy opisującej zachowanie przedsta­wionej powyżej implemen­tacji tabli­cowej wieży złożonej z co najwyżej 10 krążków może wyglądać następująco:

class Wieza
{
    int n;
    int krazek[10];
public:
    Wieza();
    void Wstaw(int kr);
    int Zdejmij();
    int Wysokosc();
};

Zapis ten oznacza, że klasa Wieza zawiera dwa pola prywatne i cztery metody publiczne. Deklaracje metod mają postać nagłówków (proto­typów) funkcji. Metoda Wieza jest tzw. konstru­ktorem wywoły­wanym automaty­cznie w momencie tworzenia obiektu (instancji klasy). Konstru­ktor ma zawsze nazwę taką samą jak klasa i nie zwraca żadnej wartości (nawet typu void). Pozostałe metody określają funkcjo­nalność obiektu klasy: Wstaw – wsta­wienie krążka na wierz­chołek wieży, Zdejmij – zdjęcie krążka z jej wierz­chołka, Wysokosc – udostę­pnienie liczby krążków wieży. Klasa nie zajmuje żadnego miejsca w pamięci, dopiero w momencie tworzenia obiektu jest dla niego rezerwo­wany obszar pamięci i jest wywoływany konstru­ktor, który inicja­lizuje obiekt, m.in. nadaje jego polom wartości początkowe. Podobnie jak w przypadku struktury, po nawiasie klamrowym zamyka­jącym definicję klasy wystę­puje średnik. Pomiędzy tymi dwoma znakami można w razie potrzeby zamieścić listę zmiennych i wska­źników tej klasy.

Zapowiedziane w definicji klasy metody powinny być zdefinio­wane. Definicje te można umieszczać poza klasą (w tym samym lub innym pliku), jak i wewnątrz niej. W defini­cjach występu­jących na zewnątrz klasy nazwy metod poprzedza się nazwą klasy i opera­torem zakresu :: (dwa dwukropki), który określa ich przynale­żność do danej klasy. W rozpatry­wanym przypadku definicja klasy Wieza wraz z jej metodami wygląda następująco:

class Wieza
{
    int n;
    int krazek[10];
public:
    Wieza();
    void Wstaw(int kr);
    int Zdejmij();
    int Wysokosc();
};

Wieza::Wieza()
{
    n = 0;
}

void Wieza::Wstaw(int kr)
{
    krazek[n++] = kr;
}

int Wieza::Zdejmij()
{
    return krazek[--n];
}

int Wieza::Wysokosc()
{
    return n;
}

Jak widać, konstruktor klasy Wieza ustawia liczbę krążków wieży na zero, metoda Wstaw wstawia określony w argu­mencie numer krążka na wierz­chołek wieży i zwiększa liczbę jej krążków o 1, metoda Zdejmij zwraca numer krążka z wierz­chołka wieży i zmniejsza liczbę jej krążków o 1, a metoda Wysokość zwraca aktualną liczbę krążków wieży. Kod wszystkich metod jest bardzo krótki, toteż można ich definicje umieścić wewnątrz klasy, co prowadzi do jej zwartej postaci:

class Wieza
{
    int n;
    int krazek[10];
public:
    Wieza() { n = 0; }
    void Wstaw(int kr) { krazek[n++] = kr; }
    int Zdejmij() { return krazek[--n]; }
    int Wysokosc() { return n; }
};

W najprostszym przypadku wykorzystanie powyższej klasy polega na zdefinio­waniu zmiennej typu Wieza, podobnie jak np. zmiennej typu int. Definicja ta powoduje automa­tycze wywołanie konstru­ktora. Dostęp do składowej utworzo­nego obiektu uzyskujemy w taki sam sposób jak do pól struktury, czyli za pomocą opera­tora kropki. Na przykład poniższy fragment kodu tworzy wieżę z pięciu krążków, a potem zdejmuje je z niej i wypisuje ich numery:

Wieza w;
for (int k = 5; k > 0; k--)
    w.Wstaw(k);
while (w.Wysokosc() > 0)
    cout << w.Zdejmij() << endl;

Obiekt można również utworzyć dynamicznie za pomocą opera­tora new, który rezerwuje dla niego obszar pamięci, wywołuje inicjali­zujący go konstru­ktor i zwraca wskaźnik na ten obiekt. Pamięć przydzie­lona dynami­cznie powinna być po wykorzy­staniu obiektu zwolniona za pomocą opera­tora delete. Dostęp do składowej takiego obiektu wymaga użycia opera­torów gwiazdki i kropki albo opera­tora ->. Na przykład powyższy fragment programu można zamienić na postać o podobnym działaniu:

Wieza *p = new Wieza();
for (int k = 5; k > 0; k--)
    p->Wstaw(k);
while (p->Wysokosc() > 0)
    cout << p->Zdejmij() << endl;
delete p;

Program w C++ (animacja)

Zgodnie z przyjętymi powyżej ustaleniami zakładamy, że krążki są ponume­rowane kolejnymi liczbami całko­witymi od 1 do 10 i implemen­tacją tworzonej z nich wieży jest obiekt klasy Wieza. Pozostajemy również przy przyjętej w poprze­dnim programie nume­racji palików 0, 1 i 2, co pozwoli na wykorzy­stanie rekuren­cyjnej funkcji hanoi bez zmian i prowadzi do defi­nicji tablicy trzech obiektów reprezen­tujących ustawiane z krążków wieże:

Wieza wieza[3];

Paliki są wstępnie puste. Ich stan początkowy zostanie ustalony dopiero po wczytaniu liczby krążków, kiedy wszystkie zostaną w kolej­ności od najwię­kszego do najmniej­szego nałożone na pierwszy palik:

for (int k = n; k > 0; k--)
    wieza[0].Wstaw(k);

Naszym celem jest teraz podjęcie decyzji odnośnie sposobu wizuali­zacji krążków na ekranie monitora i szybkości ich przesu­wania. Zakładamy, że animacja będzie prowa­dzona w oknie konsolowym, toteż paliki i krążki będą wyświe­tlane w trybie tekstowym jako łańcuchy znaków. Definiujemy następu­jące stałe i zmienne:

const int GORA = 6;         // Górny wiersz (wierzchołek palika)
const int DOL = 16;         // Dolny wiersz (podstawa palika)
const int PRZERWA = 1000;   // Przerwa po przeniesieniu krążka (ms)
const int PRZESKOK = 30;    // Czas przeskoku między wierszami (ms)

const string krazek[] = {
    "          |          ",    // Palik
    "         ###         ",    // Krążek 1
    "        #####        ",    // Krążek 2
    "       #######       ",    // Krążek 3
    "      #########      ",    // Krążek 4
    "     ###########     ",    // Krążek 5
    "    #############    ",    // Krążek 6
    "   ###############   ",    // Krążek 7
    "  #################  ",    // Krążek 8
    " ################### ",    // Krążek 9
    "#####################"};   // Krążek 10

int n;                      // Liczba krążków
int stop;                   // T - zatrzymania, N - nie

Łańcuch krazek[0] wyobraża fragment palika (cały palik wymaga 11 takich fragmentów), pozo­stałe reprezen­tują krążki o nume­rach od 1 do 10. Zważywszy na przejrzy­stość zapisu łańcu­chów, posłużono się znakami |#, które dla lepszego odwzoro­wania grafiki zostaną w rzeczy­wistym programie zastąpione znakami semigra­ficznymi '\xb3' (pełna pionowa kreska) i '\xdb' (zapeł­niony cały prosto­kącik znaku). Z tego samego względu podłoże palików i wież zostanie złożone ze znaków '\xdf' (zapeł­niona górna połowa prosto­kącika).

Przyjmujemy, że oprócz wczyty­wanej z klawia­tury liczby krążków do zmiennej n będzie również na początku przebiegu programu pobierany znak T lub N do zmiennej stop określa­jący, czy po każdym przenie­sieniu krążka na inny palik ma nastąpić wstrzy­manie wyko­nania programu do czasu naci­śnięcia klawisza, czy nie. Udogo­dnienie to umożliwi użytko­wnikowi podjęcie decyzji, czy ma mieć czas na odgady­wanie kolejnych ruchów, czy ma być tylko biernym obserwa­torem toczącego się postępo­wania. Wydaje się też rozsą­dnym, by przebieg programu dało się przerwać za pomocą klawisza Esc, gdy np. trwa zbyt długo. Spełnienie tych wymagań ułatwiają dwie funkcje pomocnicze:

void koniec()
{
    gotoxy(1, DOL + 3);
    clreol();
    setcursor(true);
    exit(2);
}

void zatrzymanie(bool klawisz)
{
    if (klawisz)
    {
        gotoxy(1, DOL + 3);
        cout << "Naciśnij dowolny klawisz...";
        if (_getch() == 27) koniec();
        gotoxy(1, DOL + 3);
        clreol();
    }
    else
    {
        if (_kbhit() != 0 && _getch() == 27) koniec();
        Sleep(PRZERWA);
    }
}

Funkcja koniec wywoływana, gdy użytko­wnik naciśnie klawisz Esc, czyści wiersz znajdujący się o 3 pozycje poniżej podstawy palików przezna­czony dla tekstu komuni­katów, przywraca wido­czność kursora wyłączoną na czas trwania animacji i kończy działanie programu kodem powrotu 2. Kod źródłowy funkcji jest poprawny pod warunkiem, że dostępne są funkcje gotoxy (ustawienie kursora w okre­ślonej pozycji znakowej w oknie konsoli), clreol (czyszczenie wiersza od aktualnej pozycji kursora do końca) i setcursor (wyłączenie lub włączenie kursora). W środo­wisku Borland C++ znajdują się one w biblio­tece conio (z funkcją _setcur­sortype zamiast setcursor), należy więc włączyć do programu plik nagłów­kowy conio.h. W środo­wiskach MinGW C++ i Visual C++ funkcje te nie występują, ale zostały zdefinio­wane na użytek niniej­szej witryny w module obsługi konsoli bconio, toteż należy dodać do projektu dwa pliki tego modułu i włączyć do programu plik nagłów­kowy bconio.h.

Zadaniem funkcji zatrzymanie jest wstrzy­manie wykonania programu do momentu naciśnięcia klawisza lub upły­nięcia określonego odcinka czasu. Jeżeli argu­mentem wywołania funkcji jest true, wyświe­tlony zostanie tekst informu­jący, że program oczekuje na naciśnięcie znaku na klawia­turze. Gdy użytko­wnik wybierze klawisz Esc (kod znaku 27), przebieg programu zostanie przerwany, a gdy inny klawisz, wiersz z tekstem komuni­katu zostanie wyczyszczony i wykonanie programu będzie kontynu­owane. Jeśli natomiast argu­mentem jest false, to gdy w buforze klawia­tury dostępny jest znak Esc, wykonanie programu zostanie przerwane, a gdy bufor jest pusty lub zawiera inny znak, przebieg programu będzie kontynu­owany po upły­nięciu liczby milisekund określonej w stałej PRZERWA. Funkcja Sleep wstrzy­mująca wykonanie programu przez określoną liczbę milisekund jest dostępna w pliku nagłów­kowym windows.h. W przypadku Borland C++ należy go włączyć do programu, a w przy­padku MinGW C++ i Visual C++ nie ma takiej potrzeby, gdyż jest włączany w pliku bconio.h.

Gdy wartości zmiennych nstop zostały wprowa­dzone, można zobra­zować na ekranie paliki, ich podłoże i początkowy układ krążków. Przyjmując, że łańcuchy reprezen­tujące pierwszy palik i wieżę będą wyświetlane od drugiej pozycji znakowej wiersza a podłoże palików i wież od pierwszej, zadanie to można zaprogra­mować nastę­pująco:

void start()
{
    gotoxy(1, GORA);
    for (int k = GORA; k <= DOL; k++)
        cout << ' ' << krazek[0] << krazek[0] << krazek[0] << endl;
    for (int k = 0; k < 65; k++)
        cout << "\xdf";
    for (int k = n; k > 0; k--)
    {
        wieza[0].Wstaw(k);
        gotoxy(2, DOL + k - n);
        cout << krazek[k];
    }
    gotoxy(1, DOL + 2);
    cout << "Przerwanie wykonania programu: Esc";
    zatrzymanie(true);
}

Krążek n jest po wstawieniu na wierz­chołek wieży o indeksie zero wyświe­tlany w wierszu o numerze DOL, krążek n–1 w wierszu DOL–1, ..., krążek 1 w wierszu DOL+1–n. Na koniec po podaniu informacji o możli­wości przerwania wykonania programu zostaje ono wstrzymane do momentu naciśnięcia klawisza. Wynik działania funkcji start dla ośmiu krążków w gotowym programie ilustruje poniższy rysunek:

Sformułujemy teraz dwuargumentową funkcję przenies wywoływaną w funkcji hanoi. Jej zadaniem jest przenie­sienie szczyto­wego krążka z jednego palika na inny palik. Argumenty funkcji, które nazwiemy p i q, określają numery palików. Naszym zamie­rzeniem jest opisanie operacji zdejmo­wania krążka z palika p i nakładania go na palik q. Wstępnie funkcję przenies można wyrazić nastę­pująco:

void przenies(int p, int q)
{
    int kr = wieza[p].Zdejmij();

    ... // Przesuwaj krążek kr w górę palika p do wiersza GORA

    ... // Przesuń krążek kr poziomo od palika p do palika q

    ... // Przesuwaj krążek kr w dół palika q od wiersza GORA

    wieza[q].Wstaw(kr);
    if (wieza[2].Wysokosc() < n) zatrzymanie(stop == 'T');
}

Operacja przesunięcia krążka polega na wyma­zaniu go w dotychcza­sowym miejscu poprzez wyświe­tlenie tam fragmentu palika, a następnie wyświe­tleniu krążka w nowym miejscu. Efektem wykony­wania ciągu takich operacji w krótkich odstępach czasu jest iluzja ruchu krążka na ekranie komputera. Płynność takiej animacji w trybie tekstowym jest słaba, nie mniej jednak oddaje reali­styczne wrażenie ruchu.

Ostatnią operacją w funkcji przenies jest po przenie­sieniu krążka wstrzy­mywanie przebiegu programu do momentu naciśnięcia klawisza, gdy warto­ścią zmiennej stop jest znak T, lub upły­nięcia określonej przez stałą PRZERWA liczby milise­kund, gdy warto­ścią tej zmiennej jest N. Wstrzy­manie wyko­nania programu jest pomijane, gdy wieża docelowa zawiera wszystkie krążki.

Precyzowanie zapowiedzianej w pierwszym komen­tarzu operacji rozpoczy­namy od wyzna­czenia pozycji znakowej (x,y) zdjętego z wieży krążka, którego graficzny wize­runek widnieje jeszcze na wierz­chołku wieży. Współ­rzędna x zależy od numeru palika i dłu­gości łańcuchów tablicy krazek wyno­szącej 21 znaków, a y od wysokości wieży ułożonej na paliku i stałej DOL. Gdy pozycja krążka jest już znana, można wykonywać kasowanie krążka i wyświe­tlanie go wiersz wyżej, dopóki nie znajdzie się on w wierszu o numerze GORA:

int x = 21 * p + 2;
int y = DOL - wieza[p].Wysokosc();
while (y > GORA)
{
    gotoxy(x, y--);
    cout << krazek[0];
    gotoxy(x, y);
    cout << krazek[kr];
    Sleep(PRZESKOK);
}

Po każdym przemieszczeniu krążka o wiersz w górę wykonanie programu zostaje na moment wstrzy­mane, by oko zdążyło zareje­strować obraz. Długość przerwy w milise­kundach określa stała PRZESKOK. Gdy krążek znajduje się u góry palika p, przesu­nięcie go do palika q zasygna­lizowane w drugim komen­tarzu sprowadza się jedynie do usunięcia krążka z jego aktual­nego miejsca i wyświe­tlenia go w nowym miejscu u góry palika q:

gotoxy(x, y);
cout << krazek[0];
gotoxy(x = 21 * q + 2, y);
cout << krazek[kr];

Kod zastępujący trzeci komentarz zaczynamy od wyzna­czenia numeru wiersza, w którym ma się znależć wierz­chołek wieży q po wsta­wieniu do niej krążka kr. Obliczoną wartość można zapamiętać w zmiennej p, gdyż numer poprze­dniego palika nie będzie dalej potrzebny. Teraz już łatwo przesuwać krążek w dół palika q, dopóki nie znajdzie się w wierszu o numerze p:

p = DOL - wieza[q].Wysokosc();
while (y < p)
{
    Sleep(PRZESKOK);
    gotoxy(x, y++);
    cout << krazek[0];
    gotoxy(x, y);
    cout << krazek[kr];
}

Pełny program prezentujący rozwiązy­wanie zadania o wieżach Hanoi techniką animacji jest przedsta­wiony na poniż­szym listingu. W funkcji main przed przeno­szeniem krążków za pomocą funkcji hanoi kursor zostaje ukryty, by nie śnieżył ekranu, a po ich przenie­sieniu jest przywracany.

#include <iostream>
#include <string>
#include "bconio.h"

using namespace std;

class Wieza
{
    int n;
    int krazek[10];
public:
    Wieza() { n = 0; }
    void Wstaw(int kr) { krazek[n++] = kr; }
    int Zdejmij() { return krazek[--n]; }
    int Wysokosc() { return n; }
} wieza[3];

const int GORA = 6;         // Górny wiersz (wierzchołek palika)
const int DOL = 16;         // Dolny wiersz (podstawa palika)
const int PRZERWA = 1000;   // Przerwa między przesunięciami krążka (ms)
const int PRZESKOK = 30;    // Przeskok krążka między wierszami (ms)

const string krazek[] = {
    "          \xb3          ",
    "         \xdb\xdb\xdb         ",
    "        \xdb\xdb\xdb\xdb\xdb        ",
    "       \xdb\xdb\xdb\xdb\xdb\xdb\xdb       ",
    "      \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb      ",
    "     \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb     ",
    "    \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb    ",
    "   \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb   ",
    "  \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb  ",
    " \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb ",
    "\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb"};

int n;                      // Liczba krążków
int stop;                   // T - zatrzymania, N - nie

void koniec()
{
    gotoxy(1, DOL + 3);
    clreol();
    setcursor(true);
    exit(2);
}

void zatrzymanie(bool klawisz)
{
    if (klawisz)
    {
        gotoxy(1, DOL + 3);
        cout << "Naciśnij dowolny klawisz...";
        if (_getch() == 27) koniec();
        gotoxy(1, DOL + 3);
        clreol();
    }
    else
    {
        if (_kbhit() != 0 && _getch() == 27) koniec();
        Sleep(PRZERWA);
    }
}

void start()
{
    gotoxy(1, GORA);
    for (int k = GORA; k <= DOL; k++)
        cout << ' ' << krazek[0] << krazek[0] << krazek[0] << endl;
    for (int k = 0; k < 65; k++)
        cout << "\xdf";
    for (int k = n; k > 0; k--)
    {
        wieza[0].Wstaw(k);
        gotoxy(2, DOL + k - n);
        cout << krazek[k];
    }
    gotoxy(1, DOL + 2);
    cout << "Przerwanie wykonania programu: Esc";
    zatrzymanie(true);
}

void przenies(int p, int q)
{
    int kr = wieza[p].Zdejmij();
    int x = 21 * p + 2;
    int y = DOL - wieza[p].Wysokosc();
    while (y > GORA)
    {
        gotoxy(x, y--);
        cout << krazek[0];
        gotoxy(x, y);
        cout << krazek[kr];
        Sleep(PRZESKOK);
    }
    gotoxy(x, y);
    cout << krazek[0];
    gotoxy(x = 21 * q + 2, y);
    cout << krazek[kr];
    p = DOL - wieza[q].Wysokosc();
    while (y < p)
    {
        Sleep(PRZESKOK);
        gotoxy(x, y++);
        cout << krazek[0];
        gotoxy(x, y);
        cout << krazek[kr];
    }
    wieza[q].Wstaw(kr);
    if (wieza[2].Wysokosc() < n) zatrzymanie(stop == 'T');
}

void hanoi(int n, int a, int b, int c)
{
    if (n > 1) hanoi(n - 1, a, c, b);
    przenies(a, c);
    if (n > 1) hanoi(n - 1, b, a, c);
}

int main()
{
    cout << "Wieże Hanoi\n-----------\nLiczba krążków (1-10): ";
    cin >> n;
    if (n > 0 && n <= 10)
    {
        cout << "Zatrzymania (T/N): ";
        while ((stop = toupper(_getch())) != 'T' && stop != 'N')
            ;
        cout << char(stop);
        start();
        setcursor(false);
        hanoi(n, 0, 1, 2);
        setcursor(true);
        gotoxy(1, DOL + 2);
        clreol();
        return 0;
    }
    else
    {
        cout << "Problem z liczbą krążków.\n";
        return 1;
    }
}

A oto przykładowy widok okna aplikacji w trakcie przeno­szenia wieży złożonej z ośmiu krążków:

Program w C++ (kolorowanie krążków)

Program rozwiązujący łamigłówkę o wieżach Hanoi stanie się bardziej atrakcyjny, gdy przekła­dane między palikami krążki będą, podobnie jak w popularnej grze dla dzieci, kolorowe. Stosowne zmiany są proste i łatwe do wprowa­dzenia. Po pierwsze, wybieramy część kolorów z zestawu 16 dostę­pnych w biblio­tece conio (Borland C++) lub module bconio (MinGW C++, Visual C++) i umieszczamy ich nazwy w 11 elemen­towej tablicy ściśle skore­lowanej indeksami elementów z tablicą krazek:

int kolor[] = {BLACK, LIGHTMAGENTA, LIGHTGREEN, LIGHTRED, LIGHTBLUE, LIGHTCYAN,
               BROWN, LIGHTGREEN, LIGHTRED, LIGHTCYAN, LIGHTMAGENTA};

Po drugie, funkcję main rozpoczynamy od usta­wienia czarnego koloru tekstu i białego tła oraz wyczyszczenia obszaru robo­czego okna konsoli:

textcolor(BLACK);
textbackground(WHITE);
clrscr();

Po trzecie wreszcie, przed wyświetleniem krążka ustawiamy odpowia­dający mu kolor tekstu określony w tablicy kolor, a po wyświe­tleniu go przywra­camy kolor czarny (kolor fragmentu palika i komuni­katów), np.:

textcolor(kolor[kr]);
cout << krazek[kr];
textcolor(kolor[0]);

W przypadku kompilatora Borland C++ nie są to zmiany wystar­czające, ponieważ stru­mienie cincout, jak i funkcje scanfprintf w tym środo­wisku nie reagują na zmianę koloru tekstu i tła. Można temu zaradzić, stosując funkcję cprintf z biblio­teki conio podobną w dzia­łaniu do funkcji printf, ale inaczej interpre­tującą znak nowego wiersza. Funkcja printf przed znakiem specjalnym '\n' (line feed – wysuw wiersza, nowy wiersz) wypro­wadza dodatkowo znak '\r' (carriage return – powrót karetki), a funkcja cprintf przy przejściu na początek nastę­pnego wiersza wymaga podania pary znaków specjal­nych '\r''\n', czyli łańcucha "\r\n".

Niespodzianką w Borland C++ jest również ograni­czenie zakresu argu­mentu funkcji textback­ground do numerów od 0 do 7. Wartości wyższe są redu­kowane do tego zakresu za pomocą operacji modulo 8 (% 8). Tak więc pomimo że w funkcji main określimy, że tło obszaru robo­czego okna konsoli ma być białe (numer 15 – WHITE), będzie ono jasno­szare (numer 7 – LIGHTGRAY).

Kod programu dla kompilatorów MinGW C++ i Visual C++ prezen­tujący przeno­szenie wież Hanoi składanych z kolo­rowych krążków jest przedsta­wiony na poniż­szym listingu.

#include <iostream>
#include <string>
#include "bconio.h"

using namespace std;

class Wieza
{
    int n;
    int krazek[10];
public:
    Wieza() { n = 0; }
    void Wstaw(int kr) { krazek[n++] = kr; }
    int Zdejmij() { return krazek[--n]; }
    int Wysokosc() { return n; }
} wieza[3];

const int GORA = 6;         // Górny wiersz (wierzchołek palika)
const int DOL = 16;         // Dolny wiersz (podstawa palika)
const int PRZERWA = 1000;   // Przerwa między przesunięciami krążka (ms)
const int PRZESKOK = 30;    // Przeskok krążka między wierszami (ms)

const string krazek[] = {
    "          \xb3          ",
    "         \xdb\xdb\xdb         ",
    "        \xdb\xdb\xdb\xdb\xdb        ",
    "       \xdb\xdb\xdb\xdb\xdb\xdb\xdb       ",
    "      \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb      ",
    "     \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb     ",
    "    \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb    ",
    "   \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb   ",
    "  \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb  ",
    " \xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb ",
    "\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb\xdb"};

int kolor[] = {BLACK, LIGHTMAGENTA, LIGHTGREEN, LIGHTRED, LIGHTBLUE, LIGHTCYAN,
               BROWN, LIGHTGREEN, LIGHTRED, LIGHTCYAN, LIGHTMAGENTA};

int n;                      // Liczba krążków
int stop;                   // T - zatrzymania, N - nie

void koniec()
{
    gotoxy(1, DOL + 3);
    clreol();
    setcursor(true);
    exit(2);
}

void zatrzymanie(bool klawisz)
{
    if (klawisz)
    {
        gotoxy(1, DOL + 3);
        cout << "Naciśnij dowolny klawisz...";
        if (_getch() == 27) koniec();
        gotoxy(1, DOL + 3);
        clreol();
    }
    else
    {
        if (_kbhit() != 0 && _getch() == 27) koniec();
        Sleep(PRZERWA);
    }
}

void start()
{
    gotoxy(1, GORA);
    for (int k = GORA; k <= DOL; k++)
        cout << ' ' << krazek[0] << krazek[0] << krazek[0] << endl;
    for (int k = 0; k < 65; k++)
        cout << "\xdf";
    for (int k = n; k > 0; k--)
    {
        wieza[0].Wstaw(k);
        gotoxy(2, DOL + k - n);
        textcolor(kolor[k]);
        cout << krazek[k];
    }
    textcolor(kolor[0]);
    gotoxy(1, DOL + 2);
    cout << "Przerwanie wykonania programu: Esc";
    zatrzymanie(true);
}

void przenies(int p, int q)
{
    int kr = wieza[p].Zdejmij();
    int x = 21 * p + 2;
    int y = DOL - wieza[p].Wysokosc();
    while (y > GORA)
    {
        gotoxy(x, y--);
        cout << krazek[0];
        gotoxy(x, y);
        textcolor(kolor[kr]);
        cout << krazek[kr];
        textcolor(kolor[0]);
        Sleep(PRZESKOK);
    }
    gotoxy(x, y);
    cout << krazek[0];
    gotoxy(x = 21 * q + 2, y);
    textcolor(kolor[kr]);
    cout << krazek[kr];
    textcolor(kolor[0]);
    p = DOL - wieza[q].Wysokosc();
    while (y < p)
    {
        Sleep(PRZESKOK);
        gotoxy(x, y++);
        cout << krazek[0];
        gotoxy(x, y);
        textcolor(kolor[kr]);
        cout << krazek[kr];
        textcolor(kolor[0]);
    }
    wieza[q].Wstaw(kr);
    if (wieza[2].Wysokosc() < n) zatrzymanie(stop == 'T');
}

void hanoi(int n, int a, int b, int c)
{
    if (n > 1) hanoi(n - 1, a, c, b);
    przenies(a, c);
    if (n > 1) hanoi(n - 1, b, a, c);
}

int main()
{
    textcolor(BLACK);
    textbackground(WHITE);
    clrscr();
    cout << "Wieże Hanoi\n-----------\nLiczba krążków (1-10): ";
    cin >> n;
    if (n > 0 && n <= 10)
    {
        cout << "Zatrzymania (T/N): ";
        while ((stop = toupper(_getch())) != 'T' && stop != 'N')
            ;
        cout << char(stop);
        start();
        setcursor(false);
        hanoi(n, 0, 1, 2);
        setcursor(true);
        gotoxy(1, DOL + 2);
        clreol();
        return 0;
    }
    else
    {
        cout << "Problem z liczbą krążków.\n";
        return 1;
    }
}

Oto przykładowe okna wygenerowane przez dwie wersje programu w trakcie jego wykonania:

a) wersja Borland C++,

b) wersja Visual C++.


Opracowanie przykładu: maj 2019