instrukcja_pascala.pdf

Algorytmika

oraz programowanie w Języku Pascal

Algorytmika

Definicja 1.

Algorytm ã jest to pewien ciąg czynności, który prowadzi do rozwiązania danego problemu.

Definicja 2.

Algorytm ã to jednoznaczny przepis, opisujący krok po kroku sposób postępowania w celu rozwiązania pewnego

problemu lub sposobu osiągnięcia jakiegoś celu.

Ilość kroków algorytmu zależy od tego, jak złożony jest problem, którego on dotyczy. Zawsze jednak liczba tych

kroków będzie liczbą skończoną .

Algorytmy można przedstawiać m.in. następującymi sposobami:

słowny opis

schemat blokowy

lista kroków

drzewo algorytmu

drzewo wyrażeń

w pseudojęzyk

w język programowania.

Cechy charakterystyczne poprawnego algorytmu:

1. Poprawność - dla każdego przypisanego zestawu danych, po wykonaniu skończonej liczby czynności, algorytm

prowadzi do poprawnych wyników.

2. Jednoznaczność - w każdym przypadku zastosowania algorytmu dla tych samych danych otrzymamy ten sam

wynik.

3. Szczegółowość - wykonawca algorytmu musi rozumieć opisane czynności i potrafić je wykonywać.

4. Uniwersalność - algorytm ma służyć rozwiązywaniu pewnej grupy zadań, a nie tylko jednego zadania.

Przykładowo algorytm na rozwiązywanie równań w postaci ax + b=0 ma je rozwiązać dla dowolnych

współczynników a i b, a nie tylko dla jednego konkretnego zadania, np. 2x + 6 = 0

Etapy konstruowania algorytmu(programu):

1. Sformułowanie zadania.

2. Określenie danych wejściowych.

3. Określenie wyniku oraz sposobu jego prezentacji.

4. Ustalenie metody wykonania zadania.

5. Przy użyciu wybranej metody następuje zapisanie algorytmu.

6. Dokonujemy analizy poprawności rozwiązania.

7. Testowanie rozwiązania dla różnych danych.

8. Ocena skuteczności tegoż algorytmu.

Różne sposoby przedstawiania algorytmów

a)opis słowny

Jest na ogół pierwszym, mało ścisłym opisem sposobem rozwiązania problemu. Rozpoczyna się często dyskusją, w

jaki sposób można rozwiązać postawione zadanie. Dyskusja służy do rozważań nad sposobem i technikami

przydatnymi w rozwiązania problemu.

np. Opis słowny do algorytmu opisującego funkcję modułu (wartość bezwzględną).

Dla wartości dodatnich argumentu x funkcja przyjmuje wartość x, dla wartości ujemnych argumentu x funkcja

przyjmuje wartość –x.

b)schemat blokowy

c)lista kroków

Poszczególne kroki zawierają opis operacji, które mają być wykonane prze algorytm. Mogą w nich również wystąpić

polecenia związane ze zmianą kolejności wykonywanych kroków. Kolejność kroków jest wykonywana w kolejności

ich opisu z wyjątkiem sytuacji gdy jedno z poleceń w kroku jest przejściem do kroku o podanym numerze. Budowa

opisu algorytmu w postaci listy kroków jest następujący:

tytuł algorytmu

specyfikacja problemu

lista kroków

komentarze ujęte w nawiasy klamrowe {komentarz}

uwaga : Krok 0 może być opuszczony

np. Lista kroków dla funkcji SGN(x) czytaj signum.

Algorytm obliczania wartości funkcji SGN(x)

Dane: Dowolna liczba rzeczywista x.

Wynik: Wartość funkcji

Krok 0. Wczytaj wartość danej x

Krok 1. Jeśli x>0, to f(x)=1. Zakończ algorytm.

Krok 2. {W tym przypadku x<= 0.} Jeśli x=0, to f(x)=0 . Zakończ algorytm.

Krok 3. {W tym przypadku x< 0.} Mamy f(x)=–1 . Zakończ algorytm.

d)drzewo algorytmu

Nazywany jest również drzewem obliczeń. Każde dwie drogi obliczeń

mogą mieć tylko początkowe fragmenty wspólne, ale po rozejściu już

dla





się

SGN

(

)

dla

nie spotkają.



dla

np. Drzewo algorytmu dla funkcji SGN(x).

Korzeń

Wierzchołki

pośrednie

x>0

Tak

Nie

f(x)=1

x=0

Tak

Nie

Wierzchołki

końcowe

f(x)=0

f(x)=–1

e)drzewo wyrażeń

Stosowane do obliczeń wyrażeń arytmetycznych.

np. Wyrażenie (a+sin(x))*b/(a–b)

–

sin

f)program w języku programowania np. Pascal

g)pseudojęzyk

PROGRAM Wycieczka;

ZMIENNE punkty:naturalne;

koszty, dofinansowanie:rzeczywiste;

ZACZNIJ;

WPROWADŹ(PUNKTY,KOSZTY);

JEŚLI punkty >=100 i punkty <= TO dofinansowanie :=1/3*koszty+0.2*koszty

W PRZECIWNYM WYPADKU dofinansowanie:=0.2*koszty;

WYPROWADŹ('Dofinansowanie wynosi:'dofinansowanie);

ZAKOŃCZ.

Specyfikacja problemu

Jest to dokładny opis problemu, który chcemy rozwiązać. Specyfikacja składa się z:

danych oraz warunki jakie muszą spełniać,

wynik oraz warunki jakie muszą spełniać (czyli związek pomiędzy danymi a wynikami).

Symbole stosowane w schematach blokowych.

W każdym algorytmie musi się znaleźć dokładnie

jedna taka figura z napisem "Start" oznaczająca

początek algorytmu Blok symbolizujący początek

