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

Przykład C++

Współczynniki Newtona Algorytmy Trójkąt Pascala Program w C++ Wskaźniki a tablice Tablice dynamiczne Program w C++ (wersja 2) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Współczynniki Newtona

W wielu zastosowaniach matematycznych i informatycznych wystę­pują współczyn­niki Newtona, zwane również symbo­lami Newtona lub współczyn­nikami dwumien­nymi (dwumia­nowymi) Newtona. Dla dowolnej nieuje­mnej liczby całko­witej nk = 0, 1, ..., n defi­niuje się je jako

gdzie n! oznacza funkcję silnia:

Algorytmy

Algorytm obliczania współczynników Newtona wykorzy­stujący funkcję silnia wydaje się elegancki, ale prakty­cznie jest bezuży­teczny ze względu na jej bardzo wielkie wartości. Nawet dla małych wartości argu­mentu są one zbyt duże, by zmieścić się w komputerowym prze­dziale liczb całkowitych:

Wyznaczanie współczynników Newtona bez użycia silni może być w językach C i C++ opisane za pomocą funkcji typu całko­witego zależnej od dwóch argu­mentów całko­witych:

int C(int n, int k)
{
    int p = 1;
    for (int i = 1; i <= k; i++)
        p = p * (n - i + 1) / i;
    return p;
}

Obliczenia są wykonywane itera­cyjnie w pętli for. Zmienna lokalna p, której wstę­pnie przypi­sano wartość 1 (ele­ment neutra­lny ze względu na mnożenie), służy do wyli­czenia ilo­czynu według schematu:

p = p * kolejny_czynnik;

Operatory * i / mają ten sam prio­rytet, w ich grupie obowią­zuje łączność lewo­stronna (p. 4). Wynika stąd, że chociaż czynni­kami są tu wyra­żenia (n-i+1)/i, wynik cząstkowy jest najpierw mnożony przez n-i+1, a potem dzie­lony przez i, dzięki czemu nie jest obci­nany przy dzie­leniu całko­witym. Korzysta się tu ze znanej właści­wości liczb całko­witych, że w ciągu dwóch kolej­nych takich liczb jedna jest podzielna przez 2, w ciągu trzech kolej­nych jedna jest podzielna przez 3, a inna przez 2 itd. Warto jeszcze zwrócić uwagę, że nie wolno tu skrócić instrukcji objętej pętlą:

p *= (n - i + 1) / i;

Prowadziłoby to bowiem do obcinania wyniku! Można nato­miast ulepszyć algorytm, korzy­stając z własności syme­trii współczyn­ników Newtona:

Jedna ze stron tej równości może po rozwi­nięciu do ilo­czynu zawie­rać mniej czynników niż druga, co pozwala na wybór lepszego wariantu przed reali­zacją pętli:

if (k > n - k) k = n - k;

Nieznaczne korzyści czasowe uzyska się również poprzez zwiększenie n o 1 przed pętlą zamiast robić to w jej każdym kroku. Oto ulepszona wersja algorytmu:

int C(int n, int k)
{
    int p = 1;
    if (k > n - k)
        k = n - k;
    n++;
    for (int i = 1; i <= k; i++)
        p = p * (n - i) / i;
    return p;
}

Należy tu podkreślić, że obydwa argumenty n i kprzeka­zywane do funkcji przez wartość. Oznacza to, że są trakto­wane wewnątrz funkcji jak zmienne lokalne o wartościach wyzna­czonych w momencie jej wywo­łania, toteż zmiany ich wartości nie mają poza nią żadnego znaczenia.

Inna metoda wyznaczania współczyn­ników Newtona, wynikająca ze znanego związku rekuren­cyjnego

ma postać:

int C(int n, int k)
{
    if (k == 0 || k == n)
        return 1;
    else
        return C(n - 1, k - 1) + C(n - 1, k);
}

Funkcja jest podprogramem rekurencyjnym, ponieważ wywo­łuje samą siebie. W porównaniu z wersją itera­cyjną jej kod jest znacznie prostszy i przejrzystszy. Należy jednak zdawać sobie sprawę z tego, że każde wywo­łanie funkcji wymaga pewnego obszaru pamięci, zwanego ramką stosu (stack frame), w której są pamię­tane wartości argu­mentów, zmienne lokalne i adres miejsca, do którego ma nastąpić powrót po wykonaniu funkcji. To obcią­żenie pamięci może być wyraźnie odczu­walne w przypadku podpro­gramów rekuren­cyjnych, ponieważ dla każdego nowego wywo­łania, przy niezakoń­czonych wywoła­niach poprze­dnich, do ramek zarezer­wowanych poprze­dnio jest dołączana nowa ramka. Ważne jest więc, by głębo­kość wywołań rekuren­cyjnych była względnie mała.

