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

  {\tt a:=a-b}

• Instrukcji warunkowej\\

  -przykład

  {\tt if a0 do b:=b div 2}

Instrukcje rozdzielamy średnikami i wykonujemy po kolei.

Kolejno omówimy te konstrukcje.

• Instrukcja przypisania jest postaci \\

  {\tt v

  =E}, \\

  gdzie przez {\tt v}oznaczamy zmienną, czyli obiekt, który może przyjmować wartości typu określonego przy wcześniejszej deklaracji, a przez {\tt 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 {\tt E} występującego po prawej stronie instrukcji przypisania (w wyrażeniu może wystąpić w szczególności zmienna {\tt 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 {\tt 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.