Tablice

Tablica jest złożoną strukturą danych, zbudowaną z ciągu takich samych elementów. Przed pierwszym użyciem tablicy musimy ją zdefiniować:

 

typ nazwa[liczba_elementów];

typ - określa rodzaj informacji, którą można przechować w każdym elemencie tablicy
nazwa - określa nazwę zmiennej będącej tablicą. Nazwę tworzymy wg poznanych zasad.
liczba_elementów - określa, ile elementów zawiera tablica

 

Przykład:

int a[5];  // zmienna a jest tablicą 5-cio 
elementową

 

Elementy tablicy są przechowywane w pamięci komputera w jednym bloku obok siebie. Każdy element posiada numer, zwany indeksem. Indeks pozwala na dostęp do wybranego elementu tablicy. Indeksy w języku C++ rozpoczynają się od 0. W tablicy zdefiniowanej powyżej istnieją następujące elementy (często zwane komórkami tablicy):

 

a[0]  a[1]  a[2]  a[3]  a[4]

 

Zwróć uwagę, że w tablicy tej nie ma elementu a[5]. Popularnym błędem wśród początkujących programistów w języku C++ jest odwoływanie się do nieistniejących elementów tablicy. Jest to przyczyną trudnych do wykrycia błędów, ponieważ kompilator nie ostrzega nas, jeśli indeks przekroczy dozwoloną wartość. Jeśli program zapisuje dane do takiego nieistniejącego elementu, to faktycznie dane te mogą trafić do innej zmiennej i spowodować nieprawidłowości w pracy programu - zmienna "magicznie" zmienia swoją zawartość, mimo że program tego w niej jawnie nie zapisuje - robi to przy zapisie do nadmiarowych elementów tablicy.

Tablice stosujemy wszędzie tam, gdzie musimy przetworzyć dużą liczbę podobnych danych - np. tysiące wyników pomiarów jakiejś wielkości, ciąg liczbowy, teksty itp. Tablica różni się od zmiennej prostej tym, iż może przechowywać naraz wiele różnych wartości, a zmienna prosta tylko jedną. Dzięki indeksom możemy wyliczać w programie elementy tablicy, które będą przetwarzane.

 

Poniższy program tworzy tablicę 10-cio elementową (o indeksach od 0 do 9) i wypełnia ją kolejnymi wielokrotnościami liczby 3.

 

#include <iostream>

using namespace std;

int main()
{
    int T[10],i;

    // tablicę wypełniamy wielokrotnościami liczby 3

    for(i = 0; i < 10; i++) T[i] = 3 * (i + 1);

    // wyświetlamy zawartość tablicy

    for(i = 0; i < 10; i++) cout << "T[" << i << "] = " << T[i] << endl;

    return 0;
}

 

Sito Eratostenesa

Zbiór liczb naturalnych bez liczby 1 składa się z dwóch rodzajów liczb:

  1. Liczb złożonych, które są podzielne przez liczby mniejsze z tego zbioru.
  2. Liczb pierwszych, które nie są podzielne przez liczby mniejsze z tego zbioru.

Pierwszy rodzaj liczby to wielokrotności liczb mniejszych. Jeśli zatem ze zbioru usuniemy wielokrotności kolejnych liczb, to pozostaną w nim tylko liczby pierwsze. Na tej właśnie zasadzie działa sito Eratostenesa - przesiewa liczby wyrzucając ze zbioru ich kolejne wielokrotności.

 

Przykład:

Mamy zbiór liczb:

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

 

Rozpoczynamy od liczby 2. Wyrzucamy wszystkie jej wielokrotności:

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

 

Po tej operacji w zbiorze pozostaje liczba 2 oraz liczby nieparzyste. Żadna z pozostałych liczb, oprócz 2, nie dzieli się już przez 2. Teraz to samo wykonujemy z liczbą 3. Wyrzucamy ze zbioru wszystkie jej wielokrotności:

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50


Operację kontynuujemy z pozostałymi liczbami:

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

 

...

 

I ostatecznie otrzymujemy zbiór, z którego usunięto wszystkie liczby złożone:

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

 

Pozostałe w zbiorze liczby są liczbami pierwszymi: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47.

 

Realizując ten algorytm na komputerze musimy wybrać odpowiednią reprezentację zbioru liczb, z którego można usuwać w prosty sposób wielokrotności liczb. Użyjemy do tego celu tablicy. Poszczególne elementy tej tablicy będą reprezentowały liczby zbioru. Natomiast zawartość tych elementów będzie informacją, czy dany element pozostaje w zbiorze, czy też został z niego usunięty.

