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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m (Zastępowanie tekstu - "<flash>file=(.*)\.swf\|width=(.*)\|height=(.*)\|salign=(.*)<\/flash> " na "$2x$3px|thumb|$4")
 
(Nie pokazano 2 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 33: Linia 33:
 
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.  
 
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. [[media:przypisanie1.swf|Przykład w powiększeniu.]]
 
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. [[media:przypisanie1.swf|Przykład w powiększeniu.]]
<flash>file=przypisanie1.swf|width=550|height=300|salign=left</flash>
+
[[File:przypisanie1.svg|550x300px|thumb|left]]
  
 
==Instrukcja warunkowa==
 
==Instrukcja warunkowa==
Linia 43: Linia 43:
  
 
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.]]
<flash>file=WDP-warunek-else1.swf|width=550|height=300|salign=left</flash>
+
[[File:WDP-warunek-else1.svg|550x300px|thumb|left]]==Instrukcja pętli==
 
 
==Instrukcja pętli==
 
 
'''Instrukcja pętli''' jest postaci
 
'''Instrukcja pętli''' jest postaci
 
<tt>'''while''' B '''do''' I</tt>
 
<tt>'''while''' B '''do''' I</tt>
Linia 52: Linia 50:
 
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 +, -, -, *, /, 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 <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 60: Linia 58:
  
 
Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji pętli. [[media:WDP-petla1.swf|Przykład w powiększeniu.]]
 
Przykład ilustrujący kolejność czynności przy wykonaniu instrukcji pętli. [[media:WDP-petla1.swf|Przykład w powiększeniu.]]
<flash>file=WDP-petla1.swf|width=550|height=300|salign=left</flash>
+
[[File:WDP-petla1.svg|550x300px|thumb|left]]==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).  

Aktualna wersja na dzień 12:27, 19 paź 2021

<<< 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.

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.

==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.

==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.