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

Przykład C#

Sito Eratostenesa Lista jednokierunkowa w C# Program w C# (lista) Program w C# (wersja 2, tablica) Klasa generyczna "List" Program w C# (wersja 3, klasa "List") Poprzedni przykład Następny przykład Program w C++ Kontakt

Sito Eratostenesa

Liczbę naturalną (całkowitą nieujemną) nazy­wamy pierwszą, gdy ma tylko dwa podziel­niki: 1 i samą siebie. Najmniejszą liczbą pierwszą jest 2. Naszym zadaniem jest zbudo­wanie programu wyzna­czania wszystkich liczb pierw­szych nie większych od danej liczby całko­witej n. Zastosujemy algorytm, który podał grecki matematyk Eratostenes, ur. ok. 275 p.n.e. w Cyrenie (Libia), zm. ok. 194 p.n.e. w Aleksandrii (Egipt). Algorytm nosi nazwę sito Eratostenesa.

W algorytmie Eratostenesa zaczynamy od utwo­rzenia listy wszystkich liczb całko­witych od 2 do n. Listę rozpo­czyna liczba pierwsza 2. Pozosta­wiamy ją, a wszystkie dalsze liczby, które są podzielne przez 2, usuwamy z listy. Następnie przecho­dzimy do liczby znajdu­jącej się bezpo­średnio za liczbą 2. Jest nią liczba 3. Pozosta­wiamy ją, a wszystkie dalsze liczby, które są podzielne przez 3, usuwamy. Bezpo­średnio za liczbą 3 znajduje się teraz liczba 5. Dalej więc usuwamy z listy wszystkie liczby występu­jące po liczbie 5, które są podzielne przez 5. Z pozo­stałymi liczbami postę­pujemy podobnie, aż dojdziemy do końca listy. W rezultacie pozostaną na niej tylko liczby pierwsze z określo­nego na początku zakresu. Opisana metoda nazywana jest sitem, gdyż efekt usuwania liczb podziel­nych przez wybraną liczbę pierwszą kojarzy się z nasta­wieniem oczek sita na przeni­kanie liczb złożonych i zatrzy­mywanie liczb pierwszych.

Zaprezentowane poniżej trzy programy konsolowe wyznaczania liczb pierwszych według algorytmu Eratostenesa działają na trzech różnych reprezen­tacjach listy liczb całko­witych: własnej liście jednokie­runkowej, której elementy nie muszą zajmować ciągłego obszaru pamięci, tablicy dynami­cznej liczb całko­witych oraz kolekcji genery­cznej List. Struktury te charakte­ryzują się zmien­nością liczby elementów składowych. Pamięć jest im przydzie­lana dynami­cznie w trakcie wyko­nania programu, ponieważ jej rozmiar jest nieznany podczas kompilacji i nie może być ustalany staty­cznie. Te wszystkie reprezen­tacje listy nie są jednak wolne od wad.

Najbardziej elastyczna jest lista jednokie­runkowa. Dodawanie i usuwanie jej elementów jest bardzo szybkie, gdyż nie wymaga przesu­wania pozosta­łych elementów. Każdy jej element ma referencję wskazu­jącą na następny element, co wiąże się z dodatkowym narzutem pamięci i wymaga szczególnej uwagi progra­misty ze względu na łatwe do popeł­nienia i trudne do wykrycia błędy. Z kolei dopisy­wanie nowych elementów do listy reprezen­towanej przez tablicę wymaga rezerwacji tablicy na wyrost, a gdy nie ma w niej miejsca na nowy element, konieczne jest przepi­sanie wszystkich elementów ze starej tablicy do nowej o większym rozmiarze. Ponadto gdy element nie jest dopisy­wany na końcu listy, należy przesunąć część lub wszystkie elementy tablicy w kierunku końca, by zrobić miejsce na nowy element, a gdy usuwany element listy nie jest jej ostatnim elementem, należy przesunąć część lub wszystkie elementy tablicy w kierunku początku. Na szczęście w rozpatry­wanym przypadku znany jest z góry maksy­malny rozmiar początkowej listy i jej tworzenie nie wymaga przesu­wania elementów tablicy, gdyż wszystkie są dopisy­wane na końcu. Jednak przy usuwaniu elementów, które nie są liczbami pierwszymi, nie uniknie się przesu­wania elementów. Lista generyczna List jest w istocie wygodną odmianą reprezen­tacji tablicowej listy ukrywa­jącą pewne szczegóły implemen­tacyjne, jak np. przesu­wanie elementów czy rozsze­rzanie tablicy, gdy brak w niej miejsca dla nowego elementu.

