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

Przykład C++

Rozdanie kart do gry w brydża Lista jednokierunkowa kart i jej tasowanie Rozdanie kart czterem graczom Program w C++ (lista) Program w C++ (wersja 2, wektor) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Rozdanie kart do gry w brydża

Brydż jest logiczną grą karcianą, w której uczestniczy czterech graczy siedzą­cych naprze­ciwko siebie i tworzą­cych dwie rywali­zujące pary N-S (ang. north-south, północ-południe) i E-W (ang. east-west, wschód-zachód):

     N
  W     E
     S

Do gry używana jest standardowa talia 52 kart obejmująca cztery kolory (trefl – ♣, karo – , kier – i pik – ♠), po 13 kart w każdym kolorze (od dwójki do asa). Potasowane i przeło­żone karty gracz rozda­jący rozdaje po jednej zgodnie z ruchem wskazówek zegara, poczy­nając od gracza po lewej stronie. Każdy gracz otrzymuje więc po 13 kart. Przyjęło się układać karty kolorami i porząd­kować w ich obrębie według starszeń­stwa.

W programie symulującym rozdanie kart do brydża talia 52 kart może być potrakto­wana jako lista jednokie­runkowa lub wektor. Kod programu będzie bardziej zrozu­miały, gdy zdefiniujemy trzy typy wylicze­niowe symboli­zujące cztery kolory kart i ich wysokości w kolej­ności od najniż­szych do najwyż­szych wartości oraz czterech graczy:

enum Kolor { Trefl, Karo, Kier, Pik };

enum Wysok { Dwojka, Trojka, Czworka, Piatka, Szostka, Siodemka, Osemka,
             Dziewiatka, Dziesiatka, Walet, Dama, Krol, As };

enum Gracz { West, North, East, South };

Wartościami stałych wyszczególnionych w nawiasach {} są liczby całkowite. Jeśli nie są określone jak w rozpatry­wanym przypadku, są nimi kolejne liczby od zera wzwyż. W prezento­wanych na niniejszej witrynie programach używana jest tylko pierwsza i ostatnia ze stałych typu Wysok, dlatego jego definicja mogłaby zostać skrócona do postaci:

enum Wysok { Dwojka, As = 12 };

Lista jednokierunkowa kart i jej tasowanie

Elementy listy jednokierunkowej wyobraża­jącej karty w programie będą zawierać po trzy składniki: kolor karty, jej wysokość i wska­źnik na następny element listy. Definiując ich strukturę, od razu dekla­rujemy wskaźnik na początek talii i tablicę czterech wskaźników na początki układów kart na ręku każdego gracza:

struct Karta
{
    Kolor kol;
    Wysok wys;
    Karta *nas;
} *talia = NULL, *gracz[] = { NULL, NULL, NULL, NULL };

Wstępnie wszystkie listy są puste. Wygenero­wanie listy reprezen­tującej pełną talię kart uporządko­waną według koloru od trefla do pika, a w ramach kolorów od dwójki do asa, jest operacją bardzo prostą. Używając dwóch zmiennych pomocni­czych k (kolor) i w (wysokość) typu całko­witego, tworzymy elementy typu Karta w odwro­tnej kolejności i wstawiamy je na początek listy:

void zacznij()
{
    Karta *p;
    for (int k = Pik; k >= Trefl; k--)
        for (int w = As; w >= Dwojka; w--)
        {
            (p = new Karta)->kol = Kolor(k);
            p->wys = Wysok(w);
            p->nas = talia;
            talia = p;
        }
}

Zanim karty zostaną rozdane, należy je potasować. Proces ten można zorgani­zować poprzez wielo­krotne losowanie karty talii i przekła­danie jej na początek. Ponieważ operacja usuwania następnika elementu listy jest łatwa do sformu­łowania, możemy losować element spośród 51 elementów listy z zakresu od pierwszego do przedosta­tniego, po czym przekładać na początek listy element znajdu­jący się bezpo­średnio za wyloso­wanym. W poniższym sformu­łowaniu funkcji tasowania losowanie karty i przesu­wanie jej następnika na początek talii powta­rzamy od 100 do 1000 razy.

