Plan Laboratorium Teoretycznych Podstaw

Informatyki

Aleksander Wojdyga

2011-10-07

1

Laboratorium – instrukcje proste

W schematach zwartych NS wyróżniany 3 podstawowe instrukcji proste:

• instrukcja wejścia (wczytania, input )

• instrukcja wyjścia (wypisania, output )

• instrukcja podstawienia

W treści instrukcji wejścia i wyjścia wpisujemy nazwy zmiennych rozdzielone
przecinkami. Nazwa zmiennej rozpoczyna się od litery i zawiera litery i cyfry.

Składnia instrukcja podstawienia jest następująca:

nazwa zmiennej := wyrazenie arytmetyczne

Wyrażenie arytmetyczne jest zbudowane z nazw zmiennych, liczb, znaków
działań (+−∗/mod div), nawiasów, wywołań funkcji (sin, cos, tg, ctg, sqrt, abs, log, exp)
zgodnie z regułami matematycznymi.

Przykład 1

Schemat pokazany na Rysunku 1 przedstawia użycie podstawowych in-

strukcji. Należy zauważyć, że są dwie możliwości zmiany wartości zmiennej
– podstawiając obliczoną wartość wyrażenia albo wczytując coś z wejścia.

Przykład 2

W schemacie pokazanym na Rysunku 1 wyrażenie nie jest określone da

wszystkich liczb. Przestetuj ten schemat podając ujemne wartości.

1

Rysunek 1: Instrukcje proste

Rysunek 2: Wyrażenie nieobliczalne

Rysunek 3: Dzielenie całkowite i reszta z dzielenia

2

Przykład 3

Algorytm zapisany w schemacie na Rysunku 1 wypisuje wynik dzielenia

całkowitego i resztę dla dwóch liczb podanych przez użytkownika.

Zadanie

Na podstawie przykładu na Rysunku 1 napisz schemat NS, który

dla liczby dwucyfrowej (użytkownik ma podać taką liczbę) wypisze jako dwie
osobne wartości jej cyfry.

3

2

Laboratorium – instrukcja warunkowa

Składnia

Składnia instrukcji warunkowej przedstawiona jest na Rysunku

4.

Rysunek 4: Składnia instrukcji warunkowej

Warunek jest wyrażeniem logicznym zbudowanym z wyrażeń arytmetycz-

nych połączonych operatorami relacyjnymi oraz spójnikami logicznymi. W
programie NSBuilder dostępne są następujące operatory relacyjne z języka
Pascal: <, <=, >=, >, <> (różne), =. Mogą wystąpić dwa spójniki logiczne
dwuargumentowe and oraz or i jeden spójnik jednoargumentowy not. W
celu uniknięcia niejednoznaczności zaleca się używanie nawiasów.

Dwie gałęzi instrukcji warunkowej mogą zawierać dowolne instrukcje. Do-

wolna z gałęzi może być pusta.

Semantyka

Wykonywanie instrukcji rozpoczyna się od obliczenia warto-

ści warunku. Może to być dokładnie jedna z wartości logicznych: prawda
albo fałsz. W przypadku gdy wartością wyrażenia jest prawda wykonywa-
ne są kolejno instrukcje z gałęzi oznaczonej etykietą TAK, a druga gałąź jest
pomijana. Gałąź pod etykietą NIE jest wykonywana, gdy warunek jest fał-
szywy. Warto zauważyć, że na początku wykonywania tej gałęzi prawdziwe
jest zaprzeczenie warunku.

Przykład 1

Schemat zwarty przedstawiony na Rysunku 5 wypisuje war-

tość bezwzględną liczby podanej przez użytkownika. Jest to równoważne wy-

wołaniu wbudowanej funkcji abs.

Przykład 2

Schemat podający znak liczby, czyli wartość 1, 0, −1 w zależ-

ności czy liczba jest dodatnia, zero lub ujemna, widoczny jest na Rysunku
6. Należy zauważyć, że wartość zmiennej s jest ustawiona we wszystkich
gałęziach selekcji.

4

Rysunek 5: Wartość bezwzględna wczytanej liczby

Rysunek 6: Znak wczytanej liczby

Przykład 3

Na Rysunku 7 przedstawiono możliwość zbadania czy z trzech

liczb można zbudować trójkąt prostokątny. Schemat sprawdza również czy da

się zbudować jakikolwiek trójkąt z podanych liczb.

Rysunek 7: Sprawdzanie czy trójkąt jest prostokątny

5

Przykład 4

Schemat zwarty na Rysunku 8 wyznacza największą liczbę

spośród 3 podanych przez użytkownika. Jest to jedna z możliwości rozwią-
zania tego zadania; aby uniknąć wymiany wartościami zmiennych można

zagnieździć selekcje.

Rysunek 8: Wyznaczanie największej z 3 liczb

Zadanie

Na podstawie przykładu z Rysunku 8 napisz schemat zwarty, któ-

ry wypisze najmniejszą z trzech liczb podanych przez użytkownika.

6

3

Laboratorium – instrukcja iteracji

Składnia instrukcji iteracji w schematach zwartych jest przedstawiona na Ry-
sunku 9. Warunek zbudowany jest tak, jak w instrukcji warunkowej. Refren
składa się z dowolnych instrukcji.

Rysunek 9: Składnia instrukcji iteracji

Przed wykonaniem instrukcji iteracji należy wykonać czynności przygo-

towawcze (protokół wstępny). Mają one na celu przygotowanie poprawnych
wartości zmiennych do pierwszego obliczenia warunku iteracji – niekoniecz-
nie wartością warunku musi być prawda.
Jeśli warunek jest prawdziwy, następują kolejne wykonania instrukcji refrenu.
Po wykonaniu ostatniej instrukcji obliczany jest ponownie warunek iteracji.
Jeśli warunek jest fałszywy, pomijane są instrukcje refrenu i wykonywana jest
kolejna instrukcji po iteracji.

Na początku wykonywania refrenu prawdziwy jest warunek W and N . Po

wykonaniu refrenu prawdziwy jest warunek N . Nazywany jest on niezmien-
nikiem iteracji.

Należy tak napisać instrukcje refrenu, aby warunek nie był zawsze praw-

dziwy. Jeśli autor schematu o tym zapomni, instrukcja będzie pętlą nieskoń-
czoną.

7

Rysunek 10: Schemat wypisujący N pierwszych kwadratów

Rysunek 11: Schemat wypisujący kwadraty z przedziału [1,N]

Rysunek 12: Schemat wypisujący sumę liczb dodatnich

8

Rysunek 13: Schemat sprawdzający czy dana suma zostanie przekroczona
przez dodatnie wyrazy ciągu

4

Laboratorium – złożone instrukcje iteracji

4.1

Złożone warunki iteracji

Jeśli warunek iteracji ma postać koniunkcji α ∧ β, to jego zaprzeczeniem jest
¬α ∪ ¬β. To zdanie logiczne jest prawdziwe po zakończeniu wykonywania
iteracji. Sprawdzając po iteracji jeden z warunków α lub β można stwierdzić
z jakiego powodu zakończyła się iteracja.

Schemat na Rysunku 13 sprawdza czy dodatnie wyrazy ciągu w sumie

przekraczają pewną ustaloną liczbę. Użytkownik podaje najpierw liczbę, któ-
rą mają przekroczyć zsumowane wyrazy ciągu, następnie długość ciągu i jego
kolejne wyrazy.

Jeśli w pewnym momencie suma zostanie przekroczona, pętla kończy swo-

je działanie z powodu fałszywości drugiego warunku. Sprawdzane jest to w

instrukcji warunkowej.

4.2

Iteracja wewnątrz iteracji

Jeśli rozwiązanie zadania wymaga osadzenia instrukcji iteracji w innej in-
strukcji iteracji należy użyć dwóch różnych liczników iteracji. Licznik iteracji

9

wewnętrznej powinien być inicjowany z każdym razem na początku refrenu
iteracji zewnętrznej.

Zadanie

Napisz schemat zwarty, który zliczy ile punktów o współrzędnych

całkowitych nieujemnych znadujących się w kwadracie o boku a, którego
lewy, dolny wierzchołek leży w początku układu współrzędnych leży jedno-
cześnie w kole o promieniu a, którego środek jest także w środku układu

współrzędnych.

Rysunek 14: Schemat zliczający punkty należące do koła i prostokąta

Rozwiązanie

Rozwiązanie znajduje się na Rysunku 14. Zewnętrzna itera-

cja przechodzi po wierszach, wewnętrzna po kolumnach w danym wierszu. To
rozwiązanie nie jest optymalne – wewnętrzna iteracja za każdym razem prze-
chodzi przez cały wiersz. Może ona skończyć się wcześniej – po napotkaniu
pierwszego punktu, który jest poza kołem.

Do zrobienia

Zmodyfikuj przykładowe rozwiązanie, aby było ono opty-

malne.

Zadanie

Napisz schemat zwarty, który sprawdzi czy w macierzy dwuwy-

miarowej k × k znajduje się choć jeden element równy zero.

10

Rysunek 15: Schemat sprawdzający niezerowość elementów macierzy

Rozwiązanie

Na Rysunku 15 przedstawiono przykładowe rozwiązanie po-

wyższego zadania. Zawiera ono metodę wyjścia z obu iteracji – wewnętrznej
i zewnętrznej. W tym celu używana jest zmienna o wartości binarnej (0/1),
od której zależy wykonywanie refrenów obu iteracji.

4.3

Liczby pierwsze

Problem sprawdzenia, czy liczba N jest pierwsza, można rozwiązać szukając
dzielnika tej liczby w przedziale [2, b

√

N c], ponieważ jeśli liczba jest złożo-

na to posiada dzielnik niewiększy od pierwistka z tej liczby. Jeśli liczba jest
parzysta, to na pewno nie jest pierwsza, jeśli jest nieparzysta to należy szu-
kać dzielnika wśród liczb nieparzystych. Przykładowy schemat sprawdzający

pierwszość liczby przedstawiono na Rysunku 16.

11

