WDP Wprowadzenie do programowania

<<< Powrót

Nieformalny wstęp do programowania

W poprzednim wykładzie rozważaliśmy algorytmy znajdowania największego wspólnego dzielnika. Po precyzyjnym wyrażeniu definicji istoty algorytmu za pomocą wzorów rekurencyjnych, zostały one zilustrowane w postaci kodu programu, jednak bez głębszego komentarza dotyczącego tego, jak zastosowane konstrukcje programistyczne działają. W uproszczonej wersji programy konstruujemy z trzech rodzajów instrukcji:

Instrukcji przypisania

Przykład

a:=a-b;

Instrukcji warunkowej

Przykład

if a < b then c:=a else c:=b;

Instrukcji pętli

Przykład

while b > 0 do b:=b div 2;

Instrukcje oddzielamy średnikami i wykonujemy po kolei.

Kolejno omówimy te konstrukcje.

Instrukcja przypisania

Instrukcja przypisania jest postaci v:=E, gdzie przez v oznaczamy zmienną, czyli obiekt, który może przyjmować wartości typu określonego przy wcześniejszej deklaracji, a przez E wyrażenie pochodzące z dziedziny algorytmicznej, której nośnikiem jest typ zmiennej. Wyrażenie jest termem, w skład którego wchodzą stałe, zmienne i operacje dostępne w tej dziedzinie.

Wykonanie instrukcji przypisania odbywa się na dwa takty. Najpierw wyliczana jest wartość wyrażenia E występującego po prawej stronie instrukcji przypisania (w wyrażeniu może wystąpić w szczególności zmienna v z lewej strony przypisania i wtedy bierze się jej starą wartość), a potem obliczoną wartość przypisuje się zmiennej v.

Przykład ilustrujący ilustruje kolejność czynności przy wykonaniu instrukcji przypisania. Zakładamy w nim, że w pamięci komputera są zarezerwowane komórki na wartości wszystkich zmiennych programu. W animacji odwołujemy się do wartości tych komórek. Znaki zapytania oznaczają, że zmienna nie ma jeszcze nadanej wartości. Zakładamy, że ten mały fragment programu jest częścią większej całości i pomijamy szczegóły dotyczące kontekstu. Przykład w powiększeniu.

Plik:Przypisanie1.svg

Instrukcja warunkowa

Instrukcja warunkowa jest postaci if B then I1 else I2 gdzie warunek B jest wyrażeniem logicznym, dającym wartości true lub false (prawda lub fałsz), a I1 oraz I2 są instrukcjami. Instrukcja warunkowa pozwala nam wybrać jeden z dwóch wariantów dalszego wykonania programu w zależności od tego, czy warunek b jest spełniony, czy nie.

Wykonanie instrukcji warunkowej odbywa się również na dwa takty: najpierw obliczana jest wartość warunku B i jeśli jest ona równa true, to wykonujemy I1, a jeżeli nie, wykonujemy I2. Gdy nie chcemy, aby cokolwiek wykonywało się w tym drugim przypadku, wówczas nie piszemy „else I2” i wtedy w przypadku, gdy wartość warunku jest false, nic się nie dzieje. Przykład takiej instrukcji mieliśmy w algorytmie Euklides1 i Euklides3: gdy zmienna a miała wartość większą od b, nie trzeba było niczego zamieniać.

Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji warunkowej. Przykład w powiększeniu.

Plik:WDP-warunek-else1.svg

Instrukcja pętli

Instrukcja pętli jest postaci while B do I gdzie B jest warunkiem logicznym, a I instrukcją, którą pętla ma powtarzać, aż do spełnienia warunku B. Wykonanie pętli zaczyna się od obliczenia wartości warunku. Jeśli wartość ta wynosi false, to pętla nie robi niczego i kończy swoje działanie, ale jeśli wynosi true, to pętla wykonuje instrukcję I, a następnie wraca do sprawdzenia warunku B. Wykonuje tę sekwencję tak długo, aż warunek B przestanie być spełniony. Może się zdarzyć, że warunek B nigdy nie przestanie być spełniony i pozostanie prawdziwy na zawsze. Program wtedy nie zatrzyma się nigdy i mówimy o takiej sytuacji, jako o zapętleniu programu.

