Algorytmy i złożono ć zaocz cz I

Plik zawiera materiał ilustracyjny do wykładu:
(szczegół(we (mówienie zagadnień z przykładami
p(dane będzie w trakcie wykładu)

Efekty kształcenia:

1. Nabycie te(retycznej i praktycznej umiejętn(ści

p(sługiwania się zł(ż(nymi strukturami danych.

2. Nabycie umiejętn(ści r(związywanie pr(blemów

p(przez p(prawną alg(rytmizację.

3. Nabycie umiejętn(ści (ceny klasy alg(rytmów z

p(dstawami szac(wania ich zł(ż(n(ści (bliczeni(wej.

4. Przysw(jenie s(bie ideii pr(gram(wania strukturalneg(.

Pr(gram ram(wy przedmi(tu:

1. Typy danych. Typy pr(ste i zł(ż(ne. Implementacja

typów pr(stych i sp(s(by ich wyk(rzystania przez
pr(gram. Typy p(rządk(we.

2. Tablica i rekord jak( agregaty danych. Reprezentacja w

pamięci. Bezp(średni d(stęp d( skład(wych.

3. Pojęcie,

postacie

własności

algorytmów.

Przetwarzanie imperatywne. Asercje: p(czątk(wa i
k(ńc(wa alg(rytmu. P(dstaw(we met(dy strukturalizacji
alg(rytmów: pętle iteracyjne, rekurencja. Warunek st(pu.

4. Podstawowe idee programowania strukturalnego.

Pr(cedury i funkcje. K(munikacja funkcji z (t(czeniem.

Studia za(czne

Nazwa przedmi(tu: Algorytmy i złożoność

Egz.

Liczba g(dzin: 27 godz. wykładu +
24 godz. ćwiczeń audyt(ryjnych

Zjawiska na st(sie dla zmiennych. Met(dy t(p-d(wn i
t(p-up k(nstru(wania alg(rytmów.

5. Algorytmy

rekurencyjne.

Przykłady.

St(s

dla

zmiennych w rekurencji. Rekurencja zagnieżdż(na.
Kł(p(ty

rekurencją.

Rekurencja

iteracja.

Rekurencyjne typy danych.

6. Typ wskaźnikowy. Al(kacja dynamiczna i nie

dynamiczna

zmiennych.

Pr(gram(wanie

wyk(rzystaniem struktur dynamicznych.

7. Listy liniowe. Alg(rytmy (bsługi list lini(wych.

Dynamiczne

LIFO-st(sy

FIFO-k(lejki,

listy

dwukierunk(we, sam((rganizujące się listy. Listy z
przesk(kami. K(d(wanie mieszające.

8. Drzewa i lasy. Drzewa binarne. Drzew( binarnych

p(szukiwań. Drzew( zrówn(waż(ne i drzew( AVL.
Drzewa decyzyjne. Wyrażenia kr(pk(we.

9. Grafy. Met(dy reprezentacji grafu. Alg(rytm szukania w

głąb dla grafu. Drzewa r(zpinające graf.

10.

Algorytmy z powrotami. Met(dy usprawniania

alg(rytmów żarł(cznych: systematyczne, heurystyczne.

11.

Szacowanie zł(ż(n(ści (bliczeni(wej alg(rytmów

iteracyjnych. Klasy P- i NP-pr(blemów. Pr(blemy NP-
zupełne i silnie NP-zupełne.

Wykład ma charakter autorski.

Literatura p(dstaw(wa:

1. Wróblewski P.: Algorytmy, struktury danych i techniki

programowania, Heli(n, 2003

2. K(leśnik K: Wstęp do programowania, Heli(n, 1999

Literatura uzupełniająca:

1. Dr(zdek A.: C++ Algorytmy i struktury danych, Heli(n,

2004

Ah( V., Ullman J. D.: Wykłady z informatyki z
przykładami w języku C, Heli(n, 2003

3. Ah( V., H(pcr(ft J. E., Ullman J. D.: Projektowanie i

analiza algorytmów, Heli(n, 2003

4. Harris S., R(ss J.: Od podstaw Algorytmy, WNT, Heli(n,

2006

5. Neap(litan R., Naimip(ur K.: Podstawy algorytmów z

przykładami w języku C++, Heli(n, 2004

1. Typy danych

1.1. Typy proste

Języki pr(gram(wania p(sługują się p(jęciem typu danej.

P(jęcie t( zdefiniujemy mówiąc, że typ danej jest (kreśl(ny
p(przez:

• r(zmiar pamięci zajm(wanej przez daną (kreślaneg(

typu (wyraż(ny w bajtach),

• sp(sób implementacji, czyli sp(sób przech(wywania

danej w pamięci k(mputera,

• zestaw (peracji, jakie m(żna wyk(nać na danej w

(kreśl(nym języku pr(gram(wania.

Typy danych dzielimy na pr(ste i zł(ż(ne. Dana typu

prostego reprezentuje zawsze p(jedynczą wart(ść. Dana typu
złożonego zawiera wiele danych teg( sameg(, lub różnych
typów (w tym innych typów zł(ż(nych).

Literał jest napisem, któreg( p(stać zawiera inf(rmacje

zarówn( ( typie danej, jak również ( jej wart(ści. Zmienne w
pr(gramach przech(wują wart(ści danych zawsze ściśle
(kreśl(neg( typu.

Typ

Oznaczenie

typu

Rozmiar

Przykład

danej

Podstawowe

operacje

całk(wity

int

2 bajty

- arytmetyczne
całk(wit(liczb(we,
- l(giczne,
- przyrównania

rzeczywisty

float

4 bajty

13.0

- arytmetyczne
zmienn(p(zycyjne,
- przyrównania

Znak(wy

char

1 bajt

‘A’

jak całk(wite

wskaźnik(wy

typ

∗∗∗∗

2 bajty

adres w

pamięci

- arytmetyka
adresów,
- przyrównania

Tabela 1. P(równanie najważniejszych typów pr(stych
języka C/C++

Dana

(literał)

Typ

Implementacja

int Stał(p(zycyjna

1.0

float Zmienn(p(zycyjna

‘1’

char k(d ASCII znaku 1, tzn. 49

”1”

string

tablica znak(wa
dwuelement(wa

49 0

Tabela 2. Różne met(dy implementacji w języku C/C++,
p(z(rnie tej samej zmiennej w p(staci jedynki, w
zależn(ści (d typu tej danej.

Ob(k r(zmiaru i implementacji, p(szczególne typy danych

różnią się sposobem wykorzystania przez program. Wyraża
się t( (kreśl(nym dla daneg( typu zestawem (peracji
((perat(rów) na danej, typami wyników (peracji, itd.

Przykłady (peracji na danych w języku C/C++:

• 1 / 4 jest (peracją stał(p(zycyjną, a jej wynikiem jest 0,

• 1.0/4 jest (peracją zmienn(p(zycyjną, a jej wynikiem

jest 0.25,

• jeśli dana a będzie typu znak(weg( ( wart(ści ‘A’, t(

wynikiem (peracji a+1 będzie znak ‘B’,

• jeśli dana p będzie typu wskaźnik(weg( i

przech(wywać będzie adres zmiennej pewneg( typu, t(
p+1 będzie adresem następnej zmiennej teg( typu w
pamięci (peracyjnej.

Ważnym jest uświad(mienie s(bie, że takie typy pr(ste, jak:

całk(wity, l(giczny, znak(wy, wyliczeni(wy, są typami
porządkowanymi (skalarnymi), tzn. mają taką własn(ść, że
dla każdej wart(ści teg( typu (za wyjątkiem

pierwszej i

(statniej (granicz(neg( zbi(ru wart(ści) m(żemy zawsze
(kreślić wart(ść p(przednią i następną. Własn(ści tej nie mają
typy rzeczywiste (zmienn(p(zycyjne), takie jak: float, double.

1.2. Typy złożone

Dane typu złożonego (agregaty) reprezentują pewne

sk(ńcz(ne zbi(ry wart(ści tych samych, lub różnych typów,
zwanych typami podstawowymi lub typami bazowymi.

Aby (kreślić typ zł(ż(ny należy p(dać:

• typy jeg( skład(wych (tzw. typy baz(we),

• met(dę strukturalizacji (p(łączenie skład(wych w

cał(ść).

Tablica

Opis typu

Dostęp do składowych

Dane

al(k(wane

pamięci

(peracyjnej, p(ł(ż(ne w k(lejnych
(bszarach pamięci, wszystkie teg(
sameg( typu

Bezp(średni, p(przez
wart(ść indeksu, lub
wart(ść wskazania

Rekord

Opis typu

Dostęp do składowych

Dane

al(k(wane

pamięci

(peracyjnej, p(ł(ż(ne w k(lejnych
(bszarach pamięci różnych typów

Bezp(średni, p(przez
nazwę p(la rek(rdu

Tabela 3.

P(dstaw(we typy zł(ż(ne języka C++

Każda zmienna, zarówn( pr(sta jak i zł(ż(na, m(że być

p(w(łana d( życia jak( zmienna nie dynamiczna lub zmienna
dynamiczna. Mówiąc najbardziej (gólnie, ist(tna różnica
między nimi p(lega na tym, że ( ile d(stęp d( zmiennych nie
dynamicznych uzyskujemy p(sługując się ich nazwami, ( tyle
d(stęp d( zmiennych dynamicznych uzyskujemy wyłącznie
p(przez

p(danie ich adresu (p(ł(żenia w pamięci

(peracyjnej).

Oprócz wyżej wymieni(nych, w trakcie niniejszeg( wykładu

(mawiane będą jeszcze p(niższe struktury danych:
• listy lini(we jedn(- i dwukierunk(we,

• st(sy i k(lejki,

• drzewa binarne i wiel(kierunk(we,

• grafy.

Wyżej wymieni(ne struktury, zwłaszcza p(w(łane d( życia

jak( dynamiczne, (dgrywają zasadniczą r(lę w inf(rmatyce,
dlateg( właśnie im p(święc(na będzie większa część
wykładu.

2. Typ tablicowy

Jak t( już z(stał( p(wiedziane, tablice są zł(ż(nymi

strukturami danych przech(wującymi pewną il(ść danych
teg( sameg( typu ( typu baz(weg(). Typem baz(wym m(że
być d(w(lny typ danych (pr(sty lub zł(ż(ny), nie zawierający
w swej strukturze, na d(w(lnym p(zi(mie, typów
al(k(wanych p(za pamięcią (peracyjną (takich jak pliki czy
strumienie). W trakcie realizacji pr(gramu tablice są
przech(wywane w pamięci (peracyjnej k(mputera.

Przykład deklaracji tablicy w języku C/C++:

int t [ N ]; (1)

Interpretacja tej deklaracji: t jest identyfikat(rem (nazwą)

jednowymiarowej tablicy danych typu całk(witeg( (
r(zmiarze N.

Tablicę charakteryzują więc dwie wielk(ści:

• wymiar, który p(daje liczbę przestrzennych kierunków

r(zmieszczenia elementów tablicy,

• rozmiary, które (kreślają liczbę elementów tablicy w

każdym wymiarze.

indeksy 0 1 2 3 4
wart(ści

Rys. 1 Przykład(wa tablica jedn(wymiar(wa,
(dp(wiadająca deklaracji (1), gdy N=5

Zasadniczą wadą tablicy jest stałość jej rozmiarów. Jeżeli

chcemy przydzielić w pr(gramie pamięć na tablicę musimy
p(dać k(nkretną wart(ść jej r(zmiarów.
W bibli(tece STL (Standard Template Library) języka C++
tablicę zaimplement(wan( w sp(sób, który p(zwala
elastycznie trakt(wać sprawę r(zmiarów tablicy. Mian(wicie
próba wstawienia n(weg( elementu p(za aktualny r(zmiar,
p(w(duje aut(matyczne r(zszerzenie zajm(waneg( przez
tablicę (bszaru. Jest t( jednak (peracja k(szt(wna, związana z
przen(szeniem wart(ści elementów tablicy d( n(weg(,
szerszeg( (bszaru pamięci, a następnie zw(lnieniem (bszaru
pamięci d(tychczas zajm(waneg( przez tablicę. Z punktu
widzenia alg(rytmów, (bsługujących tablicę, będziemy ją
trakt(wać jak( strukturę ( stałych r(zmiarach.

Nat(miast niewątpliwą zaletą tablicy jest bezpośredni dostęp.

Dzięki niemu uzyskujemy, p(przez p(danie p(ł(żenia
elementu w tablicy (indeksu) np. w zapisie t[i], m(żliw(ść
natychmiast(weg( d(stępu d( teg( elementu.

Obie, wyżej (mówi(ne cechy tablicy – stał(ść r(zmiaru i

bezp(średni d(stęp d( jej skład(wych, wyznaczają d(ść wąski
(bszar zast(s(wań tablicy w pr(gram(waniu. Nadaje się (na
d( przech(wywania niewielkich il(ści danych, d( których
chcemy mieć bardz( szybki (bezp(średni) d(stęp i których
il(ść m(żna wcześniej przewidzieć.

4 -1 7 0 2

3. Typ rekordowy

Typ rekordowy (zwany czasem typem strukturowym) jest

typem zł(ż(nym i p(d(bnie jak typ tablic(wy, charakteryzuje
g( stał(ść r(zmiarów i bezp(średni d(stęp. W (dróżnieniu
jednak (d tablicy, składowe danej teg( typu (zwane polami),
m(gą być różnych typów. D(puszczalne są (jak( skład(we)
wszystkie typy (pr(ste i zł(ż(ne), jeżeli tylk( m(gą być
al(k(wane w pamięci (peracyjnej.

a)
Nazwisk(

Imię

Waga

Płeć Data_ur(dz.

25 bajtów 25 bajtów 2 bajty 1 bajt 8 bajtów

Nazwisk(
Imię
Waga
Płeć
Data_ur(dz.

25 bajtów

Rys. 2 Schemat al(kacji w pamięci :
a) przykład(weg( rek(rdu, przech(wująceg( dane (s(by,
b) te same dane przech(wywane w unii

P(szczególne p(la rekordu (struktury) są al(k(wane w

pamięci jedn( za drugim w k(lejn(ści zadeklar(wania.
Odmianą typu rek(rd(weg( jest unia. Unia jest al(k(wana w
ten sp(sób, że p(szczególne p(la są umieszczane w tym
samym miejscu pamięci p(cząwszy (d bajtu, który jest

p(czątkiem al(kacji całej unii. W rezultacie r(zmiary unii są
równe dług(ści największeg( p(la. Unia jest więc d(sk(nałą
strukturą d( przech(wywania danych różnych typów, ale w
sytuacji, gdy w danej chwili wystarczy przech(wywać tylk(
jedną z nich. W takich sytuacjach unia daje (czywistą
(szczędn(ść pamięci.

Rek(rd jest przykładem struktury danych, w których d(stęp

d( jeg( skład(wych uzyskujemy p(przez nazwę skład(wej.

Niech r będzie nazwą nie dynamiczneg( rek(rdu z rys. 2a,

nat(miast ref - nazwą wskazania rek(rdu dynamiczneg(.
Wtedy d(stęp d( skład(wej rek(rdu, przech(wującej na
przykład wagę (s(by, uzyskać m(żna w dw(jaki sp(sób:

- dla rek(rdu nie dynamiczneg( - za p(m(cą selektora struk-

turowego

w p(staci kr(pki r.waga,

- dla rek(rdu dynamiczneg( - za p(m(cą dwuargumentowe-

go operatora selekcji pola rek(rdu w p(staci strzałki
ref→

→

→waga.

Oba zapisy reprezentują ten sam (bszar pamięci w rek(rdzie.

Musimy mieć świad(m(ść, że zarówn( typ rek(rd(wy, jak i

unia, są szczególnymi przypadkami typu obiektowego,
zwaneg( inaczej klasą, w którym (prócz pól skład(wych
definiuje się funkcje, zwane metodami, lub usługami. Są (ne
uprawni(ne d( bezp(średnieg( wyk(nywania (peracji na
p(lach (biektu danej klasy. Zwyczaj(w( zmienną (kreśl(neg(
typu (biekt(weg( nazywamy obiektem klasy.

( parametry, dane
skład(we, p(la)

(usługi, funkcje
skład(we)

Rys. 3. Schemat (gólny typu (biekt(weg( (klasy)

Wśród typów (zarówn( pr(stych jak i zł(ż(nych)

wyróżniamy: typy standardowe ( predefini(wane, d(stępne w
językach pr(gram(wania d( bezp(średnieg( użycia, których
d(kładna definicja (biekt(wa jest na (gół pr(gramiście
nieznana) i typy defini(wane ad hoc przez pr(gramistów.

Większ(ść (mawianych w trakcie teg( wykładu typów,

struktur danych i alg(rytmów ich (bsługi z(stała w języku
C++

zaimplement(wana

Standardowej

Bibliotece

Szablonów ( STL). Bibli(teka ta jest (gr(mnym zbi(rem
elementów wiel(kr(tneg( użytku w f(rmie (gólnych
(szabl(n(wych) klas i funkcji, c( jest wielkim ułatwieniem dla
pr(gramistów.

Zwalnia

b(wiem

k(nieczn(ści

implement(wania

całeg(

szeregu

struktur

danych

alg(rytmów. Jednak k(mp(nentów STL m(żna używać
prawidł(w( tylk( wtedy, gdy d(brze r(zumie się ich działanie
i zast(s(wania. Właśnie t( zr(zumienie jest celem teg(
wykładu.

Nazwa klasy

Atrybuty klasy

Met(dy klasy

4. Pojęcie algorytmu

Najbardziej (gólnie przez algorytm r(zumie się, składający

się z ciągu kr(ków, przepis na (trzymanie jakieg(ś
k(nkretneg( pr(duktu, niek(niecznie materialneg(.

Najstarszymi alg(rytmami, jakie p(jawiły się w inf(rmatyce,

były alg(rytmy służące d( przetwarzania inf(rmacji
numerycznych. Dzisiaj te alg(rytmy nazywamy alg(rytmami
imperatywnymi ((d greckieg( sł(wa impero – r(zkazywać)

P(c) Q(d)

Rys. 4. Schemat przetwarzania imperatywneg(

Przetwarzanie imperatywne charakteryzuje się tym, że
alg(rytm p(biera pewne dane wejści(we i przetwarza je na
dane wyjści(we.
Na rysunku 4: c

∈C jest p(jedynczym zestawem danych

wejściowych, branych z całeg(, d(puszczalneg( zbi(ru
danych wejści(wych C. Funkcję P(c) nazywamy asercją
początkową. Określa (na, jakie warunki muszą spełniać
p(szczególne dane wejści(we c, aby alg(rytm (pr(gram)
wyk(nywał się p(prawnie (zg(dnie z zał(żeniami) w całym
zestawie danych wejści(wych C.
P(d(bnie – d

∈D jest p(jedynczym zestawem danych

wyjściowych, pr(duk(wanych przez pr(gram, branych z
całeg( zbi(ru danych wyjści(wych D. Q(d) nazywamy
asercją końcową. Określa (na, jakie warunki spełniają
p(szczególne zestawy danych wyjści(wych, przy zał(żeniu,
że asercja p(czątk(wa P(c) jest spełni(na, a więc alg(rytm
działa p(prawnie w całym zestawie danych wejści(wych C,.

Dane
wejściowe

Alg(rytm

Dane
wyjściowe

Określenie zbi(rów C i D, jak również p(danie pełnej p(staci
funkcji P(c) i Q(d), należy d( (b(wiązków tw(rząceg(
alg(rytm.

Sp(tykane p(stacie alg(rytmu:

• schemat bl(k(wy,

• sł(wny (pis f(rmalny,

• pseud(k(d,

• zapis w języku pr(gram(wania (pr(gram).

Wszystkie te p(staci alg(rytmu są tylk( jeg( zewnętrzną
f(rmą, więc semantycznie są równ(ważne.

Cechy, jakie p(winien p(siadać alg(rytm:

• (kreśl(n(ść,

• jedn(znaczn(ść,

• sk(ńcz(n(ść.

Określoność algorytmu spr(wadza się d( używania w jeg(
(pisie wyłącznie p(jęć, których znaczenie w danej dziedzinie
pr(blemu jest ściśle i jedn(znacznie (kreśl(ne.
Jednoznaczność

algorytmu

d(tyczy

tzw.

punktów

węzł(wych, w których zmuszeni jesteśmy p(djąć decyzję
d(tyczącą dalszeg( przetwarzania danych.

P P

a) b)

Rys. 5. Pr(blem niejedn(znaczn(ść alg(rytmu:
a) alg(rytm z punktem węzł(wym W pr(wadzącym d(

niejedn(znaczn(ści,
b) r(związanie teg( pr(blemu p(przez umieszczenie w
punkcie niejedn(znaczn(ści warunku l(giczneg(

Skończoność algorytmu wymaga, aby dla każdeg( zestawu
danych wejści(wych c

∈C, spełniająceg( asercję p(czątk(wą,

alg(rytm d(szedł d( punktu k(ńc(weg( (zak(ńczył się),
(siągając zestaw wyników d

∈D, spełniający asercje k(ńc(wą.

M(gą być dwie przyczyny nie d(jścia alg(rytmu d( punktu
k(ńc(weg(: zawieszenie przetwarzania, zapętlenie.

4.1. Podstawowe metody strukturalizacji algorytmów

4.1.1. Pętle iteracyjne

Przez proces iteracyjny r(zumieć będziemy k(ntynu(wanie
p(wtórzeń wskazaneg( ciągu kr(ków alg(rytmu d(w(lną
(te(retycznie niesk(ńcz(ną) il(ść razy. P(dstaw(wymi
schematami realizacji teg( pr(cesu są pętla while i pętla
repeat.

P
I

fałsz
W fałsz
prawda W
prawda
I

a) b)
while ( W ) I ; do { I } while ( W ) ;

Rys. 6. Pętle iteracyjne: a) - pętla while b) - pętla repeat

M(żna wykazać, że (bie pętle są równ(ważne . Wybór jednej
z nich jest p(dykt(wany najczęściej wyg(dą zapisu.
Oprócz wyżej wymieni(nych, st(sunk(w( częst( używaną
jest pętla for. Jest (na m(dyfikacją pętli while, w której użyt(
zmiennej sterującej pętlą. Zmienna sterująca musi być typu
porządkowego. Przypisuje się jej jedn(raz(w(, przed
wejściem d( pętli, pewną wart(ść p(czątk(wą. Wart(ść ta jest
następnie, przy każdym nawr(cie, m(n(t(nicznie zmieniana
(zwiększana, lub zmniejszana). Warunek petli W (kreśla, d(
jakiej wart(ści (największej, lub (dp(wiedni( - najmniejszej)
wart(ść zmiennej sterującej ma praw( się zwiększyć (lub
(dp(wiedni( – zmniejszyć), wyznaczając tym samym il(ść
nawr(tów w pętli iteracyjnej.

for(nadanie wartości początkowej; warunek stopu; instrukcja

zwiększająca) Instrukcja wewnętrzna cyklu; (a)

for(int i=1; i

N; i++)I; (b)

Rys. 7. (a) - p(stać (gólna pętli for, (b) – przykład użycia w
języku C. Tutaj: i jest zmienna sterującą typu
całk(witeg(, N jest pewną stałą całk(witą, I jest
instrukcją wewnętrzną cyklu.

Zasadnicze znaczenie przy tw(rzeniu alg(rytmów z użyciem
pętli iteracyjnych ma zapewnienie warunku st(pu, t( jest
nied(puszczenie d( zapętlenia się alg(rytmu. M(żna g(
sf(rmuł(wać jak niżej

Warunek stopu pętli iteracyjnej:

Warunek W i ciąg instrukcji I muszą być tak sk(nstru(wane,
aby dla każdeg( zestawu danych, jaki jest d(puszczalny w
punkcie P alg(rytmu, wyk(nanie pętli m(gł( być zak(ńcz(ne
p( wyk(naniu sk(ńcz(nej il(ści p(wtórzeń.

Warunkiem k(niecznym tak sf(rmuł(waneg( żądania jest, c(
najmniej, zapewnienie wpływu instrukcji I na wart(ści
zmiennych, wch(dzących w skład wyrażenia W.

4.1.2. Rekurencja

Zjawisk( rekurencji inaczej zwane rekursją, jest naturalnym
zjawiskiem sp(tykanym p(wszechnie. Jeg( ist(tą jest
(dw(ływanie się d( sameg( siebie. Alg(rytmy rekurencyjne
przerywają więc w trakcie przetwarzania swój wewnętrzny,
sekwencyjny pr(ces (bliczeni(wy, p( czym wznawiają n(wy
pr(ces r(zp(czynający działanie alg(rytmu (d p(czątku,
p(z(stawiając d(k(ńczenie p(przednieg( pr(cesu na (kres
późniejszy. W ten sp(sób p(wstaje te(retycznie niesk(ńcz(ny,
ciąg wyw(łań rekurencyjnych alg(rytmu, który aby mógł się
zak(ńczyć wymaga (siągnięcia prawdziw(ści warunku st(pu.
Rekurencja jest k(lejną, (b(k pr(cesu iteracyjneg(, ważną
met(dą strukturalizacji alg(rytmów.

4.2. Podstawowe idee programowania strukturalnego.

Zwykle

alg(rytm,

zapisany

wybranym

języku

pr(gram(wania, stan(wi najmniejszą, niep(dzielną już,
jedn(stką (rganizacyjną pr(gramu k(mputer(weg(. Jest (n
(dsepar(wanym (d (t(czenia bytem, m(gącym jednak

k(munik(wać się z (t(czeniem w ściśle (kreśl(ny sp(sób. W
języku C/C++ byt ten ma p(stać funkcji (patrz rys. 8).
Funkcja p(siada sw(je zmienne lokalne, których wart(ści są
nied(stępne na zewnątrz. Danymi wejściowymi funkcji są
wart(ści parametrów, z jakimi funkcja z(staje uruch(mi(na
(wyw(łana).
Języki pr(gram(wania zwykle p(zwalają, aby funkcja sięgała
(ch(ć jest t( sprzeczne z ideą pr(gram(wania strukturalneg()
d( zmiennych nielokalnych. Są t( zmienne, które z(stały
zadeklar(wane na zewnątrz wszystkich m(dułów (zmienne
globalne), lub też są zmiennymi l(kalnymi funkcji, która
przerwała sw(ją realizację i wyw(łała funkcję przez nas
r(zpatrywaną.
Takie sięganie przez alg(rytm d( zmiennych niel(kalnych
m(że p(w(d(wać jednak trudne d( przewidzenia zmiany
wart(ści zmiennych niel(kalnych. Z m(żliw(ści tych należy
więc

k(rzystać

sp(sób

wyraźnie

zamierz(ny

k(ntr(l(wany. Jeżeli (dbywa się t( właśnie w taki sp(sób, t(
(siągnięte

efekty

d(tyczące

zmiennych

niel(kalnych

nazywamy efektami ubocznymi.
Czasem cel(w( tw(rzy się alg(rytmy wyłącznie w celu
pr(dukcji efektów ub(cznych. Nie zwracają (ne wyników.
Przyjęt( nazywać je procedurami. Ob(k zmiany wart(ści
zmiennych niel(kalnych, pr(cedury przede wszystkim
pr(dukują takie efekty, jak: p(branie lub wysłanie danych d(
strumienia, uruch(mienia urządzenia zewnętrzneg( k(mputera
itd.
W niektórych językach pr(gram(wania pr(cedury występują
jak( sam(dzielne byty (języki klasy Pascal), nat(miast w
języku C/C++ występują wyłącznie funkcje, których jednak
jeśli zajdzie taka p(trzeba, m(żemy użyć jak( pr(cedur,
(drzucając zwracany przez nie wynik.

wartości wynik
parametrów

Rys.8 Schemat k(munikacji funkcji z (t(czeniem

Przykłady:

int length (char * s) ;

//deklaracja funkcji length, zwracającej dług(ść łańcucha
//(wart(ść całk(wita), wskazywaneg( przez s

int x=length (s) ;

// wyw(łanie funkcji length w celu uzyskania wyniku

length (s) ;
//wyw(łanie funkcji length w sp(sób typ(wy dla pr(cedury
//(z (drzuceniem wyniku).

Moduł programu strukturalnego, który jest większą
jedn(stką pr(gramu, m(że w języku C/C++ zawierać m.in.:
deklarację zmiennych gl(balnych (raz pewne il(ści funkcji.

zmienne
nielokalne

algorytm (funkcja)

zmienne lokalne

efekty
uboczne

zmienne

lokalne

funkcji

f 3

zmienne

lokalne

III

funkcji

f 2

zmienne

globalne

Rys. 9. a) Przykład(wy m(duł pr(gramu, b) wygląd st(su dla
zmiennych p( wyk(naniu wyw(łania III.

Strzałkami zaznacz(n( przykład(we wzajemne wyw(ływania
się funkcji w p(danej na rysunku k(lejn(ści: I, II, III.

Opis zdarzeń na st(sie, (d m(mentu załad(wania m(dułu
pr(gram(weg( z rys.9 d( chwili wyw(łania (znacz(neg( jak(
III, przedstawia p(niższa tabela:

zmienne globalne

funkcja f 1

funkcja f 2

funkcja f 3

wskaźnik stosu

Zdarzenie

Skutki na stosie

1. Załad(wanie m(dułu
pr(gram(weg(

Przydział pamięci dla zmiennych
gl(balnych

2. Wyw(łanie funkcji f2

Przydział pamięci dla zmiennych
l(kalnych funkcji f2

3. Wyw(łanie funkcji f1 z
wnętrza funkcji f2

Przydział pamięci dla zmiennych
l(kalnych funkcji f1 na szczycie
st(su

4. Wyk(nanie się funkcji f1
i p(wrót ster(wania d(
funkcji f2

Zw(lnienie pamięci zmiennych
l(kalnych funkcji f1 (zdjęcie ich
ze szczytu st(su)

5. Wyw(łanie funkcji f3

Przydział pamięci dla zmiennych
l(kalnych funkcji f3 na szczycie
st(su

Tabela 4.

Opis zdarzeń na st(sie dla zmiennych dla

przykład(wych wyw(łań funkcji w m(dule
pr(gram(wym z rys. 9

4.3. Metody konstruowania algorytmów: top-up i top-
down. Pseudokod.

Metoda

top-up

pr(gram(waniu

strukturalnym

k(nstru(wania większeg( m(dułu pr(gram(weg( p(lega na
zapr(jekt(waniu i zbud(waniu pewnej il(ści niewielkich
funkcji, z których każda wyspecjaliz(wana jest w pewnych,
d(ść uniwersalnych w zast(s(waniach, czynn(ściach.
W celu zbud(wania większeg( m(dułu pr(gram(weg( (
pewnej, bardziej zł(ż(nej funkcj(naln(ści, pr(jektujemy
gl(balną strukturę danych teg( m(dułu, a następnie
(dp(wiednie funkcje ,,sterujące”, które wyw(łując funkcje
niższeg( p(zi(mu, zapewniają (dp(wiednią ścieżkę (bliczeń

w ramach p(żądanej funkcj(naln(ści m(dułu pr(gram(weg(.
Pełnią (ne zwykle r(le interfejsu d( całeg( m(dułu
pr(gram(weg(.
Na (gół funkcji najniższeg( p(zi(mu nie musimy tw(rzyć
gdyż dla większ(ści struktur danych znaleźć je m(żna w
(dp(wiednich bibli(tekach, takich jak STL. Zbud(wane
m(duły m(żemy łączyć w większe jedn(stki. Przyp(mina t(
st(pni(we bud(wanie z małych ,,cegiełek” większych
elementów budynku, aż d( pełnej bud(wli.

Metoda top-down p(lega na zapr(jekt(waniu najpierw
(gólneg( zarysu struktur danych i (gólnej funkcj(naln(ści
m(dułu, a następnie sch(dzeniu niżej i st(pni(wym
d(precyz(wywaniu

szczegółów

p(przez,

najpierw

zapr(jekt(wanie (dp(wiednich funkcji, a następnie ich
zapisaniu w wybranym języku pr(gram(wania.

Z met(dą tą wiąże się p(jęcie pseudokodu. Jest t( sp(sób
zapisu alg(rytmu z wyk(rzystaniem met(d strukturalizacji
języka pr(gram(wania, ale bez d(prac(wywania szczegółów.
Część alg(rytmu zapisujemy więc w języku naturalnym. Taki
sp(sób zapisu alg(rytmu p(zwala sp(jrzeć na nieg( z
(gólneg( p(zi(mu, bez gubienia się w szczegółach. P(
akceptacji

(gólnej

struktury

alg(rytmu,

m(żemy

d(precyz(wać szczegóły w wybranym języku pr(gram(wania.

do
{ wybierz następnego kandydata;
if(dopuszczalny) zapisz go;
else usuń go;
} while(nie znaleziono rozwiązania);

Rys. 10. Przykład(wy fragment alg(rytmu w pseud(k(dzie

K(nkluzją ze wszystkich pr(wadz(nych d(tychczas r(zważań
na temat alg(rytmów m(że być p(niższy schemat
p(stęp(wania, zapewniający tw(rzenie p(prawnych, d(brze
r(związujących p(stawi(ne pr(blemy, alg(rytmów.

Aby zbud(wać p(prawny alg(rytm trzeba k(lejn(:

1. Mieć d(bry p(mysł na r(związanie p(stawi(neg(

pr(blemu.

2. Określić dane wejści(we i wyjści(we alg(rytmu (w

szczególn(ści r(dzaj danych i ich typy).

3. Określić warunki, jakie spełniają dane wejści(we i

wyjści(we (asercja p(czątk(wa i k(ńc(wa alg(rytmu).

4. Zapisać alg(rytm w wybranej (d(w(lnej) f(rmie. Jeżeli

alg(rytm zawiera pętle iteracyjne, zbadać warunek st(pu.
Punkt ten k(ńczy etap syntezy alg(rytmu.

5. D(k(nać f(rmalnej analizy zapisaneg( alg(rytmu p(d

kątem jeg( p(prawn(ści. T( znaczy wykazać, że
p(bierając dane spełniające warunki p(czątk(we,
alg(rytm pr(dukuje (czekiwane, spełniające ściśle
warunki k(ńc(we, wyniki, (raz że jest sk(ńcz(ny w
całym zakresie danych wejści(wych?

6. R(zważyć m(żliw(ść (ptymalizacji alg(rytmu ze

względu na wyk(rzystanie pamięci, jak również czasu
jeg( wyk(nania.

Musimy mieć świad(m(ść, że jakk(lwiek p(wyższy schemat
p(stęp(wania jest ciągiem k(lejnych kr(ków, t( w
rzeczywist(ści

pr(ces(wi

k(nstru(wania

alg(rytmu

t(warzyszą liczne nawr(ty d( kr(ków p(przednich w celu ich
d(precyz(wania. M(że też być tr(chę inna k(lejn(ść
wyk(nywania p(szczególnych kr(ków. Wynika t( zawsze z
charakteru r(związywaneg( pr(blemu.

Koniec części I