Lista jednokierunkowa w C#

Lista jednokierunkowa składa się z elementów (obiektów C#) zawiera­jących pewne dane i referencję do następnego elementu (rys.). W ostatnim elemencie jest nią referencja null informu­jąca, że element ten nie ma nastę­pnika. Dodatkowa referencja (poc na rys.) udostę­pnia pierwszy element listy. Pomiędzy elemen­tami takiej listy można przecho­dzić tylko w jednym kierunku – od początku do końca; przecho­dzenie w dwóch kierunkach umożliwia lista dwukie­runkowa, której elementy zawierają dwie referencje – do poprze­dniego i nastę­pnego elementu. Rozmiar listy może się zmieniać, elementy mogą być tworzone i wsta­wiane do listy, mogą też być z niej usuwane. Należy podkreślić, że w C# programista nie ma kontroli nad momentem zwalniania pamięci usuwanych elementów, których w przypadku sita Eratostenesa może być wiele – zajmuje się tym odśmiecacz pamięci wykonywany w oddzielnym wątku.

Użycie listy jednokierunkowej reprezen­tującej ciąg liczb przetwa­rzany przez sito Eratostenesa wymaga zdefinio­wania typu danych zawiera­jącego dwa pola, których wartościami są: liczba całkowita (poten­cjalna liczba pierwsza) i referencja do nastę­pnego elementu. Nowy typ definiujemy jako klasę:

class Element
{
    public int x;            // Liczba
    public Element nast;     // Następny element
}

Operacje wstawiania elementów do listy i usuwania ich są bardzo proste, gdy dotyczą początku listy. Wstawienie nowego elementu na początek listy sprowadza się do uaktualnień dwóch referencji. Mianowicie zakładając nadal, że wartością zmiennej poc jest referencja wskazująca na początek listy, a nadto przyjmując, że wartością zmiennej p jest referencja do wsta­wianego elementu, operację tę precy­zujemy następu­jąco:

p.nast = poc;                // Następnik wstawianego elementu
poc = p;                     // Nowy początek listy

Kolejność tych dwóch przypisań jest bardzo istotna. Pierwsze sprawia, że nastę­pnikiem elementu wskazy­wanego przez referencję p jest dotych­czasowy pierwszy element listy (rys. poniżej z lewej), a drugie, że nowym pierwszym elementem listy jest element określony przez referencję p (rys. poniżej z prawej). Kod ten jest poprawny również w przypadku, gdy lista jest pusta, tj. gdy wartością zmiennej poc jest null.

Operacja wielokrotnego wstawiania nowego elementu na początek wstępnie pustej listy jest prostym sposobem genero­wania takiej listy. Wynikowy porządek elementów listy jest odwrotny do kolejności ich wstawiania. Nietrudno zatem sprecy­zować metodę genero­wania listy wszystkich liczb od 2 wzwyż przesie­wanych przez sito Eratostenesa:

void Generuj()               // Utworzenie listy liczb 2-n
{                            // (wersja uproszczona)
    Console.Write("n = ");
    int n = int.Parse(Console.ReadLine().Trim());
    Element p;
    while (n > 1)
    {
        (p = new Element()).x = n--;
        p.nast = poc;
        poc = p;
    }
}

(w metodzie pominięto kontrolę poprawności wczyty­wanej z konsoli wartości n). W każdym kroku pętli while tworzony jest w pamięci nowy element za pomocą domyślnego konstru­ktora klasy Element. Po przypi­saniu polu x wartości n element ten jest wstawiany na początek listy. Ze względu na odwrotny porządek wynikowy elementów listy do porządku ich tworzenia i wsta­wiania elementy te są obsługi­wane w kolejności maleją­cych wartości pola x (dekremen­tacja n).

Usunięcie pierwszego elementu listy jednokie­runkowej sprowadza się do uaktual­nienia referencji poc, która ma po tej operacji wskazywać na dotychcza­sowy drugi element listy (rys.) lub na listę pustą, gdy usunięty element był jedynym elementem listy. Jeżeli usuwany element ma być nadal używany, należy zapamiętać jego referencję (zmienna p):

poc = (p = poc).nast;        // Nowy początek listy

W przeciwnym razie referencja ta jest zbyteczna:

poc = poc->nast;             // Nowy początek listy

Jeżeli referencja do usuniętego elementu nie została zapamię­tana, mechanizm odśmie­cania pamięci zniszczy go, przeka­zując przydzie­lony mu obszar pamięci do puli pamięci wolnej, ale nastąpi to w trudnym do przewi­dzenia momencie. Likwidację listy elementów klasy Element można połączyć z wydrukiem przechowy­wanych w nich liczb:

void Drukuj()                // Wydruk liczb listy
{
    while (poc != null)
    {
        Console.Write("{0,7} ", poc.x);
        poc = poc.nast;
    }
    Console.WriteLine();
}

W niektórych zastosowaniach operacje dołączania elementów do listy i usuwania ich nie dotyczą początku listy, lecz innych jej miejsc. Na przykład w przy­padku implemen­tacji listowej sita Eratostenesa trzeba usuwać zbędne elementy listy występu­jące po innych jej elemen­tach. Rozważmy zadanie usunięcia z listy nastę­pnika elementu wskazy­wanego przez referencję p. Rozwią­zanie sprowadza się do wyko­nania dwóch przypisań:

q = p.nast;                  // Usuwany element
p.nast = q.nast;             // Usunięcie elementu listy

Pierwsze przypisanie zapamiętuje w zmiennej pomocni­czej q referencję do usuwa­nego elementu (rys. poniżej u góry), drugie ustala, że nowym następni­kiem elementu określo­nego przez referen­cję p jest następnik elementu wskazy­wanego przez referen­cję q (rys. poniżej u dołu). Rzecz jasna jeżeli usuwany element nie będzie dalej potrzebny, operacja da się wyrazić w prostszej postaci:

p.nast = p.nast.nast;        // Usunięcie elementu listy

Program w C# (lista)

Najwyższy czas skoncentrować się na sprawie zasadniczej – operacji przesie­wania realizo­wanej przez sito Eratostenesa. Przyjmijmy, że referencja w określa element wiodący listy zawiera­jący liczbę pierwszą. Na początku jest nim pierwszy element listy z liczbą 2, a za każdym razem po usunięciu wszystkich elementów znajdu­jących się za elementem wiodącym, które zawierają liczbę podzielną przez liczbę pierwszą w.x, referen­cja w jest przesu­wana do nastę­pnego elementu, który staje się nowym elementem wiodącym zawiera­jącym kolejną liczbę pierwszą. Przesie­wanie zakończy się, gdy lista zostanie wyczerpana, tj. gdy referen­cja w osiągnie wartość null:

for (Element w = poc; w != null; w = w.nast)
{
    ...   // Usuwanie zbędnych elementów za elementem wiodącym w
}

Aby usunąć wszystkie zbędne elementy listy występu­jące za elementem wiodącym określonym przez referen­cję w, wystarczy przeglądać listę, manipu­lując dwoma referen­cjami p i q odwołu­jącymi się do dwóch sąsie­dnich elementów (q=p.nast), poczynając od elementu wiodącego (p=w). Jeśli okaże się, że wartość q.x jest podzielna przez w.x, należy usunąć z listy element wskazy­wany przez referen­cję q. W przeci­wnym razie należy przesunąć referen­cję p w miejsce q, pozosta­wiając na razie w liście element wskazywany przez q, gdyż może on zawierać liczbę pierwszą. Całą operację przesie­wania elementów listy można sformu­łować następu­jąco:

void Przesiewaj()            // Sito Eratostenesa
{
    Element w, p, q;
    for (w = poc; w != null; w = w.nast)
        for (p = w; (q = p.nast) != null; )
            if (q.x % w.x == 0)
                p.nast = q.nast;
            else
                p = q;
}

Pełny program w C#, który dla podanej z klawiatury liczby naturalnej znajduje wszystkie liczby pierwsze nie większe od niej, korzystając z sita Eratostenesa używa­jącego listy jednokie­runkowej, jest przedsta­wiony na poniższym listingu. Metoda Generuj jest w nim w porównaniu z pierwo­wzorem rozbu­dowana o kontrolę poprawności wczyty­wanej liczby z uwzglę­dnieniem zakresu określo­nego przez stałą N, a treść metody Drukuj jest przenie­siona do metody Main.

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

namespace SitoEra1
{
    class Element
    {
        public int x;                   // Liczba
        public Element nast;            // Następny element
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Sito Eratostenesa");
            Console.WriteLine("Liczby pierwsze od 2 do n (max. {0}): ", N);
            if (Generuj())
            {
                Przesiewaj();
                while (poc != null)     // Wydruk liczb pierwszych
                {
                    Console.Write("{0,7} ", poc.x);
                    poc = poc.nast;
                }
                Console.WriteLine();
            }
        }

        static bool Generuj()           // Utworzenie listy liczb 2-n
        {
            Console.Write("n = ");
            try
            {
                int n = int.Parse(Console.ReadLine().Trim());
                if (n < 2 || n > N)
                    throw new Exception("Nieprawidłowy zakres n.");
                Element p;
                while (n > 1)
                {
                    (p = new Element()).x = n--;
                    p.nast = poc;
                    poc = p;
                }
                return true;
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                return false;
            }
        }

        static void Przesiewaj()        // Sito Eratostenesa
        {
            Element w, p, q;
            for (w = poc; w != null; w = w.nast)
                for (p = w; (q = p.nast) != null; )
                    if (q.x % w.x == 0)
                        p.nast = q.nast;
                    else
                        p = q;
        }

        static Element poc = null;      // Lista liczb pierwszych
        static readonly int N = 25000;  // Maksymalny zakres
    }
}