Jeśli chcemy zaznaczyć, że zależy nam na wykonaniu ciągu instrukcji, to ciąg ten ujmujemy w nawiasy begin ... end.

Na razie będziemy używali jedynie zmiennych o wartościach całkowitoliczbowych, a w dziedzinie algorytmicznej będą się znajdowały operacje +, -, -, *, /, mod (gdzie dwa minusy nie są pomyłką, tylko zgodnie z tradycją oznaczają dwie różne operacje: jednoargumentową tworzenia liczby przeciwnej i dwuargumentową odejmowania; niestety są one tradycyjnie oznaczane tym samym znakiem) oraz relacje $<,<=,>,>=,=$ oraz $<>$, przy czym znaki relacji kolejno oznaczają mniejszość, mniejszość lub równość, większość, większość lub równość, równość i różność. Umawiamy się ponadto, że zachowane są tradycyjne priorytety działań (czyli mnożenie i dzielenie wiąże mocniej niż dodawanie i odejmowanie, minus jednoargumentowy wiąże silniej od mnożenia i dzielenia, a działania są wykonywane od lewej do prawej). W wyrażeniach logicznych używamy standardowych spójników logicznych not, and, or z umową, że not wiąże najsilniej, and słabiej, a or najsłabiej. Wolno nam tworzyć wyrażenia logiczne przez porównanie wartości całkowitoliczbowych za pomocą jednego z powyższych sześciu operatorów relacji. Dopuszczamy także użycie nawiasów, które służą do wymuszania właściwej kolejności obliczeń zarówno w wyrażeniach arytmetycznych, jak i logicznych. Oto kilka przykładów poprawnych wyrażeń logicznych:

i>=0
(i>=0) and (j>=i)
not ((k<n) or (j<n))

Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji pętli. Przykład w powiększeniu.

Plik:WDP-petla1.svg

Zmienne indeksowane (tablice)

Często działamy na ciągach zmiennych tego samego typu. Przykładowo taka sytuacja występuje gdy chcemy posortować jakieś dane, albo sprawdzić, czy w zestawie danych znajduje się zadana wartość. Wygodnie wtedy jest używać zmiennych indeksowanych, które realizują pojęcie skończonego ciągu. Zmienna taka ma wtedy jeden wspólny identyfikator, a kolejne elementy oznacza się kolejnymi indeksami, które zazwyczaj są liczbami naturalnymi, choć nie jest to konieczne i w niektórych językach programowania dopuszcza się indeksowanie również innymi typami dyskretnymi (np. znakami).

Zmienne indeksowane nazywają się tablicami. Jeśli A jest tablicą, to A[i] jest jej i-tym elementem. Umawiamy się, że indeksem tablicy może być dowolne poprawne wyrażenie, ale pod warunkiem, że jego wartość mieści się w zakresie określoności tablicy. Zatem odwołanie do elementu spoza zakresu indeksów traktowane jest jako poważny błąd. Często powoduje przerwanie programu bez ostrzeżenia.

W przykładowych zadaniach poniżej proponujemy przećwiczenie podstawowych algorytmów na tablicach. Zakładamy zazwyczaj, że tablica jest zadeklarowana w zakresie $1..n$. Dla ułatwienia zrozumienia zapisu pewnych algorytmów stosujemy skrót notacyjny

for k:=1 to n do I

na oznaczenie następującego równoważnego kodu

k:=1;
while k<=n do
  begin
   I;
   k:=k+1
  end

Konwencja ta powoduje, że dla każdej wartości indeksu, poczynając od $1$, a kończąc na $n$, wykonamy instrukcję I. Zakresy pętli for mogą być dowolnymi wyrażeniami dającymi wartości całkowite.