Trójkąt Pascala

Jeżeli w kolejnych wierszach ustawimy współ­czynniki Newtona tak, że w wierszu o numerze n wystąpią wszystkie odpo­wiadające tej liczbie współ­czynniki, otrzymamy tzw. trójkąt Pascala:

0                      1
1                    1   1
2                  1   2   1
3                1   3   3   1
4              1   4   6   4   1
5            1   5  10  10   5   1
6          1   6  15  20  15   6   1
7        1   7  21  35  35  21   7   1
8      1   8  28  56  70  56  28   8   1
.  .  .  .  .  .  .  .  .  .  .  .  .  .

Jego konstrukcja jest wobec poda­nego wyżej wzoru rekuren­cyjnego bardzo prosta. Pierwszy wiersz ma jeden współ­czynnik równy jeden. Każdy nastę­pny powstaje w ten sposób, że współ­czynniki skrajne są jedyn­kami, zaś wewnę­trzne sumą dwóch sąsie­dnich współ­czynników wiersza poprze­dniego: tego na lewo skos i tego na prawo skos.

Program w C++

Wyprowadzanie trójkąta Pascala do okna konsoli wymaga odpowie­dniego rozpla­nowania wydruku. Przyj­mijmy, że współ­czynniki Newtona będą zajmo­wały pola o szerokości 6 znaków łącznie ze spacją oddzie­lającą jedną liczbę od drugiej. Ograni­czenie to oznacza, że mogą być one liczbami co najwyżej 5 cyfrowymi. Proste ćwiczenie na kalku­latorze lub kompu­terze prowadzi do wniosku, że n nie może być większe od 19, gdyż w przeciwnym razie część współ­czynników przekra­czałaby zakres pola, zaburzając trójkątny układ wydruku.

Na początku każdego wiersza chcemy wypro­wadzić jego numer n do pola dwuzna­kowego, a po odpo­wiednim odstępie współ­czynniki tego wiersza. Zauważmy, że współ­czynniki wiersza o numerze wyższym od zera są przesu­nięte w lewo o 3 znaki względem współ­czynników wiersza poprze­dniego. Zatem liczba spacji poprzedza­jących pierwszy współ­czynnik wiersza jest równa wartości wyra­żenia 3*(nMax-n), w którym

Rozważania te prowadzą do następującego programu w C++, który wczytuje z klawiatury maksymalną wartość n do zmiennej nMax i układa w trójkąt Pascala wyzna­czane rekuren­cyjnie współczyn­niki Newtona:

#include <iostream>
#include <iomanip>

using namespace std;

int C(int n, int k)
{
    if (k == 0 || k == n)
        return 1;
    else
        return C(n - 1, k - 1) + C(n - 1, k);
}

int main()
{
    int nMax;
    cout << "Trojkat Pascala\n---------------\nnMax (0-19): ";
    cin >> nMax;
    cout << "---------------\n";
    for (int n = 0; n <= nMax; n++)
    {
        cout << setw(2) << n << setw(3 * (nMax - n)) << "";
        for (int k = 0; k <= n; k++)
            cout << setw(6) << C(n, k);
        cout << endl;
    }
    return 0;
}

Kod źródłowy i projekt programu:

A oto przykładowe wyniki wykonania wersji Visual C++ programu (standar­dowe okno konsoli zostało powię­kszone, by widoczny był cały trójkąt Pascala):

Wskaźniki a tablice

Wskaźnik jest adresem miejsca pamięci, w którym jest przecho­wywana wartość określo­nego typu. Wskaźnik na zmien­ną jest zazwyczaj tworzony za pomocą operatora &. Na przykład w instrukcji scanf wczytu­jącej wartość zmiennej n typu int jest wymagany zapis &n, czyli wskaźnik na tę zmienną:

scanf("%d", &n);

Zmienne wskaźnikowe deklarujemy, poprzedając ich nazwy operatorem * (gwiazdka). Z kolei operator * przed nazwą zmiennej wskaźni­kowej oznacza wyłuska­nie (wydo­bycie, pobranie) wartości wskazy­wanej przez tę zmienną. Na przy­kład w wyniku wyko­nania kodu

int t = 1284;
int *p = &t;
cout << *p << endl;

na wyjściu pojawi się liczba 1284. Wartością zmiennej p jest bowiem wskaźnik na zmienną t, więc wyłu­skaną przez wyra­żenie *p wartością jest 1284 (wartość zmiennej t).

Istnieje ścisła odpowiedniość między tablicami i wskaźnikami przeja­wiająca się w dowol­ności używa­nia inde­ksów i wska­źników w kodowaniu operacji dotyczą­cych przetwa­rzania tablic. Wynika ona z dwóch podsta­wowych reguł:

Rozważmy dla przykładu tablicę jednowymiarową

double x[10];

złożoną z ułożonych obok siebie 10 elementów typu double ponume­rowanych warto­ściami indeksu od 0 to 9. Jak wiadomo, dostęp do elementu tablicy określa jej nazwa i indeks umie­szczony w nawiasach kwadra­towych (stąd nazwa zmienna inde­ksowana), np. x[4] czy x[i+j]. Stosując jednoargu­mentowe opera­tory & i *, otrzymu­jemy równo­ważne formy wyrażeń:

Adres elementu Wartość elementu
x     i    &x[0] x[0]   i   *x
x+1   i    &x[1] x[1]   i   *(x+1)
x+2   i    &x[2] x[2]   i   *(x+2)
. . . . . . . . . . . . . . . . . . . . . . . .
x+k   i    &x[k] x[k]   i   *(x+k)
. . . . . . . . . . . . . . . . . . . . . . . .

Dużym zaskoczeniem, nawet dla wielu progra­mistów C i C++, jest fakt, że zamiast wyra­żenia x[k] określa­jącego k-ty element tablicy x można użyć dziwa­cznego wyra­żenia k[x]. Kompi­lator zastę­puje odwo­łanie x[k] do ele­mentu tablicy wyraże­niem wskaźni­kowym *(x+k), a ponieważ to z kolei jest równo­ważne wyra­żeniu *(k+x), bo doda­wanie jest prze­mienne, traktuje jako poprawne k[x].

Tablice o większej liczbie inde­ksów są nazy­wane tabli­cami wielowy­miarowymi. Pierwszy indeks tablicy dwuwy­miarowej jest nazywany jej numerem wiersza, drugi numerem kolumny, zaś sama tablica jest utożsa­miana z macierzą prosto­kątną w sensie matema­tycznym. Przykła­dowo, definicja

double a[4][5];

tworzy tablicę składającą się z czterech wierszy o indeksach od 0 do 3, z których każdy jest tablicą ele­menów typu double o indeksach od 0 do 4. Zapis a[i][j] oznacza ele­ment tej tablicy w i-tym wierszu i j-tej kolumnie. A jak wygląda równo­ważny mu zapis przy użyciu wska­źników? Oto wiodąca do niego analiza:

Wyrażenie Znaczenie
a tablica, wskaźnik na jej pierwszy z czterech wierszy
a+i wskaźnik na i-ty wiersz tablicy
*(a+i) i-ty wiersz tablicy, wskaźnik na jego pierwszy element
*(a+i)+j wskaźnik na j-ty element i-tego wiersza tablicy
*(*(a+i)+j) j-ty element i-tego wiersza tablicy, czyli a[i][j]

Uff!!! Lepiej nie używać wskaźników, ale nie zawsze jest to możliwe. Jak widać, dostęp do ele­mentu tablicy dwuwy­miarowej bez użycia indeksów wymaga podwój­nego wska­źnika ** (wska­źnik wskazu­jący na wska­źnik). Z tej analizy można również wysnuć wniosek, że w C++ tablice dwuwy­miarowe są pamię­tane wier­szami (w ogólności osta­tni indeks rośnie najszyb­ciej).

Tablice dynamiczne

Przytoczone wyżej przykłady dotyczyły tablic staty­cznych, których rozmiary są znane w trakcie tworzenia (kompi­lacji) programu. Nie jest możliwe okre­ślanie ich rozmia­rów podczas wyko­nania pro­gramu.

Uwaga. Kompilator MinGW C++ nie trzyma się standardu języka C++, zezwalając na definio­wanie tablicy, której rozmiar określa zmienna typu całko­witego. Wprowa­dzenie tego pseudoudo­godnienia przez twórców kompilatora jest godne ubolewania, a korzy­stanie z niego w nauce programo­wania powinno być zakazane, gdyż przeczy filozofii programo­wania, jest zbędnym i irytującym źródłem nieprzeno­śności oprogramo­wania.

