Algorytmy - od projektu do zapisu w języku

programowania

Andrzej Sendlewski

14 paź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 + 2 + 3 + . . . + n =

1 + n

2

· n .

Przeto wystarczy nadać zmiennej s wartość

1 + n

2

· n

tj., wykonać jedną

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