Warsztat

Odmiany typów podstawowych

Podsumujmy typy danych, które możesz napotkać w języku C:

char

Aby uniknąć niejednoznaczności, można stosować modyfikatory typu:

int

W świecie mikrokontrolerów 8-bitowych typ int najczęściej oznacza daną o długości 16 bitów. Zakres wynosi wtedy od -32768 do 32767 (-2¹⁵...2¹⁵ - 1). Jednakże może również oznaczać daną o długości 1 bajta, ponieważ to jest naturalna dana całkowita dla mikroprocesora 8-bitowego. Zwykle taki tryb wymaga włączenia w kompilatorze odpowiedniej opcji. Musisz to sobie sprawdzić w dokumentacji środowiska programowania, którego będziesz używał.

Typ int może występować z modyfikatorami (przy stosowaniu modyfikatorów nazwę int można pominąć):

float

double

long double

Definiowanie własnego typu

W języku C możesz definiować własne typy danych za pomocą słowa kluczowego typedef:

typedef nazwa_typu_istniejącego nowa_nazwa;

Na przykład: nie podoba ci się nazwa typu unsigned int. Nie ma sprawy:

/* Własne typy danych (C)2016 mgr Jerzy Wałaszek Data utworzenia: 26.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> // Definicja własnego typu typedef unsigned int bezznakowe; int main() { // definiujemy zmienne z nową nazwą typu bezznakowe a,b,c; setlocale(LC_ALL,""); a = 1; b = a + 10; c = 12 * b; printf("%u %u %u\n", a, b, c); return 0; }

W ten sposób da się pozmieniać nazwy wszystkich typów podstawowych, tylko po co? Lepszym zastosowaniem dla typedef jest tworzenie zupełnie nowych typów danych:

/* Własne typy danych (C)2016 mgr Jerzy Wałaszek Data utworzenia: 26.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> // Definicja własnego typu typedef struct { float re,im; } complex; int main() { // definiujemy zmienne z nową nazwą typu complex a = {1,2}; complex b = {2,2}; complex c; setlocale(LC_ALL,""); c.re = a.re + b.re; c.im = a.im + b.im; printf("DODAWANIE LICZB ZESPOLONYCH\n" "---------------------------\n\n" "Liczba a = %f + j%f\n" "Liczba b = %f + j%f\n" "Suma a + b = %f + j%f\n", a.re,a.im,b.re,b.im,c.re,c.im); return 0; }

W programie utworzyliśmy bezimienną strukturę i przypisaliśmy jej typ do nazwy nowego typu danych complex (liczba zespolona). Struktura zawiera dwa pola: re – część rzeczywista liczby zespolonej (ang. real part) i im – część urojona (ang. imaginary part). Wg nowego typu complex zdefiniowaliśmy 3 zmienne: a, b i c. Dwóm pierwszym zmiennym nadaliśmy wartości początkowe: a = 1 + j2 i b = 2 + j2. Następnie obliczyliśmy sumę liczb a i b, umieszczając wynik w zmiennej c.

Jeśli nie wiesz, czym są liczby zespolone, to dowiesz się tego w tym rozdziale.

Typ wyliczeniowy

Bardzo przydatny jest tzw. typ wyliczeniowy (an. enumerated type). Tworzymy go za pomocą słówka kluczowego enum w sposób następujący:

enum nazwa_typu {nazwa_1, nazwa_2,...,nazwa_n};

Jak to działa? Weźmy prosty przykład:

enum weekday {sunday, monday, tuesday, wednesday, thursday, friday, saturday};

W efekcie tej definicji powstanie nowy typ danych o nazwie enum weekday (dzień tygodnia). Oprócz nazwy typu powstaje zbiór stałych o nazwach dni tygodnia. Stałe te otrzymują kolejne wartości:

sunday ← 0 monday ← 1 tuesday ← 2 wednesday ← 3 thursday  ← 4 friday ← 5 saturday ← 6

Teraz na podstawie nowego typu możesz definiować zmienne i nadawać im wartości określone przez stałe:

enum weekday a,b,c; ... a = tuesday; ... if(b == c && b == friday) ... ...

Czy naprawdę potrzebujemy typ enum? Oczywiście, że nie. Bez niego moglibyśmy się obejść, lecz dobrze go mieć, bo jest czasem wygodny. Nasze stałe moglibyśmy zdefiniować następująco:

#define sunday 0 #define monday 1 #define tuesday 2 #define wednesday 3 #define thursday 4 #define friday 5 #define saturday 6 ... int a,b,c; ... a = wednesday; ... if(b == c && b == saturday) ... ...

A teraz wyobraź sobie, że zrobiłeś drobną pomyłkę:

#define sunday 0 #define monday 1 #define tuesday 2 #define wednesday 3 #define thursday 4 #define friday 5 #define saturday 5 ... int a,b,c; ... a = wednesday; ... if(b == c && b == saturday) ... ...

I już program staje się wadliwy. Typ enum nadaje stałym kolejne wartości automatycznie. Dodatkowo zadanie wykonywane jest przez kompilator a nie przez preprocesor. Zatem można już w trakcie kompilacji wyłapać różne błędy.

Wartości stałych w typie enum możesz też sam okreslić:

enum weekday {sunday, monday, tuesday = 6, wednesday, thursday, friday, saturday};

Jeśli na liście stałych nadasz jednej z nich konkretną wartość, to wszystkie stałe, które na liście występują później, otrzymają wartości kolejne od nadanej. W tym przypadku otrzymasz:

sunday ← 0 monday ← 1 tuesday ← 6 wednesday ← 7 thursday  ← 8 friday ← 9 saturday ← 10

W krańcowym przypadku możesz sam określić wartość każdej stałej:

enum weekday {sunday = 7, monday = 2, tuesday = 6, wednesday = 5, thursday = 99, friday = 12, saturday = 87};

Zmienna zbudowana na podstawie zdefiniowanego typu wyliczeniowego jest zwykle typu int. Jednak nie licz na to zbytnio, ponieważ w definicji typu wyliczeniowego określono jedynie, że zmienna wynikowa będzie takiego typu, który pomieści wszystkie wartości stałych.

/* Typ wyliczeniowy (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> enum boolean {False,True}; int main() { setlocale(LC_ALL,""); printf("%d\n",sizeof(enum boolean)); return 0; }

Również kompilator nie kontroluje wartości nadawanym zmiennym typu enum:

/* Typ wyliczeniowy (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> enum boolean {False,True}; int main() { enum boolean a,b,c; setlocale(LC_ALL,""); a = False; // OK b = True; // OK c = 3; // ??? też OK! printf("%d %d %d\n", a, b, c); return 0; }

Pola bitowe

Pola bitowe (ang. bit fields) umożliwiają tworzenie danych, które zajmują określoną liczbę bitów, co z kolei pozwala efektywniej wykorzystać pamięć komputera. Definicja pól bitowych opiera się na definicji struktury i wygląda następująco:

struct nazwa_typu { typ_całkowity nazwa_pola_1 : rozmiar_1; typ_całkowity nazwa_pola_2 : rozmiar_2; ... typ_całkowity nazwa_pola_n : rozmiar_n; };

Jak to działa? Struktura tyle danych typu int, aby pomieściły w sobie wszystkie pola bitowe. Załóżmy, że zdefiniowaliśmy następującą strukturę:

struct flags { unsigned a : 1, b : 3, c : 2, d : 1; };

W strukturze zawarte są 4 pola bitowe: a jednobitowe, b trzybitowe, c dwubitowe oraz d jednobitowe. Liczba użytych bitów wynosi: 1 + 3 + 2 + 1 = 7, zatem mieszczą się w jednej danej typu int. Rozmiar struktury zależy od rozmiaru typu int. W Code::Blockcs będzie to 4 bajty:

/* Pola bitowe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> struct flags { unsigned a : 1, b : 3, c : 2, d : 1; }; int main() { setlocale(LC_ALL,""); printf("%d\n", sizeof(struct flags)); return 0; }

W pamięci pola te są rozmieszczone w pierwszym bajcie struktury następująco (gdy typ int ma rozmiar 4 bajtów):

Pola bitowe są traktowane tak samo jak pola struktur (którymi przecież są). Możesz umieszczać w nich dane oraz używać ich w wyrażeniach. Jedynym ograniczeniem jest to, iż nie można uzyskać adresu pola bitowego oraz nie można go zainicjować w trakcie tworzenia zmiennej.

/* Pola bitowe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> struct flags { unsigned a : 1, b : 3, c : 2, d : 1; }; int main() { struct flags f; // tworzymy zmienną z polami bitowymi setlocale(LC_ALL,""); f.a = 1; f.c = 3; f.d = 0; f.b = f.a + f.c + f.d; printf("%d\n",f.b); return 0; }

Jeśli wynik przekracza rozmiar pola, to zostanie obcięty do rozmiaru pola. Innymi słowy: jeśli w strukturze zdefiniowałeś pole 3 bitowe, a chcesz w nim umieścić daną np. 4 bitową 1101₂ (dziesiętnie 13), to w polu zostaną umieszczony tylko 3 najmłodsze bity, czyli 101₂ (dziesiętnie 5):

/* Pola bitowe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> struct flags { unsigned a : 1, b : 3, c : 2, d : 1; }; int main() { struct flags f; // tworzymy zmienną z polami bitowymi setlocale(LC_ALL,""); f.b = 13; printf("%d\n",f.b); return 0; }

Pola bitowe nie muszą leżeć obok siebie. Możesz wprowadzić między nimi przerwy. Przerwę definiujesz podając tylko jej rozmiar. Na przykład definicja:

struct flags
{
  unsigned : 3, a : 2, : 5;
  int b : 5;
};

tworzy strukturę, w której są dwa pola bitowe: a trzybitowe i b pięciobitowe. Pole a przechowuje liczby całkowite bez znaku od 0 do 7. Pole b przechowuje liczby całkowite ze znakiem od -16 do 15. Pierwsze trzy bity struktury są nieużywane, również 5 bitów pomiędzy polami a i b nie jest używane. Całość wygląda następująco:

/*
 Pola bitowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

struct flags
{
  unsigned : 3, a : 3, : 5;
  int b : 5;
};

int main()
{
  struct flags f; // tworzymy zmienną z polami bitowymi

  setlocale(LC_ALL,"");

  f.a = 6;
  f.b = -12;
  printf("%d %d\n", f.a, f.b);

  return 0;
}

Jest to dyrektywa preprocesora, która przyporządkowuje nazwie pewną stałą wartość. Dzięki niej możemy łatwo zdefiniować w programie wartości logiczne:

#define FALSE 0
#define TRUE 1

Od tego momentu każde wystąpienie słowa FALSE będzie równoważne z 0, a każde wystąpienie słowa TRUE będzie równoważne z 1. Podmiana następuje przed kompilacją pliku źródłowego.

W ten sposób tworzymy zmienną, której wartości nie można w programie zmieniać. Zaletą w stosunku do poprzedniego sposobu jest to, iż stałą tworzy kompilator, zatem może wyłapać on różne błędy.

Sens takiej konstrukcji dla prostej zmiennej może nie być zbyt duży. Lecz wyobraź sobie, że chcemy w programie zainicjować np. tablicę struktur (czasem się z takiego tworu korzysta):

/* Stałe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> struct triplex { float a,b,c; }; int main() { const struct triplex cs = {3.1415,2.7728,1.4312}; struct triplex t[10]; int i; setlocale(LC_ALL,""); for(i = 0; i < 10; i++) t[i] = cs; t[5].a = 6.2833; t[5].b = 3.0; t[5].c = 0.22; for(i = 0; i < 10; i++) printf("Struktura nr %d\n" "a = %6.4f b = %6.4f c = %6.4f\n\n", i, t[i].a, t[i].b, t[i].c); return 0; }

enum {nazwa, nazwa,...}; enum {nazwa=wartość, nazwa=wartość, ...};

Typ wyliczeniowy tworzy automatycznie zestaw stałych typu całkowitego. Stałym można przypisywać kolejne wartości lub wartości wybrane. Utworzone w ten sposób stałe można wykorzystać do dowolnego celu:

/* Stałe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 30.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> int main() { enum {up,down,left,right}; int d; setlocale(LC_ALL,""); d = up+down+left+right; printf("%d\n\n",d); return 0; }

Literały

Literał jest zapisem liczby. Np. 15 jest literałem liczby dziesiętnej. Ponieważ w języku C mogą występować różne typy danych, istnieją dla nich odpowiednie literały:

int

• dziesiętnym, zapis normalny, np. 1267, -12844
• ósemkowym, zapis poprzedzony cyfrą 0, np. 033, -0777
• szesnastkowym, zapis poprzedzony przedrostkiem 0x lub 0X, np. 0xff, -0XAF3
• dwójkowym, zapis poprzedzony przedrostkiem 0b lub 0B, np. 0b11101, -0B101

unsigned int

long int

unsigned long int

/*
 Stałe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

int main()
{
  unsigned long long a;

  setlocale(LC_ALL,"");

  a = 30000000000ul;
  printf("%llu\n\n", a);

  return 0;
}

Wyrażenia stałe

Wyrażenie jest stałe (ang. constant expression), jeśli jego wartość da się policzyć w czasie kompilacji. Tego typu wyrażenia są przez kompilator obliczane i zamieniane na stałą o wartości wyrażenia. Dzięki temu mikroprocesor nie musi obliczać wartości takiego wyrażenia podczas działania programu. Przyspiesza to wykonywanie programu oraz skraca jego kod.

W świecie mikrokontrolerów wyrażenia stałe często używane są do ustawiania bitów w rejestrach.

Na przykład instrukcja:

r = (1 << 5) || (1 << 3) || (1 << 2);

jest równoważna instrukcji:

r = 0b10110;

Pierwszy sposób stosuje się dla poprawienia czytelności operacji.

Liczba losowa to taka, której zakres znamy (np. od 1 do 6 dla oczek wyrzucanych na kostce do gry), lecz nie potrafimy przewidzieć konkretnej wartości, ponieważ jest losowa (jak wynik rzutu kostką – taka niezafałszowaną). Mówimy, że dana wartość pojawia się z pewnym prawdopodobieństwem. Prawdopodobieństwo (a właściwie rachunek prawdopodobieństwa) jest terminem matematycznym pochodzących z teorii gier, która, co ciekawe, wcale obecnie nie służy tylko i wyłącznie do grania w gry, a nawet jest jedną z najważniejszych teorii matematycznych. Rachunek prawdopodobieństwa jest używany przez poważne teorie fizyczne (np. teorię kwantową), ekonomiczne i socjologiczne.

Nie wnikając zbyt głęboko w aspekty matematyczne, określmy prawdopodobieństwo jako liczbę P z zakresu od 0 do 1. Prawdopodobieństwa wiążą się z konkretnymi zdarzeniami:

• wypadnięcie na kostce sześciu oczek,
• otrzymanie w pokerze 4 asów
• wyrzucenie orzełka monetą
• oberwanie meteorytem między oczy podczas przechadzki w parku.

Prawdopodobieństwo P równe 0 oznacza zdarzenie niemożliwe, czyli takie, które w żaden sposób nie może zajść.

Prawdopodobieństwo P równe 1 oznacza zdarzenie pewne, czyli takie, które wystąpi na pewno.

Jeśli weźmiemy zbiór n zdarzeń (np. 6 zdarzeń wyrzucenia kostką od jednego do 6 oczek) i stanowią one zbiór kompletny (tzn. w danym doświadczeniu nie może wystąpić żadne inne zdarzenie spoza tego zbioru), to suma ich prawdopodobieństw jest równa 1, czyli pewnikiem jest, że zawsze któreś z tych zdarzeń na pewno wystąpi.

Na przykład, przy rzucie kostką mamy 6 możliwych zdarzeń (pomijamy zdarzenia typu: kostkę złapał kot i uciekł z nią):

1. Wypadło 1 oczko
2. Wypadły 2 oczka
3. Wypadły 3 oczka
4. Wypadły 4 oczka
5. Wypadło 5 oczek
6. Wypadło 6 oczek

Każde z tych zdarzeń jest jednakowo prawdopodobne i zakładamy, że zawsze któreś z nich wystąpi. Mamy zatem:

Wynika z tego, że każde ze zdarzeń wypadnięcia określonej liczby oczek posiada prawdopodobieństwo ¹/₆. Nie rozum tego w ten sposób, że co 6 rzutów zawsze wypadnie ci 6 oczek. Tak dobrze nie ma. Jeśli jednak wykonasz 6 milionów rzutów dobrą (tzn nieoszukaną) kostką, to powinno ci wypaść w tej liczbie około 1 miliona szóstek (im więcej rzutów tym liczba szóstek będzie bardziej zbliżona do ¹/₆ liczby wszystkich rzutów).

Jeśli każde z możliwych zdarzeń ma takie samo prawdopodobieństwo wystąpienia, to mówimy, że rozkład tych prawdopodobieństw jest równomierny.

Jak zauważyłeś, liczby losowe stosowane mogą być do symulacji wyników losowych. Jednak jest z nimi jeden kłopot: nie da się ich tworzyć programowo. Powodem jest to, iż liczba losowa nie jest wynikiem żadnego wyrażenia, w którym nie występują inne liczby losowe. I dostajemy błędne koło.

Jednym ze sposobów tworzenia liczb losowych w mikrokontrolerach jest wykorzystanie tzw. liczników/timerów (są to układy wewnątrz mikrokontrolera, które zliczają impulsy pochodzące z różnych źródeł) oraz współpracy z użytkownikiem. Człowiek dla mikrokontrolera jest bardzo powolną istotą i, co ważniejsze, nieprzewidywalną. Jeśli licznik zlicza impulsy o bardzo dużej częstotliwości, to jego stan zmienia się miliony razy na sekundę. Gdy użytkownik naciśnie np. jakiś przycisk, to mikrokontroler może w tym momencie odczytać stan licznika i otrzymać w ten sposób dobrą liczbę losową (nie wiadomo, kiedy użytkownikowi przyjdzie ochota nacisnąć przycisk, dlatego stan licznika jest nieprzewidywalny, a zatem losowy).

Jednak co zrobić, jeśli nie mamy wolnego licznika, a musimy generować liczby pseudolosowe? Z pomocą przychodzi tzw. generator liczb pseudolosowych.

Generator liczb pseudolosowych (ang. pseudorandom number generator) jest funkcją, która zwraca wartości wyglądające jak liczby losowe (to jak to właśnie łaciński przedrostek pseudo = jakby), lecz nimi nie będące. Jak to rozumieć? Otóż chodzi o to, że taka funkcja tworzy ciąg liczb, które można uznać za losowe, ponieważ na pierwszy rzut oka nie widać pomiędzy nimi jakiś zależności. W rzeczywistości taka zależność jest i jeśli znamy jedną liczbę pseudolosową, to możemy sobie wygenerować wszystkie następne. Co więcej, liczby pseudolosowe tworzą ciąg wartości, który powtarza się po pewnym okresie (np. po wygenerowaniu 4 miliardów liczb, otrzymujemy od nowa ten sam ciąg).

Jeśli cię zainteresował ten temat, to odsyłam do obszernego artykułu o generatorach liczb pseudolosowych, który znajduje się w naszym serwisie.

Wróćmy na ziemię. W języku C masz dostęp do generatora liczb pseudolosowych za pomocą dwóch funkcji:

srand(ziarno);

Funkcja srand() inicjuje generator liczb pseudolosowych. Jeśli mikrokontroler jest wyposażony w zegar czasu rzeczywistego, który działa na zasilaniu bateryjnym i mierzy czas niezależnie od wykonującego się programu, to jako ziarna można użyć wartości odczytanej z zegara jako liczby typu int. Funkcji srand() używamy w programie tylko jeden raz na samym początku.

Jeśli mikrokontroler nie posiada takiego zegara, to można wykorzystać pośrednio pamięć EPROM, która jest dostępna praktycznie w każdym mikrokontrolerze. Pamięć EPROM pamięta dane nawet po wyłączeniu zasilania. W pamięci tej tworzymy prosty licznik, którego zawartość zwiększamy o 1 (lub o inną wartość) przy każdym uruchomieniu programu. Następnie stan tego licznika wykorzystujemy jako ziarno dla funkcji srand(). Zagwarantuje to, że przy każdym uruchomieniu otrzymamy inny ciąg liczb pseudolosowych.

rand();

Funkcja jest bezargumentowa. Każde wywołanie daje liczbę pseudolosową z zakresu od 0 do 32767, czyli 15 najstarszych bitów wygenerowanej liczby pseudolosowej. Dlaczego tak dziwnie? Chodzi o rozkład. Stwierdzono, że te 15 bitów daje lepszą równomierność generowanych liczb niż inne bity liczby pseudolosowej tworzonej w generatorze.

Obie funkcje są zdefiniowane w pliku nagłówkowym stdlib.h.

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

#define MAXC 78

int main()
{
  int i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 0; i < 40; i++) printf("%d\n",rand());

  return 0;
}

W programie użyto nowej funkcji time(), która odczytuje czas. Funkcja ta zwykle nie jest dostępna we wszystkich mikrokontrolerach, ponieważ zależy od konkretnej konfiguracji sprzętowej. Funkcja time() zwraca liczbę sekund, które upłynęły od północy pierwszego stycznia 1970 roku (całkiem sporo). Jej wartość zmienia się co jedną sekundę. Parametrem jest wskaźnik miejsca w pamięci, w którym zostanie utworzona struktura opisująca czas. Jeśli w parametrze przekażemy wskaźnik pusty (NULL), to nic nie będzie tworzone, ponieważ NULL nie wskazuje żadnego obiektu. Tutaj wykorzystujemy time() do zainicjowania generatora pseudolosowego. Dzięki temu, przy każdym uruchomieniu programu otrzymamy inny ciąg liczb pseudolosowych. W ramach ćwiczenia spróbuj usunąć z programu wywołanie srand() i sprawdź co się stanie (program uruchom kilkakrotnie).

Funkcja rand() generuje liczby z zakresu od 0 do 32767 (0...2¹⁵ - 1). Co zrobić, jeśli potrzebujesz innego zakresu, np. od a do b? Aby z a otrzymać b należy do a dodać liczbę (b - a). Zatem liczby otrzymywane z rand() musisz zredukować do zakresu od 0 do (b - a). Pomoże ci w tym operacja modulo (%), czyli reszta z dzielenia. Aby otrzymać resztę z dzielenia w zakresie od 0 do (b - a) należy rand() podzielić przez (b - a) + 1. Otrzymujemy ostateczny wzór:

a + rand() % (b - a + 1)

Na przykład, chcesz generować wyniki rzutów kostką. Wyrażenie pseudolosowe o wartościach od 1 do 6 jest następujące (a = 1, b = 6) :

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

#define MAXC 78

int main()
{
  int i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 1; i <= 40; i++)
  printf("Rzut nr %2d, liczba oczek %d\n", i, 1+rand()%6);

  return 0;
}

Kolejny program "rzuca" kostką 6 milionów razy, i sprawdza, czy wypadło około miliona każdej z możliwych liczby oczek.

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

#define MAXC 78

int main()
{
  int t[] = {0,0,0,0,0,0},i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 0; i < 6000000; i++) t[rand()%6]++;
  for(i = 0; i < 6; i++)
  printf("%d: %7d\n", i + 1, t[i]);

  return 0;
}

Liczby pseudolosowe często stosujemy do mieszania zawartości tablic. Zadanie to rozwiązujemy następująco:

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

int main()
{
  int t[] = {0,1,2,3,4,5,6,7,8,9},i,i1,i2,x;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  printf("Przed: ");
  for(i = 0; i < 10; i++) printf("%2d",t[i]);

  // mieszamy
  for(i = 0; i < 30; i++)
  {
    i1 = rand() % 10; // losujemy indeksy
    i2 = rand() % 10;
    x  = t[i1]; t[i1] = t[i2]; t[i2] = x;
  }

  printf("\n\nPo : ");
  for(i = 0; i < 10; i++) printf("%2d",t[i]);
  printf("\n\n");

  return 0;
}

Za pomocą mieszania możesz napisać prosty program losujący liczby Multilotka (20 z 80).

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <locale.h>

int main()
{
  char m[80],r[10],x;
  int i,j,k,i1,i2;

  setlocale(LC_ALL,"");

  // inicjujemy generator LCG
  srand((int)time(NULL));

  // Wypełniamy tablicę bil m[]
  for(i = 0; i < 80; i++) m[i] = i + 1;

  for(k = 1; k <= 10; k++)
  {
    printf("Lowanie Multilotka nr %d\n",k);
    // mieszamy bile
    for(i = 0; i < 240; i++)
    {
      // losujemy indeksy
      i1 = rand() % 80;
      i2 = rand() % 80;

      // zamieniamy bile
      x = m[i1]; m[i1] = m[i2]; m[i2] = x;
    }

    // losujemy 20 pierwszych bil
    memcpy(r, m, 10);

    // sortujemy wylosowane bile rosnąco
    for(i = 8; i >= 0; i--)
    {
      x = r[i];
      for(j = i + 1; j < 10; j++)
        if(x <= r[j]) break;
        else r[j - 1] = r[j];
      r[j - 1] = x;
    }
    printf("Wyniki:");
    for(i = 0; i < 10; i++) printf(" %02d", r[i]);
    printf("\n\n");
  }

  return 0;
}

Specyfikacja %02d w tekście formatującym funkcji printf() oznacza format dziesiętny w polu o długości dwóch znaków z zerami wiodącymi.

Inne ciekawe zastosowanie liczb pseudolosowych wiąże się z szyfrowaniem tekstu. W czasie II Wojny Światowej Kwatera Główna Führera stosowała specjalną maszynę szyfrującą o nazwie Ultra.

Zasada działania tej maszyny polegała na tym, iż kody znaków były mieszane z ciągiem liczb pseudolosowych, które generowała maszyna na podstawie wprowadzonego wcześniej klucza oraz innych ustawień. My możemy postąpić podobnie: liczby pseudolosowe będzie generował generator pseudolosowy języka C. Kluczem natomiast będzie ziarno dla tego generatora. Jak napisaliśmy wcześniej, jeśli zainicjujemy generator takim samym ziarnem pseudolosowym, to wygeneruje on identyczny ciąg liczb pseudolosowych. Aby się o tym przekonać, uruchom poniższy program:

/* Liczby pseudolosowe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 31.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #include <locale.h> int main() { int t = (int)time(NULL); // zapamietujemy czas int i,j; setlocale(LC_ALL,""); for(i = 1; i < 10; i++) { srand(t); // ustawiamy generator LCG for(j = 0; j < 19; j ++) printf(" %03d", rand() % 1000); printf("\n\n"); } return 0; }

Program generuje 10 ciągów liczb pseudolosowych. Ponieważ przed generacją każdego ciągu inicjujemy generator pseudolosowy tym samym ziarnem, to generuje on taki sam ciąg liczb.

Na tym fakcie oprzemy algorytm szyfrujący/deszyfrujacy. Kluczem będzie wartość ziarna pseudolosowego jako liczba całkowita. Drugi fakt, to działanie sumy symetrycznej. Jeśli zastosujemy tę operację dwukrotnie z tym samym argumentem, to wynik wróci do postaci wyjściowej:

Zatem szyfrowanie lub deszyfrowanie polega na operacji różnicy symetrycznej kodu ASCII znaku z liczbą pseudolosową z generatora. Uruchom poniższy program:

/* Liczby pseudolosowe (C)2016 mgr Jerzy Wałaszek Data utworzenia: 31.10.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> int main() { int key,i; char t[80]; setlocale(LC_ALL,""); printf("Wpisz klucz: "); scanf("%d", &key); printf("Wpisz tekst (do 79 liter):\n\n"); gets(t); // to usuwa znak \n z wejścia gets(t); // to odczytuje właściwy wiersz // inicjujemy generator pseudolosowy srand(key); // szyfrujemy lub deszyfrujemy for(i = 0; t[i]; i++) t[i] ^= rand() % 32; // wyświetlamy wynik: printf("\n%s\n\n", t); return 0; }

W programie użyto dwukrotnie funkcji gets(). Jest to konieczne, ponieważ funkcja scanf() nie usuwa ze strumienia wejściowego znaku \n, który tam powstaje po naciśnięciu klawisza Enter, gdy użytkownik wprowadzi klucz. Z tego powodu pierwsza funkcja gets() odczyta pusty wiersz. Dopiero druga funkcja gets() odczyta właściwy wiersz do szyfrowania lub deszyfrowania. Oto wynik działania programu:

Wpisz klucz: 15 Wpisz tekst (do 79 liter): Atak o świcie na pozycje wroga w kwadracie Q17XL. Veqq5e,Ç{~ppl<by.wvdijtp>roodg$~.~}{t~trl` _'!CB0

Wpisz klucz: 15 Wpisz tekst (do 79 liter): Veqq5e,Ç{~ppl<by.wvdijtp>roodg$~.~}{t~trl` _'!CB0 Atak o świcie na pozycje wroga w kwadracie Q17XL.

Jak widzisz, cała potężna maszyna Ultra sprowadza się we współczesnym świecie do kilku linijek kodu w języku C.

Na szczęście język C przewiduje takie sytuacje i każdą zmienną możesz opatrzyć słówkiem angielskim słówkiem volatile (ulotny):

volatile typ zmienna;
typ volatile zmienna;

Od tego momentu mikroprocesor będzie zawsze odwoływał się bezpośrednio do zmiennej w pamięci. Nawet, gdy włączysz optymalizacje kodu.

Ze zmiennymi ulotnymi spotkasz się przy programowaniu tzw. przerwań (ang. interrupts).

Składnia jest następująca:

goto etykieta;

Etykieta jest nazwą, którą umieszczamy w programie w miejscu, do którego należy wykonać skok. Za nazwą etykiety należy wpisać dwukropek. Etykieta musi znajdować się w tej samej funkcji, w której umieszczono rozkaz goto. Nie wolno wykonywać skoków pomiędzy różnymi funkcjami.

/*
 Skoki
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 4.11.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

int main()
{
  int a;

  setlocale(LC_ALL,"");

jeszcze_raz: // tu jest miejsce docelowe skoku

  printf("Wpisz liczbe od 1 do 9: ");
  scanf("%d", &a);
  if(a < 1 || a > 9) goto jeszcze_raz; // skok
  printf("Dziekujemy, wpisana liczba to %d\n", a);

  return 0;
}

To samo da się otrzymać bez używania goto:

/*
 Skoki
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 4.11.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

int main()
{
  int a;

  setlocale(LC_ALL,"");

  while(1)
  {
    printf("Wpisz liczbe od 1 do 9: ");
    scanf("%d", &a);
    if(a < 1 || a > 9) continue;
    printf("Dziekujemy, wpisana liczba to %d\n", a);
    break;
  }

  return 0;
}

Funkcja również jest obiektem w pamięci i posiada swój adres. Pod tym adresem umieszczony jest kod funkcji, czyli ciąg rozkazów dla mikroprocesora, które ten wykonuje, gdy program daną funkcję wywoła. Z tego powodu nic nie stoi na przeszkodzie, aby istniały również wskaźniki do funkcji. Jednak musisz pamiętać, że wskaźnik w języku C to nie tylko sam adres (taki wskaźnik też istnieje: void *). To również typ wskazywanego obiektu. Wskaźnik do danej całkowitej nie jest tym samym co wskaźnik do danej zmiennoprzecinkowej. Chodzi o to, iż kompilator musi wiedzieć, jak ma interpretować daną wskazywaną przez wskaźnik. Również arytmetyka wskaźników odwzorowuję tę cechę: np. dodanie do wskaźnika liczby 1 oznacza przesunięcie jego adresu o tyle, ile wynosi rozmiar wskazywanego obiektu. Jest to bardzo przydatne przy odwoływaniu się do tablic, w których elementy są umieszczone w pamięci jeden obok drugiego.

Aby użyć danej funkcji, kompilator musi wiedzieć o niej kilka rzeczy:

• Liczbę argumentów
• Typy poszczególnych argumentów
• Typ zwracanego wyniku

Definicja wskaźnika do funkcji (ang. function pointer) wygląda następująco:

typ_wyniku (* wskaźnik)(typy_argumentów);

Na przykład, poniższa definicja:

float (*calc)(int *, float);

Definiuje wskaźnik o nazwie calc, który będzie wskazywał funkcję zwracającą w wyniku daną typu float i posiadającą dwa parametry: pierwszy typu wskaźnik do danej całkowitej int; drugi typu float.

Wskaźnik po utworzeniu należy odpowiednio zainicjować. Do tego celu wykorzystujemy znany nam już operator adresu & oraz nazwę funkcji, którą wskaźnik ma wskazywać.

wskaźnik = &funkcja;

Wywołanie funkcji, którą wskazuje wskaźnik wygląda następująco:

wskaźnik(argumenty);

lub

(* wskaźnik)(argumenty);

Uruchom poniższy program (przykład nieco naciągany, ale pokazujący ideę stosowania wskaźników do funkcji):

/* Wskaźniki do funkcji (C)2016 mgr Jerzy Wałaszek Data utworzenia: 5.11.2016 */ #include <stdio.h> #include <stdlib.h> #include <locale.h> // Zmienna globalna void (* func)(int); // Prototypy funkcji void f1(int); void f2(int); // Dwie funkcje, które będzie wskazywał func void f1(int a) { printf("Jestem w funkcji f1(), a = %d\n", a); func = &f2; } void f2(int a) { printf("Jestem w funkcji f2(), a = %d\n", a); func = &f1; } int main() { int i; setlocale(LC_ALL,""); func = &f1; for(i = 1; i < 10; i++) func(i); return 0; }