Użycie wskaźników pozwala na uzyskanie tablic dynami­cznych, o rozmiarach których można zadecy­dować w czasie wyko­nania programu, a w przypadku tablic wielowy­miarowych można nawet wpływać na ich kształt, np. utworzyć tablicę trójkątną. Do przydziału pamięci służy ope­rator new, a do zwalniania jej operator delete. Można ich używać zarówno w wersji prostej (dla pojedyn­czych obiektów), jak i tabli­cowej. Operator delete w wersji prostej można zasto­sować tylko do wska­źnika przeka­zanego przez new w odnie­sieniu do pojedyn­czego obiektu, zaś delete[] do tablic. Aby utworzyć tablicę dynami­czną, należy zadekla­rować wska­źnik tego samego typu co ele­menty tablicy i przypisać mu adres obszaru pamięci przydzie­lonego tablicy za pomocą opera­tora new. Ze względu na odpowie­dniość między tablicami a wskaźni­kami do ele­menów tablicy dynami­cznej można odwo­ływać się jak do zmien­nych indekso­wanych, w których nazwą tablicy jest wska­źnik, nie trzeba ope­rować wskaźni­kami.

Poniższy przykład ilustruje użycie dwóch tablic dynami­cznych, których eleme­nty typu double repre­zentują współ­rzędne punktów płasz­czyzny. Liczba punktów, a po niej parami ich współ­rzędne, są wczyty­wane z klawia­tury. Gdyby użyć tablic staty­cznych, należa­łoby zarezer­wować dużą liczbę ich elemen­tów dla przy­padku pesymisty­cznego, który być może się pojawi. Takie rozwią­zanie byłoby nieefe­ktywne ze względu na wykorzy­stanie pamięci. Tablice dyna­miczne, tworzone po sprecy­zowaniu liczby punktów, pozwa­lają na rezer­wację obszaru pamięci o rozmiarze dopaso­wanym do potrzeb. Po wykorzy­staniu tablice są usuwane, zwol­niona pamięć może zostać użyta do innych celów.

int n;                        // liczba punktów (rozmiar tablic)
double *x, *y;                // wskaźniki tablic dynamicznych
cin >> n;                     // wczytanie rozmiaru tablic
x = new double[n];            // przydział pamięci tablicy x
y = new double[n];            // przydział pamięci tablicy y
for (int k = 0; k < n; k++)
    cin >> x[k] >> y[k];      // wczytanie współrzędnych x[k] i y[k]
. . .
delete[] x;                   // zwolnienie pamięci tablicy x
delete[] y;                   // zwolnienie pamięci tablicy y

Dwuwymiarowa tablica dynamiczna wymaga użycia podwój­nego wskaź­nika ** wskazu­jącego na typ jej elemen­tów. Najpierw należy przy­pisać mu adres tablicy wska­źników utwo­rzonej za pomocą opera­tora new dla pierw­szego wymiaru (liczby wierszy), a nastę­pnie każdemu z tych wska­źników należy przypisać adres utwo­rzonej tablicy ele­mentów typu docelo­wego dla dru­giego wymiaru (wiersz). Po wykorzy­staniu tablicy zajmo­wany przez nią obszar pamięci trzeba zwolnić w odwro­tnej kolej­ności: naj­pierw wszy­stkie tablice dru­giego wymiaru (wiersze), a potem tablicę wska­źników. Poniż­szy przy­kład prezen­tuje użycie tablicy dynami­cznej o wczyty­wanej z klawia­tury liczbie wierszy i kolumn.

int m, n;                     // liczba wierszy i kolumn tablicy
double **a;                   // wskaźnik tablicy dwuwymiarowej
cin >> m >> n;                // wczytanie liczby wierszy i kolumn
a = new double*[m];           // przydział pamięci dla tablicy wskaźników
for (int i = 0; i < m; i++)
    a[i] = new double[n];     // przydział pamięci dla wiersza tablicy
. . .
for (int i = 0; i < m; i++)
    delete[] a[i];            // zwolnienie pamięci wiersza tablicy
delete[] a;                   // zwolnienie pamięci tablicy wskaźników

Program w C++ (wersja 2)

W drugiej wersji programu tworzącego trójkąt Pascala skorzy­stamy ze wspo­mnianej wyżej zasady, że każdy jego skrajny współ­czynnik jest równy 1, a każdy wewnę­trzny jest sumą dwóch współ­czynników stoją­cych na lewo i na prawo od niego o jeden wiersz wyżej. Natu­ralnym wydaje się, aby trój­kątny układ współ­czynników był reprezen­towany przez trój­kątną tablicę dyna­miczną o elemen­tach typu int. Przyj­mijmy, że c jest jej nazwą. Oznacza to, że c jest wskaźni­kiem typu int** wskazu­jącym na jej ele­menty. Jeśli zmienna nMax określa maksy­malną wartość n wczyty­waną z klawia­tury, proces przy­działu pamięci tablicy można zapro­gramować następująco:

int nMax, **c;
cin >> nMax;
c = new int *[nMax + 1];         // przydział pamięci tablicy wskaźników
for (int n = 0; n <= nMax; n++)
    c[n] = new int[n + 1];       // przydział pamięci dla wiersza tablicy

Najpierw przydziela się pamięć dla tablicy wskaź­ników i przypisuje jej adres wskaźni­kowi c, a nastę­pnie przy­dziela się pamięć dla kolej­nych wierszy trójkąta Pascala i zapamię­tuje ich adresy w elemen­tach c[n] tablicy wskaź­ników. Liczba eleme­ntów wierszy nie jest stała: wiersz o inde­ksie 0 ma 1 ele­ment, wiersz 1 – 2 ele­menty, wiersz 2 – 3 ele­menty itd. W efe­kcie utwo­rzona tablica dwuwy­miarowa nie jest prosto­kątna, lecz trój­kątna. Warto­ści jej elemen­tów obli­czamy wg wspomnia­nego wyżej algo­rytmu:

for (int n = 0; n <= nMax; n++)
{
    c[n][0] = c[n][n] = 1;                 // skrajne współczynniki mają wartość 1
    for (int k = 1; k < n; k++)
        c[n][k] = c[n-1][k-1] + c[n-1][k]; // wewnętrzne są sumą dwóch stojących wyżej
}

Pełny kod źródłowy programu jest zaprezen­towany poni­żej. Oprócz funkcji main pro­gram ma cztery inne pro­ste funkcje. Każda ma suge­stywną nazwę, nawet nie ma potrzeby komen­towania, za jakie zada­nia odpo­wiadają. Dla ułatwie­nia dostępu do danych wszys­tkie fun­kcje są bezargu­mentowe, zaś dane glo­balne. Pro­gram mógłby być napi­sany w sposób bar­dziej zwarty, ale byłby mniej czytelny.

#include <iostream>
#include <iomanip>

using namespace std;

const int NMAX = 19;
int nMax, **c;

void Przydzial_pamieci()
{
    c = new int *[nMax + 1];
    for (int n = 0; n <= nMax; n++)
        c[n] = new int[n + 1];
}

void Obliczenia()
{
    for (int n = 0; n <= nMax; n++)
    {
        c[n][0] = c[n][n] = 1;
        for (int k = 1; k < n; k++)
            c[n][k] = c[n - 1][k - 1] + c[n - 1][k];
    }
}

void Drukowanie()
{
    for (int n = 0; n <= nMax; n++)
    {
        cout << setw(2) << n << setw(3 * (nMax - n)) << "";
        for (int k = 1; k < n; k++)
            cout << setw(6) << c[n][k];
        cout << endl;
    }
}

void Zwolnienie_pamieci()
{
    for (int n = 0; n <= nMax; n++)
        delete[] c[n];
    delete[] c;
}

int main()
{
    cout << "Trojkat Pascala\n---------------\nnMax (0-" << NMAX << "): ";
    cin >> nMax;
    cout << "---------------\n";
    if (nMax < 0 || nMax > NMAX)
    {
        cout << "Nieprawidlowy zakres nMax\n";
        return 1;
    }
    Przydzial_pamieci();
    Obliczenia();
    Drukowanie();
    Zwolnienie_pamieci();
    return 0;
}

Funkcja główna po wczytaniu maksymalnej wartości n sprawdza, czy mieści się ona w dopusz­czalnym zakre­sie. Jeśli nie, wypro­wadza stoso­wny komu­nikat i kończy dzia­łanie kodem powrotu 1 oznacza­jącym nienor­malne zakoń­czenie pro­gramu. W przeci­wnym razie funkcja przy­dziela pamięć dynami­cznej tablicy trój­kątnej reprezen­tującej trój­kąt Pascala, obli­cza wartości jej elemen­tów, dru­kuje trój­kąt Pascala w oknie konsoli, zwal­nia pamięć tablicy dynami­cznej i kończy dzia­łanie kodem powrotu 0 wskazu­jącym na pomyślne wyko­nanie programu.

Kod źródłowy i projekt programu:


Opracowanie przykładu: sierpień 2018