void tasuj()
{
    Karta *p, *q;
    for (int i = rand() % 901; i > -100; i--)
    {
        p = talia;
        for (int k = rand() % 51; k-- > 0; p = p->nas)
            ;
        p->nas = (q = p->nas)->nas;
        q->nas = talia;
        talia = q;
    }
}

W każdym kroku pętli zewnętrznej wskaźnik p przesuwamy wzdłuż listy co najwyżej 50 razy, począwszy od jej początku. Koniec listy nie zostanie nigdy przez p osiągnięty. Oznacza to, że po zakoń­czeniu pętli wewnę­trznej element *p ma nastę­pnik, który nie jest pierwszym elementem listy. Do jego identy­fikacji używamy pomocni­czego wskaźnika q o wartości p->nas. Usunięcie elementu *q z listy i wsta­wienie go na jej początek sprowadza się do prostych uaktu­alnień pól nas struktur *p*q oraz wskaźnika talia.

Rozdanie kart czterem graczom

Przejdźmy teraz do zaprogramowania operacji rozdawania kart potaso­wanej talii czterem graczom. Przyjmiemy, że rozdającym jest gracz S, który rozdaje karty po jednej zgodnie z ruchem wskazówek zegara, zaczy­nając od gracza W. Operacja polega na usuwaniu początko­wego elementu talii i wsta­wianiu go do listy kolejnego gracza. Postępo­wanie to kontynu­ujemy aż do wyczer­pania talii, zmieniając cykli­cznie graczy:

void rozdaj()
{
    Karta *p;
    for (int g = West; talia != NULL; )
    {
        talia = (p = talia)->nas;
        wstaw(p, gracz[g]);
        if (g < South)
            g++;
        else
            g = West;
    }
}

Kluczową rolę odgrywa tu funkcja wstaw, która element wskazy­wany przez wskaźnik p wstawia do listy kart gracza g. Sensowne wydaje się przyjęcie ambitnego założenia, że lista jest uporządko­wana według malejących wartości klucza kolor+wysokość karty, wszak nikt nie gra w brydża, nie mając w ręku uporządko­wanych kart. Uporządko­wanie listy uzyskuje się poprzez wstawianie nowych elementów w odpo­wiednie jej miejsce. Dokładniej mówiąc, szuka się takich dwóch kolejnych elementów *a*b, pomiędzy którymi ma być wstawiony nowy element *p. Algorytm wyszuki­wania właściwego miejsca wstawienia polega na przebie­ganiu listy parą wskaźników ab w ten sposób, że element *a poprzedza element *b. Gdy okaże się, że klucz elementu *p jest większy od klucza elementu *b, miejsce wstawienia zostało znalezione (rys.).

Należy bardzo ostrożnie formułować warunek kontynu­acji przeszuki­wania, aby uniknąć przykrego błędu adreso­wania pamięci. Ponadto trzeba przewidzieć dwa skrajne przypadki wstawiania elementu na początek lub koniec listy. Funkcja wstaw uwzglę­dniająca wszystkie te okoli­czności może wyglądać następu­jąco:

void wstaw(Karta *p, Karta *&poc)
{
    Karta *a = NULL, *b = poc;
    while (b != NULL && (p->kol < b->kol || (p->kol == b->kol && p->wys < b->wys)))
        b = (a = b)->nas;
    p->nas = b;
    if (a != NULL)
        a->nas = p;
    else
        poc = p;
}

Wstępnie wartością zmiennej a jest wskaźnik pusty, a wartością zmiennej b wskaźnik na początek listy. Odpowiada to sytuacji, w której element *p jest wstawiany na początku listy. Następnie wskaźniki a i b są przesu­wane wzdłuż listy w celu znale­zienia właściwego miejsca wstawienia. Warunek kontynuacji pętli while jest nieco złożony, składa się z dwóch czynników:

Kolejność tych czynników jest bardzo istotna. Jako pierwsze musi być wykonane sprawdzenie, czy lista się nie skończyła, bo jeśli tak, nie ma sensu porówny­wanie klucza wstawia­nego elementu z kluczem elementu nieistnie­jącego.

Po znalezieniu odpowiedniego miejsca element *p jest wstawiany do listy. Najpierw określa się, że jego następni­kiem jest *b (rys. powyżej z lewej). Zauważmy, że realizu­jące tę operację przypisanie zadziała prawidłowo także w sytuacji, gdy element jest wstawiany na koniec listy, tj. gdy b jest wskaźnikiem pustym. Następnie sprawdza się, czy element *p jest wstawiany za jakimś elementem listy, czy na jej początek. Decyduje o tym wskaźnik a. Jeżeli nie jest pusty, element *p jest wstawiany za elementem *a (rys. powyżej z prawej), a w przeciwnym razie na początek listy kart gracza wskazy­wany przez zmienną poc przekazaną funkcji wstaw przez referencję. Gdyby była przekazana przez wartość, wstawianie elementów do list graczy nie byłoby odnoto­wywane w tablicy globalnej gracz, co prowadzi­łoby do gubienia elementów reprezen­tujących karty i wycieku pamięci.

Program w C++ (lista)

Pełny program konsolowy w języku C++ symulujący rozdanie kart do gry w brydża jest przedsta­wiony na poniższym listingu. Oprócz omówionych powyżej czterech funkcji i funkcji głównej program zawiera funkcję ukazującą na ekranie wygene­rowany układ kart gracza i zwalnia­jącą pamięć reprezen­tującej ten układ listy. Lista główna określona przez wskaźnik talia jest po rozdaniu kart pusta, więc nie wymaga zwalniania.

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

using namespace std;

enum Kolor { Trefl, Karo, Kier, Pik };

enum Wysok { Dwojka, Trojka, Czworka, Piatka, Szostka, Siodemka, Osemka,
             Dziewiatka, Dziesiatka, Walet, Dama, Krol, As };

enum Gracz { West, North, East, South };

struct Karta
{
    Kolor kol;
    Wysok wys;
    Karta *nas;
} *talia = NULL, *gracz[] = { NULL, NULL, NULL, NULL };

void zacznij()
{
    Karta *p;
    for (int k = Pik; k >= Trefl; k--)
        for (int w = As; w >= Dwojka; w--)
        {
            (p = new Karta)->kol = Kolor(k);
            p->wys = Wysok(w);
            p->nas = talia;
            talia = p;
        }
}

void tasuj()
{
    Karta *p, *q;
    for (int i = rand() % 901; i > -100; i--)
    {
        p = talia;
        for (int k = rand() % 51; k-- > 0; p = p->nas)
            ;
        p->nas = (q = p->nas)->nas;
        q->nas = talia;
        talia = q;
    }
}

void wstaw(Karta *p, Karta *&poc)
{
    Karta *a = NULL, *b = poc;
    while (b != NULL && (p->kol < b->kol || (p->kol == b->kol && p->wys < b->wys)))
        b = (a = b)->nas;
    p->nas = b;
    if (a != NULL)
        a->nas = p;
    else
        poc = p;
}

void rozdaj()
{
    Karta *p;
    for (int g = West; talia != NULL; )
    {
        talia = (p = talia)->nas;
        wstaw(p, gracz[g]);
        if (g < South)
            g++;
        else
            g = West;
    }
}

