Algorytmy i schematy blokowe
Algorytm - dokładny przepis podający sposób rozwiązania określonego zadania w skończonej liczbie
kroków; zbiór poleceń odnoszących się do pewnych obiektów, ze wskazaniem porządku, w jakim mają
być realizowane.
Słowo algorytm pochodzi od łacińskiej formy (Algorismus, Algorithmus) nazwiska arabskiego
matematyka Muhammada ibn Musa al-Khwarazmi’ego (ok. 790 - ok. 840 r. ne.)
Algorytmy obliczeniowe powstawały już w czasach starożytnych, są to m.in.:
•
algorytm Euklidesa,
•
algorytm Eratostenesa (tzw. sito Eratostenesa).
Algorytmy i komputery
•
każdy komputer wykonuje jakiś program
•
każdy program jest zapisem jakiegoś algorytmu
Algorytm opisuje logiczny ciąg operacji, które ma wykonać program
Jeśli istnieje algorytm rozwiązujący jakiś problem, to można ten problem rozwiązać przy użyciu
komputera. Natomiast jeśli algorytm taki nie istnieje (lub nie jest jeszcze znany) to problemu tego nie
da się rozwiązać za pomocą komputera.
Algorytmy można przedstawiać w różny sposób. Jednym z bardziej popularnych jest schemat
blokowy, inne to opis w postaci listy kroków, czy też opis przy użyciu pewnego umownego
pseudojęzyka.
Algorytm zapisany za pomocą języka programowania jest programem - jest to najbardziej ścisły (a
przy tym zrozumiały dla komputera) opis algorytmu.
Schemat blokowy (sieć działań) jest graficznym przedstawieniem algorytmu. Składa się z pewnej
liczby figur geometrycznych (prostokątów, rombów itp.) nazywanych blokami oraz łączących ich linii
z zaznaczonym kierunkiem. Pokazuje wszystkie operacje, które mają być wykonane i określa kolejność
ich wykonania
Blok - graficzna reprezentacja pewnej czynności (operacji)
Wewnątrz większości bloków występują nazwy zmiennych.
Zmienna to miejsce w pamięci w którym przechowywana jest jakaś wartość. Zmienna ma nazwę a
także skojarzony jest z nią typ wartości, jaką może przechowywać.
Rozróżnia się:
•
zmienne proste (pojedyncza komórka przechowująca jedną wartość)
•
zmienne złożone - np. tablice (zbiór identycznych komórek przechowujących wartość tego
samego typu, mają one wspólną nazwę i są rozróżniane za pomocą numeru nazywanego
indeksem)
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 1-
Symbole schematów blokowych
Blok operacyjny (obliczenia). Ma kształt prostokąta. Wewnątrz bloku umieszcza się zapis jednej lub
kilku operacji, w wyniku której ulega zmianie wartość, postać lub miejsce przechowywania danych.
Bloki wejścia/wyjścia (wprowadzanie i wyprowadzanie danych). Mają kształt równoległoboku.
Wewnątrz bloku umieszcza się nazwy zmiennych, którym mają być nadane wartości wprowadzone z
urządzenia wejścia lub nazwy zmiennych, których wartości mają być wypisane na urządzenie wyjścia
Blok warunkowy (decyzyjny). Wewnątrz bloku umieszcza się zapis operacji pozwalającej wybrać
jedną z alternatywnych dróg dalszego działania.
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 2-
Bloki graniczne (początek i koniec algorytmu). Każdy schemat musi zwierać jeden (i tylko jeden) blok
początku oraz co najmniej jeden blok końca (może ich być więcej, jeśli zwiększa to czytelność
schematu).
Blok procesu.
Proces zdefiniowany
poza algorytmem
Bloki łącznikowe
(międzystronicowe i stronicowe )
Komentarz
łączą fragmenty schematu znajdujące się
na tej samej (łącznik stronicowy) lub
różnych (łącznik międzystronicowy)
stronach.
miejsce na napisanie
komentarza
Specyfikacja – dokładny opis zadania, które ma być wykonane lub problemu, który ma być
rozwiązany. Musi zawierać opis trzech elementów:
•
pożądanych wyników działania algorytmu,
•
danych wejściowych,
•
sposobu otrzymania wyników na podstawie danych wejściowych.
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 3-
Podstawowe rodzaje algorytmów
Algorytm liniowy (inaczej prosty lub sekwencyjny)
Jest to najprostsza forma realizacji procesu obliczeniowego. Ma ustaloną z góry kolejność realizacji
poszczególnych etapów, a wszystkie czynności wykonywane są jeden raz (żadna z nich nie może być
pominięta ani powtórzona). Nie ma w nim bloków decyzyjnych.
Przykład: obliczanie pola i obwodu koła
Dane: promień r
Wynik: pole p i obwód ob
Wzory do obliczeń
2
r
p
π
=
;
r
2
ob
π
=
Algorytm rozgałęziony (inaczej decyzyjny albo rozwidlony)
Rozwidla się na kilka gałęzi. Musi zawierać co najmniej jeden blok decyzyjny, pozwalający wybrać
jedną z możliwych dróg realizacji danego zadania. W zależności od danych, pewne czynności są
wykonane, inne nie.
Przykład: rozwiązywanie równania kwadratowego ax
2
+ bx + c = 0
Dane: współczynniki a, b, c
Wynik: pierwiastki x
1
i x
2
albo pierwiastek
x albo brak pierwiastków rzeczywistych.
Metoda rozwiązania: algorytm „delty” znany ze szkoły średniej.
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 4-
Algorytm cykliczny (inaczej iteracyjny albo z powtórzeniami)
Występują wielokrotne powtórzenia niektórych operacji różniących się jedynie wartością danych, na
których działają.
Przykład: sumowanie ciągu n liczb a
1
, a
2
, a
3
...... a
n
Dane: n oraz a
1
, a
2
, a
3
...... a
n
Wynik: suma a
i
(
i =1 ... n)
∑
=
=
n
i
i
a
suma
1
Metoda rozwiązania: tak jak przy użyciu
kalkulatora z funkcją „dodaj do pamięci” (M+)
M
←
0
M
←
M + a
i
←
tę czynność powtarzamy n razy
Pętla obejmuje te bloki, które są powtarzane.
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 5-
Graficzny opis algorytmu można wykorzystać do symulacji jego działania (lub badania własności) bez
potrzeby pisania programu komputerowego. Na rysunku – symulacja działania algorytmu cyklicznego
dla przykładowych danych.
Przykład algorytmu gry w kółko i krzyżyk na planszy 3x3.
Gra człowiek (gracz) z komputerem (komp), przy czym grę rozpoczyna komputer i nie powinien
przegrać!
(Rysunek oparty na schemacie podanym w skrypcie: Ambroziak K., Kott R.K.: Programowanie
maszyn cyfrowych. Materiały do ćwiczeń. Wyd. Politechniki Warszawskiej, Warszawa, 1984).
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 6-
Pierwszy program do gry w „kółko i krzyżyk” opracował
A.S. Douglas w 1952 dla potrzeb swojej rozprawy
doktorskiej poświęconej możliwościom interakcji między
człowiekiem i maszyną, którą postanowił zilustrować
komputerową symulacją wspomnianej gry (na komputerze
EDSAC – pierwszym oddanym do użytku komputerze
zbudowanym zgodnie z koncepcją von Neumanna, tzn. z
programem umieszczonym w pamięci.).
Była to pierwsza gra komputerowa i jednocześnie pierwsza
gra działająca w trybie graficznym.
Darmowy symulator EDSAC'a (dla Windows) wraz z pakietem programów (w tym również oryginalną
grą Douglasa) można pobrać ze strony http://www.dcs.warwick.ac.uk/~edsac/
Gra „kółko i krzyżyk” w wersji opracowanej przez J. Walkenbach’a (arkusz Excela wraz z programem
w Visual Basicu dla Aplikacji). Adres pliku w Internecie:
http://j-walkblog.com/blog/docs/jwalk-tick-tac-toe.xls
A. Spyra – Elementy informatyki ... – materiały pomocnicze (sem. 2)
- 7-