WDP Wprowadzenie do programowania

Wykład 2. Nieformalne wprowadzenie do programowania

Na poprzednim wykładzie rozważaliśmy algorytmy znajdowania największego wspólnego dzielnika i 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ą.

#Wykład4

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 rozdzielamy średnikami i wykonujemy po kolei.

Kolejno omówimy te konstrukcje.

• Instrukcja przypisania jest postaci v:=E, gdzie przez voznaczamy 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 {\tt v}.

Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji i:=i+1. 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. Trzy 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.

• {Demonstracja Flash}

• Instrukcja warunkowa jest postaci \\

  {\tt if B then I1 else I2},\\

  gdzie warunek {\tt B} jest wyrażeniem logicznym, dającym wartości {\tt true} lub {\tt false} (prawda lub fałsz), a {\tt I1} oraz {\tt 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 {\tt b} jest spełniony, czy nie.

  Wykonanie instrukcji warunkowej odbywa się również na dwa takty

  najpierw obliczana jest wartość warunku {\tt B} i jeśli jest ona równa {\tt true}, to wykonujemy {\tt I1}, a w przeciwnym razie {\tt I2}. Gdy nie chcemy, aby cokolwiek wykonywało się w przeciwnym razie, wówczas nie piszemy {\tt „else I2”} i wtedy w przypadku, gdy wartość warunku jest {\tt 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ć.

• Instrukcja pętli jest postaci \\

  {\tt while B do I},\\

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

Jeśli chcemy zaznaczyć, że zależy nam na wykonaniu ciągu instrukcji, to ciąg ten ujmujemy w nawiasy {\tt 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 {\tt not, and, or} z umową, że {\tt not} wiąże najsilniej, {\tt and} słabiej, a {\tt 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: \begin{verbatim} i>=0 (i>=0) and (j>=i) not ((k<n) or (j<n)) \end{verbatim}

{\BF 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ć {\tt 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ę {\tt tablicami}. Jeśli {\tt A} jest tablicą, to {\tt 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 \begin{verbatim} for k:=1 to n do I \end{verbatim} na oznaczenie następującego równoważnego kodu \begin{verbatim} k:=1; while k<=n do

begin
 I;
 k:=k+1
end

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