Poniższy rysunek przedstawia ciąg wszystkich liczb pierwszych nie większych od 1000 wygenero­wany przez program.

Program w C# (wersja 2, tablica)

Najprostszym sposobem przedstawienia listy używanej w algo­rytmie Eratostenesa jest jednowy­miarowa tablica liczb całko­witych. Zaczynamy od zadekla­rowania tej tablicy i zmiennej określa­jącej na początku wykonania programu zakres (górne ograni­czenie) liczb pierwszych, a od momentu wygene­rowania listy jej rozmiar:

int[] x = null;              // Tablica (lista) liczb pierwszych
int n;                       // Faktyczny zakres i rozmiar listy

Przez analogię do uproszczonej wersji metody Generuj tworzącej wstępną listę jednokie­runkową potencjal­nych liczb pierwszych od 2 wzwyż możemy łatwo sformu­łować wersję tej metody dla reprezen­tacji tablicowej listy. W nowej metodzie po wczytaniu podanego zakresu liczb pierwszych do zmiennej n należy przydzielć pamięć tablicy x rozmiaru o 1 mniejszego od n i określić wartości jej elementów:

void Generuj()               // Utworzenie listy liczb 2-n
{                            // (wersja uproszczona)
    Console.Write("n = ");
    n = int.Parse(Console.ReadLine().Trim());
    x = new int[--n];
    for (int k = 0; k < n; k++)
        x[k] = k + 2;
}