void pokaz(Karta *p, int x, int y)
{
    static string SK[] = { "Trefl", "Karo", "Kier", "Pik" };
    static string SW[] = { "2", "3", "4", "5", "6", "7", "8", "9", "10",
                           "W", "D", "K", "A" };
    for (int k = Pik; k >= Trefl; k--)
    {
        gotoxy(x, y++);
        cout << setw(5) << SK[k] << ": ";
        for ( ; p != NULL && p->kol == k; p = p->nas)
            cout << " " << SW[p->wys];
    }
}

void zwolnij(Karta *&poc)
{
    Karta *p;
    while (poc != NULL)
    {
        poc = (p = poc)->nas;
        delete p;
    }
}

int main()
{
    srand(unsigned(time(NULL)));
    do
    {
        zacznij();
        tasuj();
        rozdaj();
        clrscr();
        pokaz(gracz[North], 23, 3);
        pokaz(gracz[West], 1, 9);
        pokaz(gracz[East], 45, 9);
        pokaz(gracz[South], 23, 15);
        zwolnij(gracz[North]);
        zwolnij(gracz[West]);
        zwolnij(gracz[East]);
        zwolnij(gracz[South]);
        gotoxy(1, 21);
        cout << "Esc - koniec\nInny klawisz - następne rozdanie";
    } while (_getch() != 27);
    return 0;
}

Funkcja pokaz wyświetla w czterech wierszach, począwszy od podanej pozycji, układ kart gracza reprezen­towany przez listę wskazywaną przez argu­ment p. W pierwszym wierszu pokazuje pliki, w drugim kiery, w trzecim kara, a w czwartym trefle, wypisując po nazwie koloru i dwukropku wysokości kart w tym kolorze. Uporządko­wanie listy według malejącego klucza kolor+wysokość ułatwia wydruk wiersza: wysokości kart są wypisy­wane, dopóki nie napotkano końca listy i karta ma kolor zgodny z kolorem podanym na początku wiersza. Cztero­krotne wywołanie funkcji pokaz z odpowie­dnimi argumen­tami powoduje utworzenie typowego obrazu stolika brydżo­wego z układami kart czterech graczy ustawio­nymi zgodnie z kierun­kami stron świata.

Po wygenerowaniu i pokazaniu rozkładu rozdania i zwolnieniu przydzie­lonej dynami­cznie pamięci program czeka na naciśnięcie klawisza. Gdy użytko­wnik naciśnie Esc, program kończy działanie, a gdy inny klawisz, generuje nowe rozdanie. Przekazanie wskaźnika przez referencję do funkcji zwolnij określa­jącego początek listy jest konieczne. Gdyby został przekazany przez wartość, listy zostałyby także zwolnione, lecz przy genero­waniu kolejnego rozdania doszłoby do załamania programu, gdyż próbowałby on działać na nieprzy­dzielonej mu pamięci.

Uwaga. Kompilatory MinGW C++ i Visual C++ wymagają dodania do projektu programu modułu obsługi okna konsoli bconio zawiera­jącego implemen­tacje wybranych elementów biblio­teki conio Borland C++. Włączenie pliku nagłów­kowego string jest niezbędne jedynie w przy­padku kompila­tora Visual C++.

A oto przykładowy rozkład kart wygenerowany przez program:

Program w C++ (wersja 2, wektor)

W drugiej wersji programu symulującego rozdanie kart do gry w brydża zamiast list jednokie­runkowych użyjemy obiektów klasy vector ze standar­dowej biblio­teki szablonów STL reprezen­tujących talię kart i układy kart czterech graczy. Ich elementami są struktury złożone z dwóch pól typów wylicze­niowych KolorWysok (kolor i wysokość karty) zdefinio­wanych na początku niniejszej witryny. Oto definicja tej struktury i potrze­bnych wektorów:

struct Karta
{
    Kolor kol;
    Wysok wys;
};

vector<Karta> talia, gracz[4];

Nową wersję programu można łatwo sformułować, przekształ­cając kolejno funkcje jego poprze­dniej wersji, by działały nie na listach, lecz na wektorach. W funkcji zacznij generu­jącej uporząd­kowaną talię kart od najniższej do najwyższej elementy reprezen­tujące karty wygodnie jest dopisywać na końcu wektora za pomocą metody push_back klasy vector. Oznacza to, że powinny być one tworzone w kolej­ności odwrotnej niż poptrze­dnio – od trefla do pika, a w ramach kolorów – od dwójki do asa:

void zacznij()
{
    Karta karta;
    for (int k = Trefl; k <= Pik; k++)
        for (int w = Dwojka; w <= As; w++)
        {
            karta.kol = Kolor(k);
            karta.wys = Wysok(w);
            talia.push_back(karta);
        }
}

W celu potasowania uporządkowanej talii posłużymy się prostą metodą polega­jącą na zamianie miejscami każdego elementu wektora, od pierwszego do ostatniego, z innym jego elementem wybieranym za każdym razem losowo. Do przesta­wianych elementów wygodnie jest odwoływać się za pomocą indeksów:

void tasuj()
{
    for (unsigned int i = 0; i < talia.size(); i++)
    {
        unsigned int j = rand() % talia.size();
        if (i != j) swap(talia[i], talia[j]);
    }
}

Funkcja szablonowa swap dostępna w biblio­tece STL zamienia miejscami dwa przekazane jej przez referencję elementy tego samego typu. W rozpatry­wanym przypadku jej wywołanie można zastąpić ciągiem trzech instrukcji:

Karta temp = talia[i];
talia[i] = talia[j];
talia[j] = temp;

Rozdawanie potasowanych kart polega na sekwen­cyjnym usuwaniu pierwszego elementu wektora talia i wsta­wianiu go w odpo­wiednie miejsce wektora gracz[g] reprezen­tującego układ kart kolejnego w zamkniętym cyklu gracza g. Zarówno jedna, jak i druga z tych operacji wymaga użycia iteratora. Odkładając na później rozwa­żania dotyczące wstawiania elementu do wektora, funkcję rozdawania kart formu­łujemy następu­jąco:

void rozdaj()
{
    for (int g = West; !talia.empty(); )
    {
        wstaw(talia.front(), gracz[g]);
        talia.erase(talia.begin());
        if (g < South)
            g++;
        else
            g = West;
    }
}

Metoda front klasy vector udostępnia pierwszy element wektora, begin zwraca wskazu­jący na niego iterator, a erase usuwa ten element z wektora. Należy zauważyć, że zanim pierwszy element wektora talia zostanie usunięty, jest najpierw wstawiany (kopiowany) do wektora gracz[g]. Podczas usuwania zostaje bowiem nieodwra­calnie zamazany przez następny element, jeśli oczywiście nie jest ostatnim elementem wektora, a nawet gdy jest ostatnim, po usunięciu dostęp do niego zostaje i tak utracony.

Operację rozdawania kart można przyśpieszyć poprzez wybór elementów wektora w odwrotnej kolejności. Użyte­cznymi byłyby wówczas metody back (udostę­pnienie ostatniego elementu wektora) i pop_back (usunięcie ostatniego elementu bez przesu­wania innych elementów). Uzyskane korzyści czasowe nie miałyby tu żadnego znaczenia, toteż pozostajemy przy pierwszym, bardziej naturalnym rozwią­zaniu.

Wstawienie nowego elementu (kopii pierwszego elementu talii) do wektora reprezentu­jącego uporząd­kowany malejąco układ kart gracza wymaga poruszania się za pomocą iteratora po kolejnych elementach od początku ku końcowi celem znale­zienia odpowie­dniego miejsca wstawienia. Przeszuki­wanie jest kontunu­owane dopóty, dopóki iterator nie wskazuje poza ostatni element wektora i klucz kolor+wysokość wstawianej karty jest niższy od klucza elementu wskazy­wanego przez iterator:

void wstaw(Karta karta, vector<Karta> &gracz)
{
    vector<Karta>::iterator it = gracz.begin();
    while (it != gracz.end() &&
          (karta.kol < it->kol || (karta.kol == it->kol && karta.wys < it->wys)))
        it++;
    gracz.insert(it, karta);
}

Przypomnijmy, że metoda end klasy vector zwraca iterator wskazujący poza ostatni, nieistnie­jący element wektora. Zatem przesu­wanie iteratora kończy się, gdy wstawiany element ma klucz niższy od kluczy wszystkich elementów wektora, bądź gdy ma klucz wyższy od klucza elementu wskazy­wanego przez iterator. W obu przypadkach iterator wskazuje na właściwe miejsce wstawienia, toteż zostaje wykorzy­stany w metodzie insert, która wstawia w to miejsce wektora reprezen­tującego układ kart gracza nowy element.

Ostateczna wersja programu symulującego rozdanie kart do gry w brydża i korzysta­jącego z kontenerów klasy vector do implemen­tacji talii kart i układów kart graczy jest przedsta­wiona na poniższym listingu. Wywoływana cztero­krotnie w funkcji main metoda clear usuwa wszystkie elementy wektorów wyobraża­jących układy kart graczy.

#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#include "bconio.h"
#include <vector>

using namespace std;

enum Kolor { Trefl, Karo, Kier, Pik };

enum Wysok { Dwojka, Trojka, Czworka, Piatka, Szostka, Siodemka, Osemka,
             Dziewiatka, Dziesiatka, Walet, Dama, Krol, As };

enum Gracz { West, North, East, South };

struct Karta
{
    Kolor kol;
    Wysok wys;
};

vector<Karta> talia, gracz[4];

void zacznij()
{
    Karta karta;
    for (int k = Trefl; k <= Pik; k++)
        for (int w = Dwojka; w <= As; w++)
        {
            karta.kol = Kolor(k);
            karta.wys = Wysok(w);
            talia.push_back(karta);
        }
}

void tasuj()
{
    for (unsigned int i = 0; i < talia.size(); i++)
    {
        unsigned int j = rand() % talia.size();
        if (i != j) swap(talia[i], talia[j]);
    }
}

void wstaw(Karta karta, vector<Karta> &gracz)
{
    vector<Karta>::iterator it = gracz.begin();
    while (it != gracz.end() &&
          (karta.kol < it->kol || (karta.kol == it->kol && karta.wys < it->wys)))
        it++;
    gracz.insert(it, karta);
}

void rozdaj()
{
    for (int g = West; !talia.empty(); )
    {
        wstaw(talia.front(), gracz[g]);
        talia.erase(talia.begin());
        if (g < South)
            g++;
        else
            g = West;
    }
}

void pokaz(vector<Karta> &gracz, int x, int y)
{
    static string SK[] = { "Trefl", "Karo", "Kier", "Pik" };
    static string SW[] = { "2", "3", "4", "5", "6", "7", "8", "9", "10",
                           "W", "D", "K", "A" };
    unsigned int p = 0;
    for (int k = Pik; k >= Trefl; k--)
    {
        gotoxy(x, y++);
        cout << setw(5) << SK[k] << ": ";
        for ( ; p < gracz.size() && gracz[p].kol == k; p++)
            cout << " " << SW[gracz[p].wys];
    }
}

int main()
{
    srand(unsigned(time(NULL)));
    do
    {
        zacznij();
        tasuj();
        rozdaj();
        clrscr();
        pokaz(gracz[North], 23, 3);
        pokaz(gracz[West], 1, 9);
        pokaz(gracz[East], 45, 9);
        pokaz(gracz[South], 23, 15);
        gracz[North].clear();
        gracz[West].clear();
        gracz[East].clear();
        gracz[South].clear();
        gotoxy(1, 21);
        cout << "Esc - koniec\nInny klawisz - następne rozdanie";
    } while (_getch() != 27);
    return 0;
}

Opracowanie przykładu: grudzień 2019