WDP Wprowadzenie do programowania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 2: Linia 2:
  
 
=Nieformalny wstęp do programowania=
 
=Nieformalny wstęp do programowania=
Na 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:
+
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'''
 
'''Instrukcji przypisania'''
Linia 27: Linia 27:
  
 
==Instrukcja przypisania==
 
==Instrukcja przypisania==
'''Instrukcja przypisania''' jest postaci <tt> v:=E,</tt> gdzie przez <tt> v</tt> oznaczamy zmienną, czyli obiekt, który może przyjmować wartości typu określonego przy wcześniejszej deklaracji, a przez <tt>E</tt> 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.  
+
'''Instrukcja przypisania''' jest postaci <tt> v:=E</tt>, gdzie przez <tt> v</tt> oznaczamy zmienną, czyli obiekt, który może przyjmować wartości typu określonego przy wcześniejszej deklaracji, a przez <tt>E</tt> 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</tt> występującego po prawej stronie instrukcji przypisania (w wyrażeniu może wystąpić w szczególności zmienna <tt>v</tt> z lewej strony przypisania i wtedy bierze się jej starą wartość), a potem obliczoną wartość przypisuje się zmiennej <tt> v</tt>.  
 
Wykonanie instrukcji przypisania odbywa się na dwa takty. Najpierw wyliczana jest wartość wyrażenia <tt>E</tt> występującego po prawej stronie instrukcji przypisania (w wyrażeniu może wystąpić w szczególności zmienna <tt>v</tt> z lewej strony przypisania i wtedy bierze się jej starą wartość), a potem obliczoną wartość przypisuje się zmiennej <tt> v</tt>.  
Linia 40: Linia 40:
 
gdzie warunek <tt> B</tt> jest wyrażeniem logicznym, dającym wartości <tt>true</tt> lub <tt>false</tt> (prawda lub fałsz), a <tt>I1</tt> oraz <tt>I2</tt> 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</tt> jest spełniony, czy nie.  
 
gdzie warunek <tt> B</tt> jest wyrażeniem logicznym, dającym wartości <tt>true</tt> lub <tt>false</tt> (prawda lub fałsz), a <tt>I1</tt> oraz <tt>I2</tt> 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</tt> jest spełniony, czy nie.  
  
Wykonanie instrukcji warunkowej odbywa się również na dwa takty: najpierw obliczana jest wartość warunku <tt>B</tt> i jeśli jest ona równa <tt>true</tt>, to wykonujemy <tt>I1</tt>, a w przeciwnym razie <tt>I2</tt>. Gdy nie chcemy, aby cokolwiek wykonywało się '''??''' w przeciwnym razie, wówczas nie piszemy <tt>„else I2”</tt> i wtedy w przypadku, gdy wartość warunku jest <tt>false</tt>, 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ć.
+
Wykonanie instrukcji warunkowej odbywa się również na dwa takty: najpierw obliczana jest wartość warunku <tt>B</tt> i jeśli jest ona równa <tt>true</tt>, to wykonujemy <tt>I1</tt>, a jeżeli nie, wykonujemy <tt>I2</tt>. Gdy nie chcemy, aby cokolwiek wykonywało się w tym drugim przypadku, wówczas nie piszemy <tt>„else I2”</tt> i wtedy w przypadku, gdy wartość warunku jest <tt>false</tt>, 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. [[media:WDP-warunek-else1.swf|Przykład w powiększeniu.]]
 
Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji warunkowej. [[media:WDP-warunek-else1.swf|Przykład w powiększeniu.]]
Linia 48: Linia 48:
 
'''Instrukcja pętli''' jest postaci
 
'''Instrukcja pętli''' jest postaci
 
<tt>'''while''' B '''do''' I</tt>
 
<tt>'''while''' B '''do''' I</tt>
gdzie <tt>B</tt> jest warunkiem logicznym, a <tt>I</tt> instrukcją, którą pętla ma powtarzać, aż do spełnienia warunku  <tt>B</tt>. Wykonanie pętli zaczyna się od obliczenia wartości warunku. Jeśli wartość ta wynosi <tt>false</tt>, to pętla nie robi niczego i kończy swoje działanie, ale jeśli wynosi true, to pętla wykonuje instrukcję  <tt>I</tt>, a następnie wraca do sprawdzenia warunku  <tt>B</tt>. Wykonuje tę sekwencję tak długo, aż warunek <tt>B</tt> przestanie być spełniony. Może się zdarzyć, że warunek  <tt>B</tt> 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 <tt>zapętleniu</tt> programu.  
+
gdzie <tt>B</tt> jest warunkiem logicznym, a <tt>I</tt> instrukcją, którą pętla ma powtarzać, aż do spełnienia warunku  <tt>B</tt>. Wykonanie pętli zaczyna się od obliczenia wartości warunku. Jeśli wartość ta wynosi <tt>false</tt>, to pętla nie robi niczego i kończy swoje działanie, ale jeśli wynosi true, to pętla wykonuje instrukcję  <tt>I</tt>, a następnie wraca do sprawdzenia warunku  <tt>B</tt>. Wykonuje tę sekwencję tak długo, aż warunek <tt>B</tt> przestanie być spełniony. Może się zdarzyć, że warunek  <tt>B</tt> 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 <tt>zapętleniu</tt> programu.  
  
 
Jeśli chcemy zaznaczyć, że zależy nam na wykonaniu ciągu instrukcji, to ciąg ten ujmujemy w nawiasy <tt>begin ... end</tt>.  
 
Jeśli chcemy zaznaczyć, że zależy nam na wykonaniu ciągu instrukcji, to ciąg ten ujmujemy w nawiasy <tt>begin ... end</tt>.  
  
Na razie będziemy używali jedynie zmiennych o wartościach całkowitoliczbowych, a w dziedzinie algorytmicznej będą się znajdowały operacje <math>+,-,-,*,\div,\mod</math> (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 <math><,<=,>,>=,=</math> oraz <math><></math>, 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</tt> z umową, że <tt>not</tt> wiąże najsilniej, <tt>and</tt> słabiej, a <tt>or</tt> 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:
+
Na razie będziemy używali jedynie zmiennych o wartościach całkowitoliczbowych, a w dziedzinie algorytmicznej będą się znajdowały operacje <math>+,-,-,*,\div,\mod</math> (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 <math><,<=,>,>=,=</math> oraz <math><></math>, 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</tt> z umową, że <tt>not</tt> wiąże najsilniej, <tt>and</tt> słabiej, a <tt>or</tt> 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:
  
 
{{kotwica|kod_zrodlowy|}}
 
{{kotwica|kod_zrodlowy|}}
Linia 64: Linia 64:
 
==Zmienne indeksowane (tablice)==
 
==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</tt>, 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).  
+
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</tt>, 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</tt>. Jeśli <tt>A</tt> jest tablicą, to <tt>A[i]</tt> 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.  
 
Zmienne indeksowane nazywają się <tt>tablicami</tt>. Jeśli <tt>A</tt> jest tablicą, to <tt>A[i]</tt> 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.  

Wersja z 19:57, 15 lis 2006

<<< 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. <flash>file=przypisanie1.swf|width=550|height=300|salign=left</flash>

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. <flash>file=WDP-warunek-else1.swf|width=550|height=300|salign=left</flash>

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 Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. TeX parse error: Extra close brace or missing open brace”): {\displaystyle +,-,-,*,\div ,\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. <flash>file=WDP-petla1.swf|width=550|height=300|salign=left</flash>

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 . 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 , a kończąc na , wykonamy instrukcję I. Zakresy pętli for mogą być dowolnymi wyrażeniami dającymi wartości całkowite.