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

Przykład C#

Wieże Hanoi Algorytm rekurencyjny Program w C# Klasa C# implementacją wieży Wizualizacja palików i krążków Program w C# (animacja) Poprzedni przykład Następny przykład Program w 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ą metodę Przenieś, 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);
    Przenieś(a, c);
    if (n > 1) Hanoi(n - 1, b, a, c);
}

Pozostaje problem sformułowania metody 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 konsolowy, który wczytuje liczbę krążków i wypisuje ich wszystkie przesta­wienia, może wyglądać następująco:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Hanoi1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Wieże Hanoi\n-----------\nLiczba krążków: ");
            int n = int.Parse(Console.ReadLine());
            if (n > 0)
                Hanoi(n, 0, 1, 2);
            else
                Console.WriteLine("Problem z liczbą krążków.");
        }

        static void Hanoi(int n, int a, int b, int c)
        {
            if (n > 1) Hanoi(n - 1, a, c, b);
            Przenieś(a, c);
            if (n > 1) Hanoi(n - 1, b, a, c);
        }

        static void Przenieś(int p, int q)
        {
            const string palik = "abc";
            Console.WriteLine("{0} -> {1}", palik[p], palik[q]);
        }
    }
}

A oto przykładowy wynik wykonania tego programu:

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.

Zakładamy, że krążki wieży są w kolejności od najmniej­szego do najwię­kszego ponume­rowane liczbami całko­witymi od 1 do 10 (max). Numery te możemy przecho­wywać w 10-elemen­towej tablicy liczb całkowi­tych, której początek (element o indeksie zero) reprezen­tuje dno stosu (najwię­kszy krążek). Wówczas 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.

Wieża w popularnej grze dla dzieci jest obiektem rzeczy­wistym, którego natu­ralnym sposobem opisu w języku C# jest klasa stano­wiąca pewnego rodzaju szablon, według którego buduje się obiekty (instancje klasy). Definicja klasy opisującej zacho­wanie przedsta­wionej powyżej implemen­tacji tabli­cowej wieży złożonej z co najwyżej 10 krążków może mieć postać:

class Wieza
{
    private int n;              // Liczba krążków wieży
    private int[] krazek;       // Tablica numerów krążków

    public Wieza()              // Konstruktor
    {
        n = 0;
        krazek = new int[10];
    }

    public void Wstaw(int kr)   // Wstawienie krążka na stos
    {
        krazek[n++] = kr;
    }

    public int Zdejmij()        // Zdjęcie krążka ze stosu
    {
        return krazek[--n];
    }

    public int Wysokosc         // Wysokość stosu (liczba krążków)
    {
        get
        {
            return n;
        }
    }
}

Zapis ten oznacza, że klasa Wieza zawiera dwa pola prywatne, trzy metody publiczne i jedną właści­wość publiczną tylko do odczytu. Konstru­ktor klasy ustawia liczbę krążków wieży na zero i przy­dziela pamięć dla tablicy numerów krążków reprezen­tującej wieżę, 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 właści­wość Wysokosc udostę­pnia aktualną liczbę krążków (wysokość) wieży.

Wykorzystanie powyższej klasy wymaga utwo­rzenia obiektu za pomocą opera­tora new, który rezerwuje dla tego obiektu obszar pamięci, wywołuje inicjali­zujący go konstru­ktor i zwraca jego referencję (adres obszaru pamięci przydzie­lonej obiektowi). Dostęp do składowej utworzo­nego obiektu uzyskujemy 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 = new Wieza();
for (int k = 5; k > 0; k--)
    w.Wstaw(k);
while (w.Wysokosc > 0)
    Console.WriteLine(w.Zdejmij());

W programie prezen­tującym wizualnie rozwiązy­wanie zadania o wieżach Hanoi i korzysta­jącym z klasy Wieza potrzebne są trzy obiekty tej klasy. Ich refe­rencje wygodnie jest umieścić w tablicy trójelemen­towej, ponieważ indeksy 0, 1 i 2 jej elementów są wtedy numerami palików. Przed użyciem tej tablicy należy nie tylko ją utworzyć, lecz także zainicja­lizować wszystkie jej elementy:

Wieza[] wieża = new Wieza[3];
wieża[0] = new Wieza();
wieża[1] = new Wieza();
wieża[2] = new Wieza();

Możliwy jest również zwarty zapis inicjali­zacji tablicy i jej elementów bez podawania ich liczby:

Wieza[] wieża = new Wieza[] { new Wieza(), new Wieza(), new Wieza() };

W przestrzeni System.Collections.Generic platformy .NET dostępne są tzw. typy generyczne pozwalające na tworzenie różnych struktur danych, takich jak lista, kolejka, stos, słownik itd., opartych na kolekcjach obiektów tego samego typu i dostarcza­jących podsta­wowych operacji, do których należą m.in. dodanie nowego elementu do kolekcji, usunięcie elementu z kolekcji i udostę­pnienie liczby wszystkich jej elementów. Pojemność kolekcji ustalona przez konstru­ktor jest w razie potrzeby automa­tycznie zwiększana. Typ elementów klasy genery­cznej określa się w dekla­racji zmiennej po nazwie klasy w nawiasach <>. W przyto­czonym powyżej fragmencie kodu obsługu­jącego wieżę pięciu krążków można zamiast klasy Wieza użyć genery­cznej klasy Stack o elementach typu int:

Stack<int> w = new Stack<int>();
for (int k = 5; k > 0; k--)
    w.Push(k);
while (w.Count > 0)
    Console.WriteLine(w.Pop());

Naturalnie klasa Stack jest implementacją stosu. Jej metoda Push wstawia element danych na wierz­chołek stosu, metoda Pop usuwa element z wierz­chołka i zwraca go, a właści­wość Count udostępnia aktualną liczbę elementów stosu. Wypada przy okazji dodać, że nie są to jedyne metody i właści­wości tej klasy, np. Peek zwraca element z wierz­chołka bez usuwania go, a Clear usuwa wszystkie elementy kolekcji.

Jeżeli w programie mają być stosowane algorytmy i struktury danych, rzadko trzeba je tworzyć od podstaw, gdyż zazwyczaj znajdują się one w biblio­tekach standar­dowych. Warto wtedy z nich skorzystać, są bowiem przetesto­wane, wydajne i nie trzeba marnować czasu na ich pisanie. Zgodnie z tym zaleceniem użyto klasy genery­cznej Stack w poniż­szej, wstępnej wersji programu konso­lowego prezentu­jącego wizualnie przeno­szenie wież Hanoi. Program wczytuje z klawia­tury liczbę krążków, tworzy trójele­mentową tablicę elementów Stack<int> reprezen­tujących paliki z pustymi wieżami, układa na pierwszym wieżę z wczytanej liczby krążków, a następnie przenosi ją na trzeci palik, postępując według opisanego na początku niniejszej witryny algorytmu rekuren­cyjnego. Kropkami oznaczono niesprecy­zowane jeszcze fragmenty kodu dotyczące wizuali­zacji krążków i ich przesu­wania na ekranie.

class Program
{
    static void Main(string[] args)
    {
        Console.Write("Liczba krążków (1-10): ");
        n = int.Parse(Console.ReadLine());
        wieża = new Stack<int>[] { new Stack<int>(), new Stack<int>(), new Stack<int>() };
        for (int k = n; k > 0; k--)
        {
            wieża[0].Push(k);
            ...                 // Wizualizacja krążka k na paliku 0
        }
        Hanoi(n, 0, 1, 2);
    }

    static void Hanoi(int n, int a, int b, int c)
    {
        if (n > 1) Hanoi(n - 1, a, c, b);
        Przenieś(a, c);
        if (n > 1) Hanoi(n - 1, b, a, c);
    }

    static void Przenieś(int p, int q)
    {
        int kr = wieża[p].Pop();
        ...                     // Wizualizacja przenoszenia krążka kr z plika p na palik q
        wieża[q].Push(kr);
    }

    static int n;               // Liczba krążków
    static Stack<int>[] wieża;  // Paliki z wieżami
}

