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

Przykład C#

Współczynniki Newtona Algorytmy Trójkąt Pascala Program w Visual C# Tablice dwuwymiarowe Tablice tablic Program w Visual C# (wersja 2) Poprzedni przykład Następny przykład Program w C++ Kontakt

Współczynniki Newtona

Występujące w wielu zastosowaniach matematy­cznych i informaty­cznych współczyn­niki Newtona, nazy­wane również symbo­lami Newtona lub współczyn­nikami dwumien­nymi (dwumia­nowymi) Newtona, defi­niuje się dla dowol­nej nieuje­mnej liczby całko­witej nk = 0, 1, ..., n za pomocą wzoru

w którym n! oznacza funkcję silnia:

Algorytmy

Algorytm obliczania współczynników Newtona z wykorzy­staniem silni jest prakty­cznie 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 kompu­terowym prze­dziale liczb całko­witych (rys.):

Wyznaczanie współczynników Newtona bez użycia silni może być w języku C# opisane za pomocą metody itera­cyjnej 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;
}

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 w pętli for ilo­czynu według schematu:

p = p * kolejny_czynnik;

Operatory * i / mają ten sam prio­rytet, a w ich grupie obowią­zuje łączność lewo­stronna (p. 3). W następstwie tego, pomimo że ­czynni­kami są 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. Wynika to ze znanej właści­wości liczb całko­witych: 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 zwrócić uwagę, że nie wolno tu skrócić instrukcji objętej pętlą do postaci:

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 metody przez wartość. Oznacza to, że są one trakto­wane wewnątrz metody jak zmienne lokalne o wartościach wyzna­czonych w momencie jej wywo­łania, toteż zmiany ich wartości nie mają poza nią żadnego znaczenia.

Inny sposób wyznaczania współczyn­ników Newtona, wynikający ze znanego związku rekuren­cyjnego

prowadzi do metody

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

Metoda jest rekurencyjna, 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 metody 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 metody. 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
.  .  .  .  .  .  .  .  .  .  .  .  .  .

Konstrukcja trójkąta opiera się na poda­nym wyżej wzorze rekuren­cyjnym. W pierw­szym wierszu znajduje się jedynka stano­wiąca wierz­chołek trój­kąta. Każdy nastę­pny wiersz powstaje w ten sposób, że współ­czynniki skrajne są jedyn­kami, zaś wewnę­trzne sumą dwóch współ­czynników wiersza poprze­dniego: tego na lewo skos i tego na prawo skos.

Program w Visual C#

Podobnie jak w przypadku równoważ­nego pro­gramu w C++ przyj­mijmy, że współ­czynniki Newtona będą zajmo­wały pola o szerokości 6 znaków łącznie ze spacją oddzie­lającą jeden współ­czynnik od drugiego. Z ograni­czenia tego wynika, że mogą być one liczbami co najwyżej 5 cyfrowymi. Maksy­malna wartość n, wczyty­wana z klawia­tury do zmiennej nMax, nie może być wówczas większa od 19. Warto zabez­pieczyć się przed jej przekro­czeniem, zgła­szając wyjątek niosący komu­nikat o błędzie, np.:

if (nMax < 0 || nMax > 19)
    throw new Exception("Nieprawidłowy zakres nMax.");

Nawet gdy zostanie zgłoszony poza instrukcją try—catch, to i tak łańcuch będący argu­mentem konstru­ktora klasy Exception będzie wyświe­tlony przez mecha­nizm obsługi wyjątków i użytko­wnik zostanie poinfor­mowany o błędzie, jaki popełnił.

Na początku każdego wiersza trójkąta Pascala znajduje się numer zajmu­jący pole dwuzna­kowe, a po nim stosowny odstęp i współ­czynniki. Przyjmijmy, że w osta­tnim wierszu odstęp ma szerokość zero. Wraz z przesu­waniem się o wiersz w górę odstęp wzrasta o 3 znaki, zatem w wierszu o numerze n ma szero­kość równą wartości 3*(nMax-n). Aby wypro­wadzić na wyjściu wartość n i odstęp o tej szerokości, two­rzymy łańcuch zawie­rający dwa symbole forma­tujące, który następnie używamy jako format do wyświe­tlenia n i pustego łańcucha:

string format = "{0,2}{1," + 3*(nMax-n) + "}";
Console.Write(format, n, "");

W wyrażeniu po prawej stronie operatora = wystę­pują dwa opera­tory + określa­jące konkate­nację (łączenie) łańcu­chów, bo dwa skrajne argu­menty są łańcu­chami. Ich obecność powo­duje, że środkowy argu­ment, który jest wyraże­niem arytme­tycznym, zostaje nieja­wnie przekonwer­towany na wartość typu string i połą­czony z dwoma pozostałymi. Można by tu zasto­sować jawną konwer­sję, używając np. metody ToString klasy Convert. Oczywiście można powyższy fragment kodu zapisać bez użycia zmiennej pomocniczej:

Console.Write("{0,2}{1," + 3*(nMax-n) + "}", n, "");

Poniższy program w C# tworzy w oknie kon­soli trój­kąt Pascala dla n nieprzekra­czających wczyty­wanej z klawia­tury war­tości zmiennej nMax. Współ­czynniki Newtona są wyzna­czane za pomocą rekuren­cyjnej metody staty­cznej C klasy Program. Pole statyczne NMAX tylko do odczytu określa górną granicę nMax.

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

namespace TPascala1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Trójkąt Pascala\n---------------\nnMax (0-{0}): ", NMAX);
            int nMax = Convert.ToInt32(Console.ReadLine());
            if (nMax < 0 || nMax > NMAX)
                throw new Exception("Nieprawidłowy zakres nMax.");
            Console.WriteLine("---------------");
            for (int n = 0; n <= nMax; n++)
            {
                Console.Write("{0,2}{1," + 3 * (nMax - n) + "}", n, "");
                for (int k = 0; k <= n; k++)
                    Console.Write("{0,6}", C(n, k));
                Console.WriteLine();
            }
        }

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

        static readonly int NMAX = 19;
    }
}

Tablice dwuwymiarowe

Tablica dwuwymiarowa jest układem ele­mentów tego samego typu o wspólnej nazwie ponume­rowanych dwoma inde­ksami całko­witymi od zera wzwyż. Można ją postrzegać jako prosto­kątną tabelę o okre­ślonej liczbie wierszy i kolumn. Obsługa tablic dwy­miarowych jest niemal taka sama jak tablic jedno­miarowych. Jedyna różnica przejawia się w tym, że w nawiasach [] wystę­puje przeci­nek i w związku z tym dwa indeksy zamiast jednego. Przykła­dowo, poniższy kod:

int[,] x;
x = new int[3,4];

który można zapisać w zwartej postaci:

int[,] x = new int[3,4];

powoduje zadeklarowanie tablicy dwuwymiarowej typu int o nazwie x i przydzie­lenie jej pamięci. Utworzona tablica ma 3 wiersze i 4 kolumny. Dostęp do jej elemen­tów wymaga podania dwóch indeksów, numeru wiersza i kolumny. I tak, w wyniku wyko­nania frag­mentu programu:

for (int i = 0; i < 3; i++)
    for (int j = 0; j < 4; j++)
        x[i, j] = 10 * (i+1) + (j+1);

elementy tablicy otrzymują wartości:

11   12   13   14
21   22   23   24
31   32   33   34

Ten sam efekt można uzyskać, inicjali­zując tablicę w trakcie jej tworzenia:

int[,] x = new int[,] {{11, 12, 13, 14}, {21, 22, 23, 24}, {31, 32, 33, 34}};

Powyższy zapis można skrócić do postaci:

int[,] x = {{11, 12, 13, 14}, {21, 22, 23, 24}, {31, 32, 33, 34}};

Analogicznie można tworzyć tablice o większej liczbie wymiarów. Właści­wość Length klasy Array udostę­pnia liczbę wszys­tkich elemen­tów tablicy wielowy­miarowej. Ponadto właści­wość Rank określa liczbę wymiarów tej tablicy, a metoda GetLength liczbę jej elemen­tów w danym wymiarze (argu­mentem metody jest numer wymiaru – liczba całko­wita od zera wzwyż). W rozpa­trywanym wyżej przykła­dzie tablicy dwuwymiarowej

Tablice tablic

W języku C# oprócz tablic wielowymiarowych dostępne są tablice tablic, nazy­wane również tabli­cami postrzę­pionymi (ang. jagged array). Podo­bnie jak w przy­padku tablic dynami­cznych C++, można tworzyć tablice, których elemen­tami są kolejne tablice. Poniższy kod ilu­struje dekla­rację tablicy typu int, której pierwszy wiersz ma trzy ele­menty, drugi pięć ele­mentów, a trzeci dwa ele­menty:

int[][] t = new int[3][];   // tablica tablic (wierszy)
t[0] = new int[3];          // pierwszy wiersz tablicy t
t[1] = new int[5];          // drugi wiersz tablicy t
t[2] = new int[2];          // trzeci wiersz tablicy t

Tę samą tablicę można zadeklarować w inny sposób:

int[][] t = new int[][]     // tablica tablic (wierszy)
{
    new int[3],             // pierwszy wiersz tablicy t
    new int[5],             // drugi wiersz tablicy t
    new int[2]              // trzeci wiersz tablicy t
};

Możliwa jest również jej deklaracja wraz z inicja­lizacją:

int[][] t = new int[][]
{
    new int[] {11, 12, 13},
    new int[] {21, 22, 23, 24, 25},
    new int[] {31, 32}
};

którą można nieco skrócić:

int[][] t =
{
    new int[] {11, 12, 13},
    new int[] {21, 22, 23, 24, 25},
    new int[] {31, 32}
};

A oto fragment programu wyświetlający tę tablicę:

for (int i = 0; i < t.Length; i++)
{
    for (int j = 0; j < t[i].Length; j++)
        Console.Write("{0,5}", t[i][j]);
    Console.WriteLine();
}

i wynik jego wykonania:

11   12   13
21   22   23   24   25
31   32

Program w Visual C# (wersja 2)

Użycie tablicy dwywymiarowej (prostokątnej) do zapisu współ­czynników trój­kąta Pascala byłoby nieeko­nomiczne, gdyż niemal połowa jej elementów byłaby niewyko­rzystana. Natu­ralnym jego reprezen­tantem jest trój­kątna tablica tablic typu int, której pierwszym ele­mentem (o inde­ksie 0) jest tablica jednoele­mentowa, drugim (o inde­ksie 1) tablica dwuele­mentowa itd. Przyj­mijmy, że c jest nazwą tej tablicy, a nMax nazwą zmiennej, której wartość wczyty­wana z klawia­tury określa maksy­malny numer wiersza (maksymalną wartość n) w trój­kącie Pascala. Przy­dział pamięci tablicy c można zaprogra­mować nastę­pująco:

c = new int[nMax + 1][];
for (int n = 0; n < c.Length; n++)
    c[n] = new int[n + 1];

Jak wiadomo, każdy skrajny współ­czynnik trójkąta 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. Algorytm ten daje się łatwo wyrazić w kodzie języka C#:

for (int n = 0; n < c.Length; 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];
}

Przejdźmy teraz do operacji drukowania trój­kąta Pascala w oknie konsoli. W zasadzie jest ona taka sama jak w wersji pierw­szej programu, oczywi­ście nieod­zowne jest zastą­pienie wywo­łania C(n,k) zmienną indekso­waną c[n][k]. Przy okazji możemy zrezy­gnować z tworze­nia łańcucha formatu­jącego odstęp o różnej szero­kości pomiędzy numerem wiersza a współczyn­nikami, przesu­wając w zamian kursor (karetkę) po wydruku n3*(nMax-n) znaków w prawo. W tym celu skorzy­stamy z klasy Console, która m.in. umożliwia zmianę poło­żenia kursora w oknie konsoli:

Pozycję kursora okre­ślają liczby całko­wite od zera wzwyż. Właści­wości CursorLeftCursorTop przypo­minają funkcje WhereXWhereY, a metoda SetCursor­Position proce­durę GoToXY modułu Crt języka Turbo Pascal, a także funk­cje wherex, whereygotoxy bibli­oteki conio Borland C++. Klasa Console daje większe możli­wości manipu­lowania kurso­rem, do jego przesu­nięcia wzdłuż jednej osi wystarcza zmiana jednej właści­wości. Ta dodatkowa elasty­czność pozwala na zaprogra­mowanie wydruku trój­kąta w sposób nastę­pujący:

for (int n = 0; n < c.Length; n++)
{
    Console.Write("{0,2}", n);
    Console.CursorLeft += 3 * (nMax - n);
    for (int k = 0; k <= n; k++)
        Console.Write("{0,6}", c[n][k]);
    Console.WriteLine();
}

W drugiej wersji programu generownia trójkąta Pascala trzy omówione wyżej fragmenty kodu posłu­żyły do sformuło­wania trzech metod staty­cznych klasy Program: Przydział_pamięci, ObliczeniaDrukowanie. Mają one bezpo­średni dostęp do tablicy c, ponieważ została ona zadekla­rowana jako pole staty­czne klasy Program. Rolą metody Main jest jedynie wczy­tanie w bloku try instrukcji try—catch wartości nMax, zgło­szenie wyjątku, gdy prze­kracza ona dopusz­czalny zakres, i wywo­łanie pozo­stałych metod, gdy żaden wyjątek nie został wygene­rowany:

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

namespace TPascala2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Trójkąt Pascala\n---------------\nnMax (0-{0}): ", NMAX);
            try
            {
                int nMax = Convert.ToInt32(Console.ReadLine());
                if (nMax < 0 || nMax > NMAX)
                    throw new Exception("Nieprawidłowy zakres nMax.");
                Przydział_pamięci(nMax + 1);
                Obliczenia();
                Drukowanie();
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }

        static void Przydział_pamięci(int rozmiar)
        {
            c = new int[rozmiar][];
            for (int n = 0; n < c.Length; n++)
                c[n] = new int[n + 1];
        }

        static void Obliczenia()
        {
            for (int n = 0; n < c.Length; 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];
            }
        }

        static void Drukowanie()
        {
            Console.SetWindowSize(Math.Max(6 * c.Length + 2, Console.WindowWidth),
                                  Math.Max(c.Length + 6, Console.WindowHeight));
            for (int n = 0; n < c.Length; n++)
            {
                Console.Write("{0,2}", n);
                Console.CursorLeft += 3 * (c.Length - n - 1);
                for (int k = 0; k <= n; k++)
                    Console.Write("{0,6}", c[n][k]);
                Console.WriteLine();
            }
        }

        static readonly int NMAX = 19;
        static int[][] c;
    }
}

Zmienna nMax jest lokalna w bloku try w metodzie Main, dlatego wartość wyra­żenia nMax+1 potrze­bna w meto­dzie Przydział_pamięci została do niej przeka­zana w argu­mencie rozmiar, a nMax w meto­dzie Drukowanie została zastą­piona warto­ścią wyra­żenia c.Length-1. Okno konsoli jest w razie potrzeby powię­kszane do rozmiaru pozwala­jącego na wyświe­tlenie całego trój­kąta Pascala. Wykorzy­stano w tym celu  kolejne skła­dowe klasy Console:


Opracowanie przykładu: sierpień 2018