Program działa następująco:

Wyszukiwanie binarne

Wskaźniki do funkcji są wykorzystywane przez kilka funkcji bibliotecznych. Jedna z nich realizuje tzw. wyszukiwanie binarne (ang. binary search). Funkcję tę wykorzystuje się na większych mikrokontrolerach, które posiadają dużo pamięci RAM.

Zwykłe wyszukiwanie liniowe (ang. linear search) polega na przeglądaniu kolejnych elementów tablicy i porównywaniu ich z wartością poszukiwaną. Jeśli zostanie znaleziona, to zatrzymujemy dalsze przeszukiwanie tablicy i zwracamy wskaźnik elementu, którego wartość jest równa poszukiwanej. Jeśli natomiast osiągniemy ostatni element element tablicy i poszukiwanej wartości w tablicy nie znajdziemy, to zwracamy wskaźnik pusty NULL.

Dla dużych tablic czas wyszukiwania elementu jest statystycznie liniowo proporcjonalny do ilości elementów n, dlatego algorytm ten nosi nazwę wyszukiwania liniowego. O takim algorytmie mówimy, że ma liniową złożoność obliczeniową. Jeśli liczba elementów tablicy wzrośnie np. 256 razy, to średni czas wyszukiwania elementu również wzrośnie około 256 razy.