Rysunek 16: Schemat sprawdzający czy liczba N jest pierwsza

12

5

Laboratorium – tablice

Zmienne typów tablicowych (w odróżnieniu od typów skalarnych – liczb czy
napisów) zawierają wiele danych tego samego typu. Rozmiar tablicy jest
stały podczas wykonywania schematu (programu) i musi być znany autorowi
schematu.

Jeśli T jest zmienną tablicową o n elementach to poprawnymi numerami

elementów (indeksami) są liczby naturalne od 1 do n. Indeksowanie tablicy
poza tymi granicami powoduje błąd wykonania.

Zadanie

Do tablicy o n elementach wczytaj w odwrotnej kolejności n-

elementowy ciąg {a

i

}

i=1,2,...,n

.

Rozwiązanie

Schemat na Rysunku 17 wczytuje ciąg z wejścia do kolejnych

elementów w tablicy (pierwsza iteracja) a następnie go w tej tablicy odwraca

(druga iteracja).

Rysunek 17: Schemat wczytujący i odwracający ciąg w tablicy

Oczywiście można wczytać ciąg z wejścia od razu na odpowiednie miejsca

– indeksy tablicy a zarazem licznik iteracji zmienia się od n do 1 co jest
przedstawione na schemacie z Rysunku 18.

13

Rysunek 18: Schemat wczytujący ciąg odwrotnie w tablicy

Zadanie

Dana jest tablica P różnych liczb pierwszych, jest w niej zapisa-

nych n liczb. Użytkownik podaje liczbę z. Napisz schemat zwarty NS, który
sprawdzi czy liczba z jest iloczynem pewnych dwóch liczb z tej tablicy.

Rozwiązanie

Przykładowe rozwiązanie jest podane na Rysunku 19. Aby

sprawdzić wszystkie niepowtarzające się pary liczb, wewnętrzna iteracja star-

tuje od następnego punktu (j := i + 1).

Rysunek 19: Schemat sprawdzający czy liczba jest iloczynem liczb pierwszych
z tablicy

14

Do zrobienia

Napisz schemat zwarty, który sprawdzi liczby podane przez

użytkownika i zapisze w tablicy P te z nich, które są liczbami pierwszymi.
Użytkownik podaje k liczb i taka jest też pojemność tablicy P.

15

6

Laboratorium – procedury i funkcje

W programowaniu strukturalnym wyróżniamy dwa typy podprogramów: pro-
cedury i funkcje. Podprogramy posiadają argumenty formalne, są one umiesz-
czane w nawiasach; w treści procedury czy funkcji można z nich korzystać
jak ze zmiennych.

Rozróżniamy dwa tryby przekazywania argumentów: przez wartość i przez

zmienną (przez referencję). Modyfikacja argumentu przekazanego przez zmien-
ną będzie widoczna na zewnątrz procedury lub funkcji, w instrukcji, która
je wywołała. W NSBuilderze należy taki parametr poprzedzić słowem var.
Argument przekazany przez zmienną ma swoją wartość początkową (przeka-
zaną jako argument aktualny) i wszelkie operacje na nim będą miały efekt
tylko w treści tego podprogramu.

Rysunek 20: Przykład instrukcji ustawiającej wartość funkcji

Zwracanie wartości z podprogramu zależy od jego typu. Nieformalnie mó-

wi się, że funkcja posiada wartość. W treści funkcji musi znaleźć się specjalna
instrukcja, powodująca ustalenie wartości tej funkcji. Na Rysunku 21 przed-
stawiono postać tej instrukcji w schematach zwartych. W treści instrukcji
należy umieścić wyrażenie, którego wartość ma być wartością funkcji.
Zwracanie wartości z procedury można zrealizować tylko poprzez argument
przekazany przez zmienną.

Rysunek 21: Przykład instrukcji wywołującej procedurę

Wywołanie procedury realizuje się specjalną instrukcją, w jej treści umiesz-

cza się nazwę procedury wraz z argumentami aktualnymi, co pokazano na
Rysunku ??. Wywołanie funkcji należy umieścić w wyrażeniu.

Przykład

Zadanie wyznaczenia najmniejszej spośród 4 liczb zostało roz-

wiązane za pomocą procedury WyznaczMin4(a,b,c,d,var min), która wy-
konuje całe zadanie oraz za pomocą funkcji min2(x,y), której wartością jest
mniejsza z liczb podanych jako argumenty. Schemat procedury przedstawio-
no na Rysunku ??, schemat funkcji na Rysunku ?? a schemat programu na
Rysunku 24.

16

Rysunek 22: Procedura wyznacza najmniejszą liczbę spośród argumentów i
zapisuje w argumencie min

Rysunek 23: Funkcja, której wartością jest mniejsza z liczb podanych jako
argumenty

Rysunek 24: Schemat wyznaczający najmniejszą z 4 liczb

Zadanie

Korzystając z poprzedniego przykładu napisz schemat algorytmu,

który skorzysta z wielokrotnego wywołania funkcji min2 w celu rozwiązania
poprzedniego zadania.

17

7

Laboratorium – tablice wielowymiarowe

18