Wizualizacja palików i krążków

Naturalną reprezentacją palików i krążków są w programie konso­lowym łańcuchy złożone ze znaków semigra­ficznych, za pomocą których można w trybie tekstowym tworzyć ramki, przyciski i inne proste kompo­zycje graficzne. Potrze­bujemy tylko jednego ze znaków semigra­ficznych – zapełnio­nego prosto­kącika, który w języku C# ma zapis '\u2580' (standard Unicode) i przy wyświe­tlaniu w oknie konsoli jest automatycznie zamie­niany na znak '\xdb' (zob. wieże Hanoi w C++). Dobrym rozwią­zaniem jest utwo­rzenie tablicy łańcuchów złożonych z takich prosto­kącików i uzupeł­nionych z obu stron spacjami, by wszystkie ze względu na wygodę pozycjo­nowania na ekranie były jedna­kowej długości (rys.):

krążek = new string[11];
for (int k = 0; k <= 10; k++)
{
    string s = new String(' ', 10 - k);
    krążek[k] = s + new String('\u2588', 2 * k + 1) + s;
}
...
static string[] krążek;         // Fragment palika (0) i krążki (1-10)

Jak łatwo zauważyć, długości łańcuchów wynoszą 21 znaków. Łańcuch o indeksie 0 wyobraża fragment palika, następne reprezen­tują krążki o nume­rach od 1 do 10. Paliki będą składane z 11 fragmentów. Ich kolor i kolory krążków wybieramy z zestawu 16 kolorów dostępnych w klasie Console­Color i umieszczamy w tablicy skorelo­wanej indeksami elementów z tablicą krążek:

static ConsoleColor[] kolor = { // Kolor:
    ConsoleColor.Black,         // palika
    ConsoleColor.Magenta,       // krążka 1
    ConsoleColor.Green,         // krążka 2
    ConsoleColor.Red,           // krążka 3
    ConsoleColor.Blue,          // krążka 4
    ConsoleColor.Cyan,          // krążka 5
    ConsoleColor.DarkYellow,    // krążka 6
    ConsoleColor.Green,         // krążka 7
    ConsoleColor.Red,           // krążka 8
    ConsoleColor.Cyan,          // krążka 9
    ConsoleColor.Magenta };     // krążka 10

Przyjmiemy, że tło okna konsoli będzie białe, a wypisywany w nim tekst czarny nieza­leżnie od tego, czy program będzie urucha­miany z poziomu środo­wiska programi­stycznego, czy z konsoli. Z tego względu na początku wykonania program będzie ustawiał kolory okna i czyścił go:

Console.BackgroundColor = ConsoleColor.White;
Console.ForegroundColor = ConsoleColor.Black;
Console.Clear();

Po tych przygotowaniach wyświe­tlanie palików, ich podłoża (poziomej linii złożonej ze znaków semigra­ficznych '\u2580' przedsta­wiających zapeł­nioną górną połowę prosto­kącika), początkowego układu krążków i komuni­katu o możli­wości przerwania wyko­nania programu można zaprogra­mować nastę­pująco:

Console.SetCursorPosition(0, GÓRA);
for (int k = GÓRA; k <= DÓŁ; k++)
    Console.WriteLine(" {0}{1}{2}", krążek[0], krążek[0], krążek[0]);
Console.Write(new String('\u2580', 3 * 21 + 2));
for (int k = n; k > 0; k--)
{
    wieża[0].Push(k);
    Console.SetCursorPosition(1, DÓŁ + k - n);
    Console.ForegroundColor = kolor[k];
    Console.Write(krążek[k]);
}
Console.ForegroundColor = kolor[0];
Console.SetCursorPosition(0, DÓŁ + 2);
Console.Write("Przerwanie wykonania programu: Esc");
...
const int GÓRA = 6;             // Górny wiersz (wierzchołek palika)
const int DÓŁ = 16;             // Dolny wiersz (podstawa palika)

Paliki są wyświetlane w wierszach o numerach przebiega­jących wartości od stałej GÓRA do stałej DÓŁ. Krążek n jest po wstawieniu na wierz­chołek wieży o indeksie zero wyświe­tlany w wierszu DÓŁ, krążek n–1 w wierszu DÓŁ–1, ..., krążek 1 w wierszu DÓŁ+1–n. Metoda ResetColor przywraca domyślny kolor tła i tekstu okna konsoli (WhiteBlack). Wynik działania tego fragmentu kodu dla dziewięciu krążków w gotowym programie ilustruje poniższy rysunek:

Program w C# (animacja)

Oprócz wczytywanej z klawiatury liczby krążków do zmiennej n program będzie na początku przebiegu pobierał 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. Jak już wcześniej wspomniano, przebieg programu będzie można również przerwać za pomocą klawisza Esc, gdy np. trwa zbyt długo. Spełnienie tych dwóch wymagań ułatwiają następu­jące metody pomocnicze:

static void Wyczyść(int wiersz)
{
    Console.SetCursorPosition(0, wiersz);
    Console.Write(new String(' ', Console.WindowWidth));
    Console.SetCursorPosition(0, wiersz);
}

static void Koniec()
{
    Wyczyść(DÓŁ + 3);
    Console.CursorVisible = true;
    Environment.Exit(2);
}

static void Zatrzymanie(bool klawisz)
{
    if (klawisz)
    {
        Console.SetCursorPosition(0, DÓŁ + 3);
        Console.Write("Naciśnij dowolny klawisz...");
        if (Console.ReadKey(true).Key == ConsoleKey.Escape)
            Koniec();
        Wyczyść(DÓŁ + 3);
    }
    else
    {
        if (Console.KeyAvailable && Console.ReadKey(true).Key == ConsoleKey.Escape)
            Koniec();
        System.Threading.Thread.Sleep(PRZERWA);
    }
}

Metoda Wyczyść jedynie kasuje tekst określo­nego wiersza, a metoda 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. Z kolei metoda Zatrzymanie wstrzymuje wykonanie programu do momentu naciśnięcia klawisza lub upły­nięcia określonego odcinka czasu. Jeżeli argu­mentem jej wywołania 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, przebieg programu zostanie przerwany, a gdy naciśnie inny klawisz, wiersz z tekstem komunikatu zostanie wyczyszczony i wykonanie programu będzie kontynu­owane. Jeśli natomiast argu­mentem metody 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 równej wartości stałej PRZERWA (1000 ms). Metoda Sleep klasy Thread (wątek) wstrzy­mująca wykonanie programu przez określoną liczbę milisekund jest dostępna w prze­strzeni nazw System.Threa­ding.Thread.

Po wczytaniu wartości zmiennych nstop, utworzeniu trójele­mentowej tablicy wieża reprezen­tującej paliki z wieżami i tablicy łańcuchów krążek wyobraża­jącej fragment palika i 10 krążków oraz zobrazo­waniu w oknie konsoli palików, ich podłoża i początko­wego układu krążków można przystąpić do ich przeno­szenia za pomocą rekuren­cyjnej metody Hanoi. Dalsza rozbudowa programu wymaga sformu­łowania wywoły­wanej przez nią metody Przenieś, której zadaniem jest przenie­sienie szczyto­wego krążka z jednego palika na inny palik. Argumenty metody, które nazwiemy pq, określają numery palików. Naszym zamie­rzeniem jest opisanie operacji zdejmo­wania krążka z palika p i nakła­dania go na palik q. Wstępnie tę metodę można wyrazić nastę­pująco:

static void Przenieś(int p, int q)
{
    int kr = wieża[p].Pop();
   
    ... // Przesuwaj krążek kr w górę palika p do wiersza GÓRA
   
    ... // Przesuń krążek kr poziomo od palika p do palika q
   
    ... // Przesuwaj krążek kr w dół palika q od wiersza GÓRA
   
    wieża[q].Push(kr);
    if (wieża[2].Count < 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ą instrukcją metody po przenie­sieniu krążka jest wstrzy­mywanie przebiegu programu do momentu naciśnięcia klawisza, gdy warto­ścią zmiennej stop jest znak T, lub do momentu upły­nięcia określonej przez stałą PRZERWA liczby milisekund, 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 krążek wyno­szącej 21 znaków, a y od wysokości wieży ułożonej na paliku i stałej DÓŁ. 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 GÓRA:

int x = 21 * p + 1;
int y = DÓŁ - wieza[p].Count();
while (y > GÓRA)
{
    Console.SetCursorPosition(x, y--);
    Console.Write(krążek[0]);
    Console.SetCursorPosition(x, y);
    Console.ForegroundColor = kolor[kr];
    Console.Write(krążek[kr]);
    Console.ForegroundColor = kolor[0];
    System.Threading.Thread.Sleep(PRZESKOK);
}

Przed wyświetleniem krążka w nowym miejscu ustawiany jest odpowiadający mu kolor pierw­szego planu konsoli, a po wyświe­tleniu przywracany jest kolor czarny. Po każdym przemie­szczeniu 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 (30 ms). 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:

Console.SetCursorPosition(x, y);
Console.Write(krążek[0]);
Console.SetCursorPosition(x = 21 * q + 1, y);
Console.ForegroundColor = kolor[kr];
Console.Write(krążek[kr]);
Console.ForegroundColor = kolor[0];

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 = DÓŁ - wieża[q].Count;
while (y < p)
{
    System.Threading.Thread.Sleep(PRZESKOK);
    Console.SetCursorPosition(x, y++);
    Console.Write(krążek[0]);
    Console.SetCursorPosition(x, y);
    Console.ForegroundColor = kolor[kr];
    Console.Write(krążek[kr]);
    Console.ForegroundColor = kolor[0];
}

Pełny program konsolowy prezentu­jący rozwiązy­wanie zadania o wieżach Hanoi techniką animacji jest przedsta­wiony na poniż­szym listingu. Genero­wanie tablic wieżakrążek oraz zobrazo­wanie palików, podłoża i układu początko­wego krążków zostało z metody Main wydzielone do odrębnej metody Start. Przed wywoła­niem metody Hanoi kursor jest ukrywany, by nie śnieżył ekranu w trakcie przeno­szenia krążków, a po ich przenie­sieniu jest przywracany.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Hanoi2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.SetWindowSize(70, 22);
            Console.BackgroundColor = ConsoleColor.White;
            Console.ForegroundColor = ConsoleColor.Black;
            Console.Clear();
            Console.Write("Wieże Hanoi\n-----------\nLiczba krążków (1-10): ");
            try
            {
                n = int.Parse(Console.ReadLine().Trim());
                if (n <= 0 || n > 10)
                    throw new Exception("Problem z liczbą krążków.");
                Console.Write("Zatrzymania (T/N): ");
                while ((stop = char.ToUpper(Console.ReadKey(true).KeyChar)) != 'T' && stop != 'N')
                    ;
                Console.WriteLine(stop);
                Start();
                Console.CursorVisible = false;
                Hanoi(n, 0, 1, 2);
                Wyczyść(DÓŁ + 2);
                Console.CursorVisible = true;
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }

        static void Hanoi(int n, int a, int b, int c)
        {
            if (n > 1) Hanoi(n - 1, a, c, b);
            Przenieś(a, c);
            if (n > 1) Hanoi(n - 1, b, a, c);
        }

        static void Przenieś(int p, int q)
        {
            int kr = wieża[p].Pop();
            int x = 21 * p + 1;
            int y = DÓŁ - wieża[p].Count;
            while (y > GÓRA)
            {
                Console.SetCursorPosition(x, y--);
                Console.Write(krążek[0]);
                Console.SetCursorPosition(x, y);
                Console.ForegroundColor = kolor[kr];
                Console.Write(krążek[kr]);
                Console.ForegroundColor = kolor[0];
                System.Threading.Thread.Sleep(PRZESKOK);
            }
            Console.SetCursorPosition(x, y);
            Console.Write(krążek[0]);
            Console.SetCursorPosition(x = 21 * q + 1, y);
            Console.ForegroundColor = kolor[kr];
            Console.Write(krążek[kr]);
            Console.ForegroundColor = kolor[0];
            p = DÓŁ - wieża[q].Count;
            while (y < p)
            {
                System.Threading.Thread.Sleep(PRZESKOK);
                Console.SetCursorPosition(x, y++);
                Console.Write(krążek[0]);
                Console.SetCursorPosition(x, y);
                Console.ForegroundColor = kolor[kr];
                Console.Write(krążek[kr]);
                Console.ForegroundColor = kolor[0];
            }
            wieża[q].Push(kr);
            if (wieża[2].Count < n) Zatrzymanie(stop == 'T');
        }

        static void Start()
        {
            wieża = new Stack<int>[] { new Stack<int>(), new Stack<int>(), new Stack<int>() };
            krążek = new string[11];
            for (int k = 0; k <= 10; k++)
            {
                string s = new String(' ', 10 - k);
                krążek[k] = s + new String('\u2588', 2 * k + 1) + s;
            }
            Console.SetCursorPosition(0, GÓRA);
            for (int k = GÓRA; k <= DÓŁ; k++)
                Console.WriteLine(" {0}{1}{2}", krążek[0], krążek[0], krążek[0]);
            Console.Write(new String('\u2580', 3 * 21 + 2));
            for (int k = n; k > 0; k--)
            {
                wieża[0].Push(k);
                Console.SetCursorPosition(1, DÓŁ + k - n);
                Console.ForegroundColor = kolor[k];
                Console.Write(krążek[k]);
            }
            Console.ForegroundColor = kolor[0];
            Console.SetCursorPosition(0, DÓŁ + 2);
            Console.Write("Przerwanie wykonania programu: Esc");
            Zatrzymanie(true);
        }

        static void Wyczyść(int wiersz)
        {
            Console.SetCursorPosition(0, wiersz);
            Console.Write(new String(' ', Console.WindowWidth));
            Console.SetCursorPosition(0, wiersz);
        }

        static void Koniec()
        {
            Wyczyść(DÓŁ + 3);
            Console.CursorVisible = true;
            Environment.Exit(2);
        }

        static void Zatrzymanie(bool klawisz)
        {
            if (klawisz)
            {
                Console.SetCursorPosition(0, DÓŁ + 3);
                Console.Write("Naciśnij dowolny klawisz...");
                if (Console.ReadKey(true).Key == ConsoleKey.Escape)
                    Koniec();
                Wyczyść(DÓŁ + 3);
            }
            else
            {
                if (Console.KeyAvailable && Console.ReadKey(true).Key == ConsoleKey.Escape)
                    Koniec();
                System.Threading.Thread.Sleep(PRZERWA);
            }
        }

        const int GÓRA = 6;                 // Górny wiersz (wierzchołek palika)
        const int DÓŁ = 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)

        static int n;                       // Liczba krążków
        static char stop;                   // T - zatrzymania, N - nie
        static Stack<int>[] wieża;          // Paliki z wieżami
        static string[] krążek;             // Fragment palika (0) i krążki (1-10)

        static readonly ConsoleColor[] kolor = { // Kolory palika (0) i krążków (1-10)
            ConsoleColor.Black, ConsoleColor.Magenta, ConsoleColor.Green, ConsoleColor.Red,
            ConsoleColor.Blue, ConsoleColor.Cyan, ConsoleColor.DarkYellow, ConsoleColor.Green,
            ConsoleColor.Red, ConsoleColor.Cyan, ConsoleColor.Magenta };
    }
}

Przykładowe okno wygenerowane przez program w trakcie przeno­szenia wieży 10-krążkowej jest przedsta­wione na poniższym rysunku. Cały przebieg programu trwał ok. 25 min. Nie przeczy to jednak podanemu wcześniej wynikowi obliczeń wyno­szącemu 17 min, gdyż przeno­szenie krążka trwa tu dłużej niż 1000 ms ze względu na dodatkowy czas przeskoku krążków między wierszami.


Opracowanie przykładu: czerwiec 2019