Okazuje się, że można znacznie przyspieszyć czas wyszukiwania elementu, jeśli tablica będzie posortowana np. rosnąco. Postępujemy wtedy następująco:

Zakres poszukiwań definiują dwa indeksy: i_p (indeks początku) i i_k (indeks końca):

Komórki tablicy od t[i_p] do t[i_k] nazwijmy partycją. Partycja będzie zawierała komórki, jeśli i_p ≤ i_k. Jeśli ten warunek nie jest spełniony, mamy pustą partycję, wtedy kończymy i zwracamy adres pusty NULL.

Wyznaczamy komórkę leżącą w środku partycji. Jej indeks oznaczmy jako i_s (indeks środka):

Sprawdzamy, czy komórka t[i_s] zawiera poszukiwaną wartość. Jeśli tak, to kończymy, zwracając adres tej komórki.

Jeśli nie, to wykorzystujemy fakt uporządkowania tablicy. Skoro elementy są uporządkowane rosnąco, to na prawo od komórki t[i_s] mamy elementy równe lub większe od niej. Na lewo mamy elementy równe lub mniejsze od t[i_s]:

Sprawdzamy teraz jak się ma poszukiwana wartość do t[i_s]. Wiemy, że nie jest równa, bo to sprawdziliśmy wcześniej. Może być zatem albo mniejsza od t[i_s], albo większa od t[i_s]. Jeśli jest mniejsza, to na pewno nie pojawi się na prawo od t[i_s], ponieważ tam są elementy większe lub równe t[i_s] (ze względu na uporządkowanie tablicy). Skoro tak, to za nową partycję przyjmujemy elementy o indeksach od i_p do i_s - 1:

Czyli, i_p zostawiamy w spokoju, a w i_k umieszczamy i_s - 1.

Jeśli poszukiwana wartość jest większa od t[i_s], to będziemy jej poszukiwać na prawo od t[i_s], ponieważ na lewo są elementy mniejsze lub równe t[i_s]. Za nową partycję przyjmiemy elementy o indeksach od i_s + 1 do i_k:

Zwróć uwagę, że dwa porównania powodują ograniczenie do połowy ilość elementów do przeszukania. Po wyznaczeniu nowej partycji proces poszukiwania powtarzamy aż do znalezienia elementu lub do osiągnięcia partycji pustej.

Okazuje się, że tak skonstruowany algorytm wyszukuje daną w czasie proporcjonalnym do log₂n. Jest to bardzo korzystne. Jeśli liczba elementów wzrośnie 256, to średni czas wyszukiwania wzrośnie jedynie log₂256 = 8 razy! O takim algorytmie mówimy, że ma złożoność obliczeniową logarytmiczną. Wyszukiwanie binarne stosuje się zwykle dla dużych tablic – przy kilku elementach zysk jest niewielki w porównaniu z algorytmem wyszukiwania liniowego.

W bibliotece standardowej (plik nagłówkowy stdlib.h) jest funkcja bsearch(), która realizuje wyszukiwanie binarne w tablicy i posiada następującą składnię:

bsearch(poszukiwane, tablica, liczba_elementów, rozmiar, funkcja_porównawcza);

int funkcja(const void * a, const void * b);

Uruchom program:

/*
 Wskaźniki do funkcji
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 8.11.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

#define MAX 160

// Funkcja porównująca
//--------------------
int comp(const void * a, const void * b)
{
  return *(int *) a - * (int *) b;
}

int main()
{
  int t[MAX],i,s,*p;

  setlocale(LC_ALL,"");

  // inicjujemy generator pseudolosowy
  srand((int)time(NULL));

  // w t umieszczamy ciąg rosnący:
  t[0] = rand() % 10; // pierwsza liczba 0...9
  for(i = 1; i < MAX; i++) t[i] = t[i - 1] + (rand() % 4);

  // losujemy element
  s = t[0] + rand() % (t[MAX - 1] - t[0] + 1);

  // szukamy
  p = bsearch(&s,t,MAX,sizeof(t[0]),comp);

  // wypisujemy wyniki:
  for(i = 0; i < MAX; i++)
  if(p == &t[i]) printf("[%3d]",t[i]);
  else           printf(" %3d ",t[i]);
  printf("\n\n");
  if(p) printf("%d jest w t[%d]\n\n", s , p-t);
  else  printf("%d nie ma w t[]\n\n",s);

  return 0;
}

Sortowanie szybkie

Sortowanie bąbelkowe oraz sortowanie przez wstawianie sortują tablicę w czasie proporcjonalnym do kwadratu liczby elementów n². Oznacza to, że jeśli zwiększysz liczbę elementów w tablicy 16 razy, to czas sortowania wzrośnie 16² = 256 razy. Dla małych tablic nie jest to zbyt istotne. Jednak przy dużych tablicach (np. długiej serii pomiarów z jakiegoś czujnika) czas przetwarzania może okazać się zbyt długi. Tutaj z pomocą przychodzi nam algorytm sortowania szybkiego (ang. quick sort), który został opracowany przez brytyjskiego informatyka Tony'ego Hoare'a.

Algorytm sortowania szybkiego opiera się na zasadzie dziel i zwyciężaj (ang. divide and conquer).  W informatyce wiele problemów da się szybciej rozwiązać, jeśli przyjmiemy jakąś mądrą strategię postępowania. Z mojego doświadczenia wynika, że często algorytm prosty działa długo na danym zestawie danych, a algorytm bardziej zaawansowany działa dużo szybciej. Zasada dziel i zwyciężaj dzieli się na trzy etapy:

1. Duży problem podziel na mniejsze podproblemy.
2. Każdy z podproblemów rozwiąż osobno.
3. Rozwiązania podproblemów połącz ze sobą, tak aby utworzyły rozwiązanie problemu głównego.

Jak to się ma do sortowania? Załóżmy, że mamy partycję startową (patrz poprzedni rozdział) zdefiniowaną przez indeksy i_p (początek) i i_k (koniec):

Partycja ta obejmuje wszystkie elementy tablicy od t[i_p] do t[i_k].  Jeśli partycja jest pusta, i_p > i_k, to kończymy. Inaczej w partycji wybieramy dowolny element, który nazwiemy sobie piwotem v (elementem zwrotnym):

Następnie elementy partycji przenosimy, tak aby przed piwotem znalazły się elementy mniejsze lub mu równe, a za piwotem elementy większe lub mu równe.  Oczywiście końcowa pozycja piwota może ulec zmianie w stosunku do jego pozycji pierwotnej:

Zwróć uwagę, że element będący piwotem znajduje się już na swoim właściwym miejscu, tzn. nie musimy go już nigdzie przenosić w tablicy. Reszta elementów jest częściowo uporządkowana (względem piwota, lecz nie względem siebie). Umówmy się, że powstają w ten sposób dwie nowe partycje: lewa o indeksach od i_p do i_v-1 i prawa o indeksach od i_v+1 do i_k. Każdą z tych partycji sortujemy w ten sam sposób, tzn. wyznaczamy w nich piwoty i reorganizujemy elementy, tak aby przed piwotem znalazły się elementy mniejsze lub równe, a za piwotem elementy większe lub równe. Powstaną teraz 4 partycje:

Każdą z nowych partycji sortujemy w ten sam sposób. Za każdym razem uporządkowanie zbioru rośnie (rozwiązanie małych problemów, czyli sortowanie partycji, przybliża nas do rozwiązania problemu głównego, czyli posortowania całego zbioru). Gdy partycje staną się puste lub jednoelementowe, sortowanie można przerwać, a zbiór będzie posortowany. Okazuje się, że tak przeprowadzone sortowanie wykonuje się w czasie proporcjonalnym do n·log₂(n). Jest to dużo korzystniejsze od n². Jeśli zwiększymy liczbę elementów 16 razy, to czas sortowania wzrośnie 16·log₂16 = 16·4 = 64 razy (poprzednio wzrost wyniósł 16² = 256 razy). O takim algorytmie mówimy, że ma złożoność obliczeniową liniowo-logarytmiczną.

Jeśli cię ten temat zainteresował, to przeczytaj nasz artykuł o sortowaniu szybkim.

W bibliotece standardowej (plik nagłówkowy stdlib.h) jest funkcja qsort(), która dokonuje sortowania szybkiego tablicy. Posiada następującą składnię:

qsort(tablica, liczba_elementów, rozmiar, funkcja_porównawcza);

int funkcja(const void * a, const void * b);

Uruchom program:

/*
 Wskaźniki do funkcji
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 8.11.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

#define MAX 200

// Funkcja porównująca
//--------------------
int comp(const void * a, const void * b)
{
  return *(int *) a - * (int *) b;
}

int main()
{
  int t[MAX],i;

  setlocale(LC_ALL,"");

  // inicjujemy generator pseudolosowy
  srand((int)time(NULL));
  // w t umieszczamy ciąg liczb pseudolosowych 100...999:
  for(i = 0; i < MAX; i++) t[i] = 100 + (rand() % 900);
  printf("PRZED SORTOWANIEM SZYBKIM:\n\n");
  for(i = 0; i < MAX; i++) printf("%4d",t[i]);
  printf("\n\n");
  // sortujemy szybko
  qsort(t,MAX,sizeof(t[0]),comp);
  printf("PO SORTOWANIU SZYBKIM:\n\n");
  for(i = 0; i < MAX; i++) printf("%4d",t[i]);
  printf("\n\n");

  return 0;
}

To już wszystko w tym kursie. Resztę poznasz w części praktycznej, gdy będziemy programować mikrokontrolery w konkretnych projektach.