Algorytmy - od projektu do zapisu w języku
programowania
Andrzej Sendlewski
14 paz
dziernika 2009 roku
Algorytm
Zacznijmy od przypomnienia określenia pojęcia algorytmu.
ALGORYTM to skończony ciąg dobrze określonych i jednoznacz-
nych instrukcji (rozkazów) prowadzących od DANYCH do WY-
NIKÓW, z których każda musi być wykonywana mechanicznie w
skończonym czasie.
Algorytm rozwiązujący dany problem musi być ostatecznie zapisany przy-
najmniej w języku programowania. Jednakże w fazie projektowania posługu-
jemy się zarówno językiem naturalnym (niestety mało precyzyjnym) i spe-
cjalnie do tego celu wymyślonym językiem  obrazkowym , zwanym językiem
schematów blokowych. Schemat blokowy to graf zorientowany o różnych
rodzajach wierzchołków, z wyróżnionymi: wierzchołkiem początkowym i koń-
cowym. Każda ścieżka prowadząca od wierzchołka początkowego do wierz-
chołka końcowego jest możliwym ciągiem instrukcji, który zostanie wykonany
w trakcie działania algorytmu na konkretnych danych wejściowych. Nie bę-
dziemy tutaj formalnie opisywać języka schematów blokowych, a wyjaśnimy
wszystko na przykładach. Zacznijmy od banalnego zadania.
Schematy blokowe do wszystkich przykładów narysuj samodzielnie
(patrz wykład).
1
1 Przykład
Zaprojektować algorytm obliczający dla danej liczby naturalnej n sumę s =
1 + 2 + 3 + . . . + n.
Rozwiązanie jest bardzo proste. Każdy matematyk umie zsumować te liczby
zgodnie ze wzorem:
1 + n
1 + 2 + 3 + . . . + n = · n .
2
1 + n
Przeto wystarczy nadać zmiennej s wartość · n tj., wykonać jednÄ…
2
instrukcję przypisania. Oto cały algorytm w języku PASCAL
begin
s:=((1+n)*n) div 2;
end;
Nie w każdej sytuacji będziemy w stanie podać wzór (albo go nie znamy, albo
taki wzór nie istnieje), a zadanie trzeba rozwiązać. Zauważmy, że w naszym
przypadku wystarczy wykonać n kroków, w k-tym kroku dodając do sumy po
k-1 krokach liczbę k. Wymaga to n instrukcji przypisania, co niestety zależy
od danej n. Języki programowania dopuszczają konstrukcję umożliwiająca
zapis czynności trwających dowolnie długo za pomocą skończonego zapisu.
Jest to struktura programistyczna tzw. pętli. (narysuj samodzielnie schemat
blokowy z wykładu).
begin
s:=0; k:=1;
while k<=n do
begin
s:=s+k; k:=k+1;
end;
end;
Zobacz inne rozwiązania z użyciem pętli repeat oraz for w programie Sche-
maty Blokowe.
2
2 Przykład
Zaprojektować algorytm obliczający dla danych liczb naturalnych x i y iloraz
q i resztÄ™ r z dzielenia x przez y.
Oto rozwiÄ…zanie
begin
q:=0; r:=x;
while r>=y do
begin
q:=q+1; r:=r-y;
end;
end;
Algorytm ten kończy się, gdyż każde wykonanie instrukcji w pętli pomniejsza
wartość r o y, co gwarantuje, że po skończonej ilości takich instrukcji wartość
zmiennej r będzie mniejsza od wartości y. Natomiast końcowe wartości q i r
są poszukiwanym odpowiednio ilorazem i resztą, gdyż na początku algorytmu
i po każdym wykonaniu instrukcji w pętli wartości zmiennych spełniają rów-
nanie x = q · y + r.
3 Przykład
Zaprojektować algorytm obliczający dla danych liczb naturalnych a i b naj-
większy wspólny podzielnik tych liczb.
Oto trzy różne rozwiązania. Algorytmy te oparte są na klasycznym rozu-
mowaniu Euklidesa znanym z arytmetyki liczb całkowitych. Zmienne x i y
wprowadzamy jedynie po to, aby zachować pierwotne wartości danych a i b.
begin {algorytm Euklidesa z odejmowaniem}
x:=a; y:=b;
while x<>y do
if x>y then x:=x-y else y:=y-x;
end; {NWD(a,b)=x=y}
3
begin {algorytm Euklidesa z dzieleniem z resztÄ…}
x:=a; y:=b;
while (x>0) and (y>0) do
if x>y then x:=x mod y else y:=y mod x;
end; {NWD(a,b)=x+y}
begin {klasyczny algorytm Euklidesa}
x:=a; y:=b;
repeat
r:=x mod y;
x:=y;
y:=r;
until
r=0;
end; {NWD(a,b)=y}
4