algorytmu ma dokładnie jedną strzałkę

wychodzącą

Start

W każdym algorytmie musi się znaleźć dokładnie

jedna figura z napisem "Stop" oznaczająca koniec

algorytmu. Najczęściej popełnianym błędem w

schematach blokowych jest umieszczanie kilku

stanów końcowych, zależnych od sposobu

zakończenia programu. Blok symbolizujący koniec

ma co najmniej jedną strzałkę wchodzącą.

Stop

Równoległobok jest stosowany do odczytu lub

zapisu danych. W jego obrębie należy umieścić

stosowną instrukcję np. Read(x) lub Write(x)

(można też stosować opis słowny np. "Drukuj x na

ekran"). Figura ta ma dokładnie jedną strzałkę

wchodzącą i jedną wychodzącą. Jest to blok

wyjścia/wejścia wy/we I/O.

Romb symbolizuje blok decyzyjny. Umieszcza się

w nim jakiś warunek (np. "x>2"). Z dwóch

wybranych wierzchołków rombu wyprowadzamy

dwie możliwe drogi: gdy warunek jest spełniony

(strzałkę wychodzącą z tego wierzchołka należy

opatrzyć etykietą "Tak") oraz gdy warunek nie jest

spełniony „Nie”. Każdy romb ma dokładnie jedną

strzałkę wchodzącą oraz dokładnie dwie strzałki

wychodzące.

Jest to figura oznaczająca proces. W jej obrębie

umieszczamy wszelkie obliczenia lub

podstawienia . Proces ma dokładnie jedną strzałkę

wchodzącą i dokładnie jedną strzałkę wychodzącą.

Ta figura symbolizuje proces, który został już kiedyś

zdefiniowany. Można ją porównać do procedury, którą

definiuje się raz w programie, by następnie móc ją

wielokrotnie wywoływać. Warunkiem użycia jest więc

wcześniejsze zdefiniowanie procesu. Podobnie jak w

przypadku zwykłego procesu i tu mamy jedno wejście i

jedno wyjście.

Koło symbolizuje tzw. łącznik stronicowy. Może się

zdarzyć, że chcemy "przeskoczyć" z jednego miejsca na

kartce na inne. Możemy w takim wypadku posłużyć się

łącznikiem. Umieszczamy w jednym miejscu łącznik z

określonym symbolem w środku (np. cyfrą, literą) i

doprowadzamy do nie go strzałkę. Następnie w innym

miejscu kartki umieszczamy drugi łącznik z takim

samym symbolem w środku i wyprowadzamy z niego

strzałkę. Łączniki występują więc w parach , jeden ma

tylko wejście a drugi wyjście.

Ten symbol to łącznik międzystronicowy. Działa

analogicznie jak pierwszy, lecz nie w obrębie strony.

Przydatne w złożonych algorytmach, które nie mieszczą

się na jednej kartce.

łącznik międzystronicowy

Poszczególne elementy schematu łączy się za

pomocą strzałek. W większości przypadków blok

ma jedną strzałkę wchodzącą i jedną wychodzącą

element łączący

www.rafalbaran.net/mb

Strona z magicznymi blokowymi.

Reguły rysowania schematów blokowych

I. Po zbudowaniu schematu blokowego nie powinno być takich strzałek, które z nikąd nie wychodzą, lub do nikąd

nie dochodzą.

II. Każdy schemat blokowy musi mieć tylko jeden element startowy oraz co najmniej jeden element końca

algorytmu.

III. Element łączący(strzałki łączące) powinien być rysowany w poziomie i pionie, załamania pod kątem prostym.

Podział algorytmów.

Definicja algorytmu liniowego

Algorytmem liniowym nazywamy taki algorytm, który ma postać listy kroków wykonywanych zgodnie z ich

kolejnością.

Algorytmy liniowe są zapisem obliczeń, które mają postać ciągu operacji rachunkowych wykonywanych bez

sprawdzania jakichkolwiek warunków.

Algorytm z warunkami (rozgałęzieniami)

Ten typ algorytmu musi mieć bloki decyzyjne czyli bloki sprawdzania warunków.

Algorytm numeryczne

Algorytmy, które wykonują działania matematyczne na danych liczbowych, nazywamy algorytmami numerycznymi.

Algorytm typu dziel i zwyciężaj

Dzielimy problem na kilka mniejszych, a te znowu dzielimy, aż ich rozwiązania staną się oczywiste,

Algorytmy iteracyjne

Iteracja jest to zapętlenie algorytmu, czyli wykonywania danych działań, dopóki warunek iteracji nie zostanie

spełniony. Jest ona podstawą wszystkich choć troszkę bardziej złożonych algorytmów. Zazwyczaj ma ona składnię

wykonuj "jakaś czynność" dopóki "jakieś wyrażenie logiczne".

Algorytmy rekurencyjne

Rekurencje wykorzystuje się do rozwiązywania problemów gdzie powtarza się czynność aby do niego dojść. Swoim

działaniem przypomina iteracje. Jednak w tym przypadku funkcja sama siebie wywołuje, dopóki nie otrzyma

rozwiązania , natomiast tam mieliśmy powtórzenie pewnej czynności określoną ilość razy.

Złożoność algorytmu- ilość zasobów potrzebnych do poprawnego działania danego algorytmu

Złożoności obliczeniowa- Algorytm wykonujący najmniejszą ilość operacji podstawowych w celu rozwiązania

problemu.

Złożoność czasowa- Określa ilość operacji podstawowych potrzebnych do wykonania algorytmu o danej wielkości

wejściowej.

Złożoność pamięciowa- Określa ilość przestrzeni pamięci wirtualnej potrzebnej do wykonania algorytmu z

określonym zestawem danych wejściowych.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: