Wstęp do programowania w języku C/Dziedzina algorytmiczna

Dziedzina algorytmiczna, typy danych, stałe i zmienne. Instrukcja przypisania. Konwersja typów.

Dziedzina algorytmiczna

Dziedziną algorytmiczną nazywamy system

${𝒜}=<A;r_1,\dots ,r_k;f_1,\dots ,f_l;c_1,\dots ,c_m>$,

gdzie A jest pewnym niepustym zbiorem, $r_1,\dots ,r_k$ są relacjami określonymi na elementach tego zbioru, $f_1,\dots ,f_k$ są funkcjami określonymi na elementach ze zbioru A i dającymi wynik w zbiorze A, zaś $c_1,\dots ,c_m$ są stałymi z A, tzn. wyróżnionymi elementami z tego zbioru. Funkcje $f_1,\dots ,f_k$ nie muszą być całkowite, tzn. nie muszą być określone dla każdego zestawu argumentów.

Przykłady dziedzin algorytmicznych

1. Zbiór liczb rzeczywistych ${ℛ}$ z operacjami (funkcjami dwuargumentowymi) +, -, *, /, relacjami <, = i stałymi 0, 1. Przy rozwiązywaniu równania kwadratowego dziedzina ta jest jeszcze rozszerzona o funkcję $\sqrt{}$.
2. Zbiór liczb całkowitych ${𝒵}$ z operacjami +, -, *, div, relacjami <, = i stałymi 0, 1. Zbiór liczb całkowitych jest dziedziną algorytmiczną w problemie obliczania największego wspólnego dzielnika dwóch liczb całkowitych dodatnich. W algorytmie 2 użyta została operacja ``modulo. Operację te można wydefiniować za pomocą dzielenia, mnożenia i odejmowania: $a\text{ mod }b=a-(b*(a\text{ div }b)$
3. Zbiór wartości logicznych ${ℬ}=\{0,1\}$ z operacjami $\vee ,\wedge ,\mathrm{\neg }$.

Typy danych

W językach programowania odpowiednikiem dziedzin algorytmicznych są typy danych. W języku C liczbą rzeczywistym odpowiadają trzy typy: float, double i long double. Typ float jest podzbiorem zbioru liczb rzeczywistych (zazwyczaj, ponieważ to zależy od reprezentacji) z przedziału $[-3.4*10^{38},3.4*10^{38}]$, najmniejsza reprezentowana liczba dodatnia wynosi $1.17*10^{-38}$.

Typ double jest podzbiorem zbioru liczb rzeczywistych z przedziału $[-1.79*10^{308},1.79*10^{308}]$, najmniejsza reprezentowana liczba dodatnia wynosi $2.22*10^{-308}$.

Typ long double jest podzbiorem zbioru liczb rzeczywistych z przedziału $[-1.1*10^{4932},1.1*10^{4932}]$, najmniejsza reprezentowana liczba dodatnia wynosi $3.4*10^{-4932}$.

Do obliczeń na liczbach rzeczywistych zaleca się używanie typu double. W każdym razie, w dalszej części wykładu, do reprezentowania liczb rzeczywistych będziemy używali typu double.

W języku C liczbą całkowitym odpowiadają także trzy typy: short int, int i long int różniące się zakresem reprezentowanych liczb. W praktyce używa się typu int lub long int. Zazwyczaj typ int reprezentuje wszystkie liczby całkowite z przedziału [-32768,32767], a typ long int reprezentuje wszystkie liczby całkowite z przedziału [-2147483648,2147483647]. W zależności od potrzeb będziemy do reprezentacji liczb całkowitych używali obu typów. W języku C nie ma typu logicznego. Na następnych wykładach pokażemy w jaki sposób temu zaradzić.

Typy rzeczywiste i całkowite nazywamy typami prostymi. Nazwa proste oznacza, że typy te są niepodzielne i mogą być używane do tworzenia typów złożonych. Do typów prostych zaliczamy jeszcze typ znakowy char. Elementami tego typu są wszystkie znaki dostępne na danej maszynie, a w szczególności duże i małe litery angielskiego alfabetu oraz cyfry.

Zmienne

Spróbujmy znaleźć największy wspólny dzielnik liczb 248 i 364 wykonując ręcznie algorytm "z resztą" z poprzedniego wykładu.

m           n         r
248         364       248

m           n         r
248         364       248
364         248       116
248         116       132
132         116       16
116         16        4
16          4         0

NWD(248,364) = 4

W trakcie wykonywania algorytmu zmieniały się wartości m, n i r. Gdybyśmy używali ołówka i gumki nie musielibyśmy wypisywać trzech słupków liczb, a tylko w trzech różnych miejscach kartki (tablicy), oznaczonych m, n i r, zapisywać ostatnio policzone, odpowiadające im wartości, wycierając wcześniej wartości już nieaktualne. Należy przy tym być ostrożnym i nie wycierać liczb, których jeszcze nie wykorzystaliśmy. Zauważmy, że w trakcie ręcznego wykonywania algorytmu wyniki pośrednie zapisywaliśmy w ustalonych miejscach kartki (tablicy), i żeby się nie pomylić w trakcie obliczeń miejsca te jednoznacznie oznaczyliśmy (nazwaliśmy) m, n i r. W rzeczywistości do wykonania algorytmu używaliśmy trzech zmiennych. Zmienne to najprostsze struktury danych służące do zapamiętywania elementów danego typu. Zajmują one pewien obszar w pamięci operacyjnej komputera, którego rozmiar i sposób interpretacji określony jest przez typ zmiennej. W języku C zmienne przed użyciem powinny być zadeklarowane. Deklarując zmienną podajemy jej typ i nazwę. Oto przykłady deklaracji zmienny różnych typów.

int wys; /* deklaracja zmiennej typu 
            int o nazwie wys */
double pole; /* deklaracja zmiennej 
                typu double o nazwie pole */

Jeżeli chcemy zadeklarować kilka zmiennych tego samego typu, to podajemy najpierw identyfikator typu a potem listę nazw zmiennych pooddzielanych przecinkami.

int wys, szer, dl, obj;
int n, m, r;
char litera1, litera2;

Uwaga: każda pełna deklaracja zmiennej (zmiennych) kończy się średnikiem (';')

Przypisanie

Zmiennym można nadawać (oraz zmieniać) wartości za pomocą instrukcji przypisania. Dla przykładu, w wyniku wykonania instrukcji

wys = 10;
szer = 5;
dl = 20;

zmiennym wys, szer i dl zostaną przypisane (nadane) wartości, odpowiednio, 10, 5 i 20. Zmienna, która ma nadaną wartość nazywamy zmienną zainicjalizowaną. Zmienne zainicjalizowane mogą występować w wyrażeniach po prawej stronie instrukcji przypisania i służyć do obliczania nowych wartości innych zmiennych (lub nawet tej samej zmiennej), jak np.

obj = wys*szer*dl;
m = 2*m;

Inicjalizacji zmiennych można dokonywać podczas ich deklaracji, jak np.

int wys = 10, szer = 5, dl = 20;

Początkową wartość zmiennej typu prostego można także wczytać za pomocą funkcji scanf. Wartość zmiennej można wypisać za pomocą printf. Zasady wczytywania i wypisywania zostaną omówione na ćwiczeniach.

Oto wzór na przybliżoną wartość silni: $n!=1*2*3*\dots *n\approx \sqrt{2\pi n}(n/e{)}^n$ Poniższy program oblicza wartość n! dla wejściowej wartości n.

#include <stdio.h>
#include <math.h>

main()
{
  long int n;
  double n_silnia;

  printf(" n < %d"); scanf("%d", &n);

  n_silnia = sqrt(2*3.14*n)*pow(n/2.71, n);

  printf("%d! = %10.3e\n", n_silnia);

  return 0;
}

Stałe

Oto czytelniejsza wersja tego programu, w którym zdefiniowano dwie stałe pi i e.

#include <stdio.h>
#include <math.h>

#define pi 3.14
#define e 2.71

main()
{
  long int n;
  double n_silnia;

  printf(" n < %d"); scanf("%d", &n);

  n_silnia = sqrt(2*pi*n)*pow(n/e, n);

  printf("%d! = %10.3e\n", n_silnia);

  return 0;
}

Makrodefinicje #define utożsamiają nazwy pi i e ze stałymi liczbowymi 3.14 i 2.71. Nazwy pi i e nie mogą pojawić się po lewej stronie instrukcji przypisania. Każde wystąpienie pi w wyrażeniu jest zamieniane na 3.14, natomiast wystąpienia e są zamieniane na 2.71. pi i e są stałymi w powyższym programie.

Identyfikatory

Jak można było zauważyć do nazywania różnych składników w naszych programach (zmiennych, funkcji, stałych) używaliśmy różnych nazw, które te składniki jednoznacznie identyfikowały. Te nazwy to identyfikatory. W języku C identyfikatorem może być dowolny napis zbudowany z liter, cyfr i znaku podkreślenia '_', pod warunkiem że zaczyna się od litery lub '_'.

Oto przykłady poprawnych identyfikatorów: szer_1, szer_2, Wys_1, Czy_juz_koniec.

Te identyfikatory są niepoprawne: 1wys, Czy-juz-koniec. W języku C rozróżniane są duże i małe litery. Zatem identyfikatory wys, Wys, WYS są różnymi identyfikatorami.

Słowa kluczowe języka C nie mogą być używane jako identyfikatory. Oto lista słów kluczowych języka C.

auto break case char const continue default do
double else enum extern float for goto if
int long register return short signed 
sizeof static struct switch typedef union
unsigned void volatile while

Wyrażenia

Podstawą języka C są wyrażenia. Wyrażeniem w danej dziedzinie algorytmicznej jest algorytmem wyznaczania wartości z dziedziny, w której operacjami podstawowymi są dostępne operacje z tej dziedziny, a kolejność obliczeń jest wyznaczona przez nawiasy, priorytety i wiązania operatorów.\\ Do najważniejszych grup operatorów w języku C można zaliczyć:

• operatory arytmetyczne: +, -, *, /, %, gdzie +, -, * to, odpowiednio, dodawanie, odejmowanie i mnożenie zarówno na liczbach całkowitych, jak i rzeczywistych, / oznacza dzielenie dla liczb rzeczywistych i dzielenie całkowite dla liczb całkowitych, natomiast % oznacza resztę z dzielenia dla liczb całkowitych. Mnożenie, dzielenie i "branie reszty" mają taki sam priorytet. W przypadku występowania tylko tych operatorów obliczenia są wykonywane kolejno od strony lewej do prawej. Dodawanie i odejmowanie mają taki sam priorytet, ale niższy od mnożenia, dzielenia i "brania reszty". W wypadku występowania tylko dodawania i odejmowania obliczenia są wykonywane od strony lewej do prawej. Operatory '+' i '-' mogą występować unarnie i wtedy mają najwyższy priorytet. Operatory unarne są wykonywane od strony prawej do strony lewej.
• operatory porównywania: <, >, <=, >=, ==, !=. Cztery pierwsze operatory mają taki sam priorytet. Dwa ostatnie mają też ten sam priorytet, ale niższy od priorytetu czterech pierwszych. Gdy w wyrażeniu występują operatory porównywania o tym samym priorytecie, to operacje są wykonywane od strony lewej do prawej.
• operatory logiczne: !, &&, || - negacja, koniunkcja i alternatywa (odpowiednio). Operatory logiczne zostały podane w kolejności priorytetów od najwyższego do najniższego. Negacja jest opeartorem unarnym i ma taki sam priorytet jak unarne '+' i '-'. Koniunkcja i alternatywa mają niższy priorytet od operatorów arytmetycznych i porównywania.

Konwersja

Co się dzieje, gdy w wyrażeniu arytmetycznym występują operandy różnych typów? W tej chwili ograniczymy się tylko do typów int, long int i double. Ogólna zasada mówi, że typ wyniku wyrażenia będzie "największym" typem spośród typów operandów w nim występujących, przy czym kolejność typów od największego do najmniejszego jest następująca: double, long int, int. Jeżeli po lewej stronie instrukcji przypisania jest zmienna innego typu niż typ wyniku wyrażenia z prawej strony, to nie ma problemu, gdy typ wyniku jest mniejszy od typu zmiennej. W przeciwnym razie przy zamianie long int na int może zostać odrzucona część najbardziej znaczących cyfr, a przy zamianie liczb rzeczywistych na całkowite jest odrzucana część ułamkowa liczby rzeczywistej. Reguły te nie są zbyt precyzyjne, ale dokładniej o konwersji będziemy mogli mówić dopiero po zapoznaniu się ze sposobami reprezentacji obiektów w komputerze.