Przypisanie elementom tablicy wartości równych indeksom tych elementów powię­kszonym o 2 odpowiada utworzeniu wstępnej listy liczb całko­witych od 2 do n. Dzięki dostępowi do elementów tablicy poprzez indeksy operację przesie­wania listy według algorytmu Eratostenesa można sprecy­zować następu­jąco:

void Przesiewaj()            // Sito Eratostenesa
{
    for (int p = 0; p < n; p++)
        for (int q = p + 1; q < n; )
            if (x[q] % x[p] == 0)
            {
                n--;
                for (int k = q; k < n; k++)
                    x[k] = x[k + 1];
            }
            else
                q++;
}

Jest oczywiste, że indeks p przebiegnie całą listę złożoną tylko z ele­mentów zawiera­jących liczby pierwsze, skoro jej początkowy element x[0] jest równy liczbie pierw­szej 2 i w trakcie przecho­dzenia indeksu q po nastę­pnych elemen­tach listy każdy napotkany element x[q] podzielny przez x[p] zostanie z niej usunięty. Operacja usunięcia elementu listy polega na zmniej­szeniu rozmiaru listy o 1 i przesu­nięciu następnych elementów tablicy o jedno miejsce w kierunku jej początku.

Rozważania te prowadzą do drugjej wersji programu w C#, która dla podanej z klawiatury liczby naturalnej znajduje wszystkie liczby pierwsze nie większe od niej, używając sita Eratostenesa operu­jącego na tablicy liczb całko­witych:

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

namespace SitoEra2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Sito Eratostenesa");
            Console.WriteLine("Liczby pierwsze od 2 do n (max. {0}): ", N);
            if (Generuj())
            {
                Przesiewaj();
                for (int k = 0; k < n; k++)
                    Console.Write("{0,7} ", x[k]);
                Console.WriteLine();
            }
        }

        static bool Generuj()           // Utworzenie listy liczb 2-n
        {
            Console.Write("n = ");
            try
            {
                n = int.Parse(Console.ReadLine().Trim());
                if (n < 2 || n > N)
                    throw new Exception("Nieprawidłowy zakres n.");
                x = new int[--n];
                for (int k = 0; k < n; k++)
                    x[k] = k + 2;
                return true;
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                return false;
            }
        }

        static void Przesiewaj()        // Sito Eratostenesa
        {
            for (int p = 0; p < n; p++)
                for (int q = p + 1; q < n; )
                    if (x[q] % x[p] == 0)
                    {
                        n--;
                        for (int k = q; k < n; k++)
                            x[k] = x[k + 1];
                    }
                    else
                        q++;
        }

        static int[] x = null;          // Tablica (lista) liczb pierwszych
        static int n;                   // Faktyczny zakres i rozmiar listy
        static readonly int N = 25000;  // Maksymalny zakres
    }
}

Klasa generyczna "List"

Przestrzeń System.Collections.Generics włączana automaty­cznie do genero­wanego przez środowisko Visual C# tekstu programu zawiera szereg tzw. klas genery­cznych umożliwia­jących wygodne korzystanie z kolekcji służących do grupo­wania danych na różne sposoby. Elementami kolekcji mogą być obiekty tej samej klasy – standar­dowej lub definio­wanej przez użytko­wnika. Jednym z przy­kładów takiej kolekcji jest klasa Stack implemen­tująca strukturę danych nazywaną w algory­tmice i informa­tyce stosem, używaną w pro­gramie przeno­szenia wież Hanoi do reprezen­towania wież ukła­danych na palikach z kolo­rowych krążków w kolej­ności malejących średnic w znanej grze logicznej dla dzieci.

Najpopularniejszyą klasą generyczną jest kolekcja List implemen­tująca listę elementów, do których można się dostać za pomocą indeksu, czyli tak samo jak do elementów tablicy. W dekla­racji obiektu tej klasy trzeba, podobnie jak w przypadku wspomnianej powyżej klasy Stack i innych klas genery­cznych, podać w nawiasach <> po nazwie klasy typ elementów kolekcji. W trzeciej wersji programu wyzna­czania liczb pierwszych według algorytmu Eratostenesa użyjemy listy zadekla­rowanej następu­jąco:

List<int> x = null;          // Lista liczb pierwszych

Zmienna x jest jedynie pustą referencją. Listę trzeba utworzyć za pomocą operatora new i konstru­ktora klasy List<>. W jego argu­mencie można podać pojemność początkową listy (konstru­ktor bezargu­mentowy tworzy listę o pojemności domyślnej). Pojemność i aktualną liczbę elementów listy określają właści­wości CapacityCount. Utworzona lista nie ma żadnego elementu, a w miarę dodawania do niej elementów jej pojemność może zostać zwiększona, gdy zajdzie taka potrzeba. Metoda Add dodaje element danych na końcu listy, toteż wywołując ją kolejno dla liczb całko­witych od 2 wzwyż, uzyskamy listę początkową gotową do przesie­wania przez sito Eratostenesa:

void Generuj()               // Utworzenie listy liczb 2-n
{                            // (wersja uproszczona)
    Console.Write("n = ");
    int n = int.Parse(Console.ReadLine().Trim());
    x = new List<int>(n - 1);
    for (int k = 2; k <= n; k++)
        x.Add(k);
}

Można również wstawiać elementy w dowolne miejsce listy, korzystając z dwuargu­mentowej metody Insert, której pierwszy argument jest indeksem określa­jącym miejsce wstawienia, usunąć wszystkie elementy listy za jednym razem za pomocą bezargu­mentowej metody Clear, a także usunąć element listy, posłu­gując się metodą RemoveAt, której jedynym argu­mentem jest jego indeks. Tak więc tablicową wersję metody przesie­wania listy można łatwo przekształcić na postać operu­jącą na elemen­tach obiektu x:

void Przesiewaj()            // Sito Eratostenesa
{
    for (int p = 0; p < x.Count; p++)
        for (int q = p + 1; q < x.Count; )
            if (x[q] % x[p] == 0)
                x.RemoveAt(q);
            else
                q++;
}

Program w C# (wersja 3, klasa "List")

Kod źródłowy trzeciej wersji programu konsolowego w C#, który dla podanej z klawia­tury liczby naturalnej wyznacza wszystkie liczby pierwsze nie większe od niej według algorytmu Eratostenesa działa­jącego na liście klasy genery­cznej List<int>, jest przedsta­wiony na poniższym listingu. Niewielkim udoskona­leniem wydruku liczb pierwszych jest w nim użycie zamiast trady­cyjnej pętli for nowszej pętli foreach, która w kolejnych krokach utożsamia zmienną itera­cyjną k typu int z elemen­tami listy x.

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

namespace SitoEra3
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Sito Eratostenesa");
            Console.WriteLine("Liczby pierwsze od 2 do n (max. {0}): ", N);
            if (Generuj())
            {
                Przesiewaj();
                foreach (int k in x)
                    Console.Write("{0,7} ", k);
                Console.WriteLine();
                x.Clear();
            }
        }

        static bool Generuj()               // Utworzenie listy liczb 2-n
        {
            Console.Write("n = ");
            try
            {
                int n = int.Parse(Console.ReadLine().Trim());
                if (n < 2 || n > N)
                    throw new Exception("Nieprawidłowy zakres n.");
                x = new List<int>(n - 1);
                for (int k = 2; k <= n; k++)
                    x.Add(k);
                return true;
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                return false;
            }
        }

        static void Przesiewaj()            // Sito Eratostenesa
        {
            for (int p = 0; p < x.Count; p++)
                for (int q = p + 1; q < x.Count; )
                    if (x[q] % x[p] == 0)
                        x.RemoveAt(q);
                    else
                        q++;
        }

        static List<int> x = null;          // Lista liczb pierwszych
        static readonly int N = 25000;      // Maksymalny zakres
    }
}

Warto na koniec porównać zgrubnie wydajność trzech powyższych programów wyzna­czania liczb pierwszych. Prosty test dla maksymal­nego zakresu 25000 wykazuje, że najszybciej wykonuje się program działa­jący na liście jednokie­runkowej, który wyświetla wyniki natych­miast po wprowa­dzeniu zakresu, a najwol­niej program operujący na tablicy dynami­cznej, na wynik którego trzeba oczekiwać ok. jednej sekundy (procesor i5-430M). Program korzystający z klasy genery­cznej List jest niemal tak szybki jak używający listy jednokie­runkowej. Dodatkowym ważnym atutem klas genery­cznych są ich metody i właści­wości ułatwiające tworzenie bezpie­cznych, zgrabnych i czytelnych programów.


Opracowanie przykładu: marzec 2020