Najlepszym typem danych dla tablicy będzie typ logiczny bool. Jeśli element tablicy będzie miał wartość true, to znaczy, że reprezentowana przez jego indeks liczba znajduje się w zbiorze. Jeśli będzie miał wartość false, to ta liczba została ze zbioru usunięta. Na początku algorytmu umieszczamy true we wszystkich elementach tablicy - odpowiada to pełnemu zbiorowi liczb. Następnie do elementów, których indeksy są wielokrotnościami początkowych liczb, będziemy wpisywać false. Na końcu algorytmu wystarczy przeglądnąć tablicę i wyprowadzić indeksy tych elementów, które zachowały wartość true - nie są one wielokrotnościami żadnych wcześniejszych liczb, a zatem są liczbami pierwszymi.

 

Algorytm Sita Eratostenesa

Wejście:

    n - określa górny kraniec przedziału <2,n>, w którym poszukujemy liczb pierwszych
Wyjście:

    Liczby pierwsze z przedziału <2,n>

Dane pomocnicze:

    T[ ] - tablica o elementach logicznych, których indeksy obejmują przedział <2,n>

    i - kolejne liczby, których wielokrotności usuwamy
    w - wielokrotności liczb i
 

K01: Ustaw wszystkie elementy T[ ] na true  
K02: Dla i = 2,3,...,n-1: wykonuj K03...K06 ; rozpoczynamy od liczby 2
K03:     wi + i ; liczymy pierwszą wielokrotność liczby i
K04:     Dopóki wn: wykonuj K05...K06 ; sprawdzamy, czy wielokrotność wpada w przedział <2,n>
K05:         T[w] ← false ; jeśli tak, to usuwamy ją ze zbioru liczb
K06:         ww + i ; obliczamy następną wielokrotność
K07: Dla i = 2,3,...,n: wykonuj:
    Jeśli T[i] = true, to pisz i
; przeglądamy tablicę T[ ], wypisując indeksy, dla których
; komórki zachowały true
K11: Zakończ  

 

 

Na podstawie algorytmu napisz pierwszą wersję programu


Algorytm na ślepo usuwa wszystkie wielokrotności kolejnych liczb w zbiorze. Tymczasem nie jest to konieczne. Np. liczba 2 usunęła ze zbioru wszystkie liczby parzyste za wyjątkiem siebie. Zatem w zbiorze nie ma już liczb 4, 6, 8 itd. Nie ma też wielokrotności żadnej liczby parzystej, która sama jest parzysta. Podobnie liczba 3 usunęła wszystkie wielokrotności podzielne przez 3: 6 9 12 15 itd. Nasuwa się spostrzeżenie, że wielokrotności danej liczby mogą występować w zbiorze, jeśli ta liczba nie została wcześniej usunięta. Jeśli ją usunięto, to również usunięto wszystkie jej wielokrotności. Zatem wykonanie pętli usuwającej wielokrotności powinniśmy uzależnić od tego, czy liczba i jest w zbiorze. Zmiana jest niewielka, a zysk duży:

Zmodyfikuj program, aby uwzględniał to spostrzeżenie.


Kolejne usprawnienie będzie dotyczyło pierwszej usuwanej ze zbioru wielokrotności. Obecnie jest to:

 

w = i + i

 

Rozważmy:

 

i = 3. Wielokrotność 6 jest podzielna przez 2 i została już usunięta wcześniej ze zbioru. Pierwszą nieusuniętą wielokrotnością jest 9, czyli 32.
i = 5. Wielokrotności już usunięte to: 10, 15, 20. Pierwsza nieusunięta wielokrotność to 25, czyli 52.
i = 7. Wielokrotności już usunięte to: 14, 21, 28, 35, 42. Pierwsza nieusunięta wielokrotność to 49, czyli 72.

 

Z podanych przykładów widzimy jasno, że pierwszą wielokrotnością, od której należy rozpocząć usuwanie jest i2. Powód jest bardzo prosty. Mniejsze wielokrotności rozkładają się na dwa czynniki, z których jednym jest i, a drugim liczba mniejsza od i. Skoro tak, to ta mniejsza liczba już wcześniej usunęła taką wielokrotność.

Zatem w programie zmieniamy:

 

for(w = i + i; ...

na

for(w = i * i; ...

 


Skoro pierwszą usuwaną wielokrotnością jest i2, to gdy i przekroczy wartość pierwiastka z n, wielokrotność ta znajdzie się poza przedziałem <2,n>. Zatem wystarczy, aby i przebiegało wartości od 2 do pierwiastka z n.


Zadanie

Zapisz kompletny algorytm w postaci listy kroków. Narysuj odpowiedni schemat blokowy.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.