Algorytmy i struktury danych - 02. ...

[ Pobierz całość w formacie PDF ]
Algorytmy i Struktury danych, wer. C/C++, Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Strona 1
Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Wst
ħ
p
To lekcja o rekurencji. Zapowiadali
Ä»
my j
Ä¢
od samego pocz
Ä¢
tku. Teraz pokazujemy j
Ä¢
w szczegółach - cał
Ä¢
anatomi
ħ
wywołania
rekurencyjnego. Postarajcie si
ħ
jak najlepiej to prze
Ä»
ledzi
Ä™
i zrozumie
Ä™
. Tego nie mo
Ň
na nauczy
Ä™
si
ħ
na pami
ħę
. To trzeba zobaczy
Ä™
- i
si
ħ
zachwyci
Ä™
. Programista nie b
ħ
dzie profesjonalist
Ä¢
w swoim zawodzie, je
Ä»
li nie b
ħ
dzie miał wyczucia w stosowaniu rekurencji. Po
tym, czy umie j
Ä¢
stosowa
Ä™
, mo
Ň
na pozna
Ä™
prawdziwego guru...
ZÅ‚o
Ň
ono
Ļę
obliczeniowa
Zagadnienia zło
Ň
ono
Ä»
ci obliczeniowej algorytmów stanowi
Ä¢
prawie zawsze klasyczne rozdziały wst
ħ
pne w podr
ħ
cznikach
po
Ä»
wi
ħ
conych algorytmom i strukturom danych. Uzasadnieniem tego jest konieczno
Ļę
przybli
Ň
enia poj
ħę
, które b
ħ
d
Ä¢
słu
Ň
yły do oceny
jako
Ä»
ci prezentowanych pó
Å…
niej szczegółowo algorytmów. Mogli
Ä»
cie zauwa
Ň
y
Ä™
,
Ň
e ju
Ň
w poprzedniej lekcji nie unikn
ħ
li
Ä»
my
odwoływania si
ħ
do zło
Ň
ono
Ä»
ci obliczeniowej, bez bli
Ň
szego wyja
Ä»
niania, na czym rzecz polega. Teraz wi
ħ
c najwy
Ň
szy czas na
wprowadzenie elementarnych podstaw w tym zakresie.
ZÅ‚o
Ň
ono
Ļę
obliczeniowa algorytmu okre
Ä»
lona jest przez czas i pami
ħę
potrzebne do jego wykonania. Mówimy wi
ħ
c o
zło
Ň
ono
Ä»
ci
czasowej
i
zło
Ň
ono
Ä»
ci pami
ħ
ciowej
. Zagadnienia te zwykle staj
Ä¢
si
ħ
wa
Ň
ne dopiero wtedy, gdy stajemy przed problemami
przetwarzania du
Ň
ych ilo
Ä»
ci danych. Projektuj
Ä¢
c algorytm dla rozwi
Ä¢
zania takiego zadania chcieliby
Ä»
my, by jego zło
Ň
ono
Ļę
obliczeniowa była jak najmniejsza - by program liczył si
ħ
jak najkrócej i zabierał jak najmniej pami
ħ
ci. Nie zawsze takie podej
Ä»
cie jest
prawidłowe - cz
ħ
sto lepiej jest dobra
Ä™
prostszy algorytm, który zrealizuje zadanie w dostatecznie krótkim czasie, ni
Ň
poszukiwa
Ä™
algorytmu szybszego, lecz bardziej zło
Ň
onego, a przez to trudniejszego w implementacji, co mo
Ň
e by
Ä™
przyczyn
Ä¢
bł
ħ
dów.
Zupełnie bowiem niezale
Ň
n
Ä¢
i nadrz
ħ
dn
Ä¢
spraw
Ä¢
s
Ä¢
zagadnienia
poprawno
Ä»
ci algorytmów
. Nie ma sensu zajmowa
Ä™
si
ħ
zło
Ň
ono
Ä»
ci
Ä¢
algorytmu, którego poprawno
Ļę
budzi w
Ä¢
tpliwo
Ä»
ci. Dbało
Ļę
o poprawno
Ļę
algorytmu musi by
Ä™
wi
ħ
c z natury rzeczy pierwszoplanowa.
Dowodzenie poprawno
Ä»
ci (w tym równie
Ň
tzw. poprawno
Ä»
ci cz
ħĻ
ciowej) algorytmów jest jednak zagadnieniem trudnym i
wykraczaj
Ä¢
cym poza ramy tego podr
ħ
cznika. Jednym z najbardziej oczywistych wymaga
ı
jest tzw. własno
Ļę
stopu algorytmu, czyli
sko
ı
czono
Ä»
ci oblicze
ı
- dla poprawnych danych algorytm powinien zatrzyma
Ä™
si
ħ
w sko
ı
czonym czasie. Ale dowodzenie własno
Ä»
ci
stopu te
Ň
nie jest spraw
Ä¢
trywialn
Ä¢
.
Skoro dowodzenie poprawno
Ä»
ci algorytmów nie jest łatwe ani cz
ħ
sto stosowane w praktyce, najpewniejsz
Ä¢
zasad
Ä¢
jest pisanie
programów prostych i przejrzystych, a dopiero potem, gdy zajdzie taka potrzeba, zastanawianie si
ħ
nad zmniejszeniem ich zło
Ň
ono
Ä»
ci
obliczeniowej.
BÅ‚
ħ
dem byłoby jednak całkowite pomijanie problemu zło
Ň
ono
Ä»
ci nawet przy prostych zagadnieniach. Przypomnijcie sobie z lekcji
programowania proste zadanie wydrukowania elementów le
ŇĢ
cych na głównej przek
Ä¢
tnej tablicy kwadratowej A o n*n elementach.
Rozwi
Ä¢
zaniem wła
Ä»
ciwym jest zastosowanie pojedynczej p
ħ
tli for z odwołaniem si
ħ
do kolejnych elementów A[i,i]. Zadanie to
rozwi
Ä¢
zuje si
ħ
wi
ħ
c w czasie liniowo proporcjonalnym do n, czyli rozmiaru tablicy. Mówimy,
Ň
e zło
Ň
ono
Ļę
czasowa tego algorytmu
jest rz
ħ
du O(n). Za chwil
ħ
wyja
Ä»
nimy dokładniej, co to znaczy.
Zadanie pobrania elementów z głównej przek
Ä¢
tnej tablicy mo
Ň
e by
Ä™
te
Ň
zrealizowane według du
Ň
o bardziej pracochłonnego algorytmu,
jaki nieraz obserwujemy jako wynik prac zaliczeniowych pocz
Ä¢
tkuj
Ä¢
cych studentów. Przechodz
Ä¢
oni w p
ħ
tli podwójnej wszystkie
elementy (i,j) tablicy, za ka
Ň
dym razem sprawdzaj
Ä¢
c, czy mo
Ň
e ju
Ň
trafili na przek
Ä¢
tn
Ä¢
, czyli czy indeks i jest równy indeksowi j.
Zamiast wykona
Ä™
n kroków - wykonuj
Ä¢
n
2
kroków, i to wymagaj
Ä¢
cych dodatkowo wykonania instrukcji warunkowej. ZÅ‚o
Ň
ono
Ļę
takiego "algorytmu" jest rz
ħ
du O(n
2
). Jak wida
Ä™
, ten tzw. naiwny algorytm o du
Ň
ej (bo opisanej funkcj
Ä¢
kwadratow
Ä¢
) zło
Ň
ono
Ä»
ci bardzo
Å‚atwo jest zast
Ä¢
pi
Ä™
algorytmem działaj
Ä¢
cym w czasie liniowym. Inne ciekawe przykłady prostych ulepsze
ı
algorytmów naiwnych, które
obni
Ň
aj
Ä¢
zło
Ň
ono
Ļę
z kwadratowej na liniow
Ä¢
, znajdziecie
na tej stronie
, w uniwersyteckim portalu informatycznym WA
ņ
NIAK:
wazniak.mimuw.edu.pl
.
W analizie algorytmów zagadnienia zło
Ň
ono
Ä»
ci czasowej s
Ä¢
znacznie wa
Ň
niejsze i znacznie cz
ħĻ
ciej rozpatrywane ni
Ň
zagadnienia
zło
Ň
ono
Ä»
ci pami
ħ
ciowej, bo brak pami
ħ
ci nie jest w dzisiejszych czasach spraw
Ä¢
krytyczn
Ä¢
. Aby uniezale
Ň
ni
Ä™
si
ħ
od sprz
ħ
tu, na któym
realizowany jest algorytm, zło
Ň
ono
Ļę
czasow
Ä¢
mierzy si
ħ
jako liczb
ħ
wykonanych operacji charakterystycznych dla algorytmu i
decyduj
Ä¢
cych o jego koszcie - s
Ä¢
to tzw.
operacje dominuj
Ä¢
ce
, takie jak np. porównywanie i zamiana elementów w algorytmach
sortowania. ZÅ‚o
Ň
ono
Ļę
jest przy tym oceniana jako funkcja rozmiaru zadania - rozumianego jako liczba danych, na których algorytm
operuje (na przykład liczba danych, które maj
Ä¢
by
Ä™
posortowane).
Notacja du
Ň
ego O
2008-03-07 18:49:14
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Strona 2
Wiemy ju
Ň
,
Ň
e oceniajac koszt algorytmów najcz
ħĻ
ciej posługujemy si
ħ
tzw. notacj
Ä¢
"du
Ň
ego O". Zamiast powiedzie
Ä™
,
Ň
e algorytm
wykonuje si
ħ
w czasie proporcjonalnym do kwadratu warto
Ä»
ci n, gdzie n jest liczb
Ä¢
danych, mówimy,
Ň
e zło
Ň
ono
Ļę
algorytmu jest
rz
ħ
du O(n
2
). Notacja "du
Ň
ego O" zdefiniowana jest nast
ħ
puj
Ä¢
co:
Mówimy,
Ň
e funkcja f ma zło
Ň
ono
Ļę
O(g(n)), je
Ä»
li istnieje pewna dodatnia stała c oraz pewna nieujemna warto
Ļę
całkowita N,
taka
Ň
e dla wszystkich n >= N spełniona jest zale
Ň
no
Ļę
f(n) <= cg(n).
Oznacza to,
Ň
e dla dostatecznie du
Ň
ego n i dla pewnej stałej c wykres funkcji zło
Ň
ono
Ä»
ci f(n) le
Ň
y poni
Ň
ej wykresu funkcji c g(n).
Zobaczcie to na przykładzie trzech funkcji opisuj
Ä¢
cych zło
Ň
ono
Ļę
obliczeniow
Ä¢
i przedstawionych na poni
Ň
szym wykresie:
Jedna z tych funkcji jest funkcj
Ä¢
kwadratow
Ä¢
. Druga z nich, funkcja f(n), dla małych n le
Ň
y powy
Ň
ej wykresu funkcji kwadratowej, ale
poczynaj
Ä¢
c od pewnego n le
Ň
y całkowicie pod wykresem funkcji kwadratowej. Mo
Ň
emy wi
ħ
c powiedzie
Ä™
,
Ň
e funkcja f(n) jest rz
ħ
du O
(n
2
). Co wi
ħ
cej, to samo mo
Ň
emy powiedzie
Ä™
równie
Ň
o funkcji liniowej, jakkolwiek w tym przypadku bardziej naturalne jest
okre
Ä»
lenie jej jako funkcji O(n). Dla danej funkcji f istnieje niesko
ı
czenie wiele funkcji cg(n) ograniczaj
Ä¢
cych j
Ä¢
od góry, ale z reguły
wybiera si
ħ
t
ħ
"najmniejsz
Ä¢
" - w tym przypadku liniow
Ä¢
, a nie kwadratow
Ä¢
.
Notacja "du
Ň
ego O" dotyczy wi
ħ
c asymptotycznego kresu górnego zło
Ň
ono
Ä»
ci - opisuje asymptotyczne zachowanie funkcji, jej
ograniczenie od góry, dla odpowiednio du
Ň
ego n. Zauwa
Ň
my te
Ň
,
Ň
e zarówno 10n
2
+100n, jak i n
2
/10 s
Ä¢
rz
ħ
du O(n
2
).
Na zako
ı
czenie popatrzcie na poni
Ň
szy wykres. Przedstawione s
Ä¢
tu trzy najcz
ħĻ
ciej spotykane funkcje opisuj
Ä¢
ce zło
Ň
ono
Ļę
obliczeniow
Ä¢
typowych algorytmów w zale
Ň
no
Ä»
ci od rozmiaru zadania n. Zwró
Ä™
cie uwag
ħ
na funkcj
ħ
nlgn
, le
ŇĢ
c
Ä¢
pomi
ħ
dzy funkcj
Ä¢
liniow
Ä¢
a kwadratow
Ä¢
, ale znacznie bli
Ň
ej tej liniowej. To tzw. funkcja liniowo-logarytmiczna, przy czym uwaga: lgn jest to
logarytm
przy podstawie 2
z warto
Ä»
ci n. To osi
Ä¢
gni
ħ
cie tej wła
Ä»
nie obni
Ň
onej zło
Ň
ono
Ä»
ci, zamiast zło
Ň
ono
Ä»
ci opisanej funkcj
Ä¢
kwadratow
Ä¢
, jest
bardzo cz
ħ
sto efektem zastosowania specjalnie dobranych algorytmów - wtedy kiedy uzyskanie zło
Ň
ono
Ä»
ci liniowej nie jest mo
Ň
liwe
lub bardzo trudne. Przykładowo w nast
ħ
pnej lekcji zajmiemy si
ħ
ró
Ň
nymi algorytmami sortowania. Poka
Ň
emy,
Ň
e proste algorytmy
sortowania maja zło
Ň
ono
Ļę
O(n
2
), szybkie algorytmy sortowania maj
Ä¢
zło
Ň
ono
Ļę
O(n lgn).
2008-03-07 18:49:14
Algorytmy i Struktury danych, wer. C/C++, Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Strona 3
Warto te
Ň
podkre
Ä»
li
Ä™
,
Ň
e bardzo niska zło
Ň
ono
Ļę
O(lgn), mo
Ň
liwa do uzyskania w niektórych algorytmach (np. w przeszukiwaniu
binarnym, co poka
Ň
emy w nast
ħ
pnym rozdziale) na poni
Ň
szym wykresie obrazowana byłaby funkcj
Ä¢
prawie pokrywaj
Ä¢
c
Ä¢
si
ħ
z osi
Ä¢
ox,
trudn
Ä¢
do narysowania. Z kolei funkcja 2
n
wznosiłaby si
ħ
bardzo stromo, blisko osi oy - tak wysok
Ä¢
zło
Ň
ono
Ļę
maj
Ä¢
niektóre algorytmy,
które zajmiemy si
ħ
jeszcze w tej lekcji.
Rekurencja
Wspomnieli
Ä»
my ju
Ň
wcze
Ä»
niej,
Ň
e podprogram mo
Ň
e wywoływa
Ä™
inne podprogramy. W szczególno
Ä»
ci mo
Ň
e równie
Ň
wywoływa
Ä™
samego siebie - to prawie jak z w
ħŇ
em zjadaj
Ä¢
cym swój własny ogon :). Wywołanie takie, jak pami
ħ
tacie z lekcji 1, nazywamy
wywołaniem rekurencyjnym.
Co to jest ?
Ogólnie
rekurencj
Ä¢
(lub
rekursj
Ä¢
) nazywamy sposób pojmowania rzeczy w kategoriach odwoływania si
ħ
od samych siebie. Zakrawa
to oczywi
Ä»
cie na syndrom niesko
ı
czono
Ä»
ci i jako takie jawi nam si
ħ
jako nieco niezwykłe. Lecz postaramy si
ħ
Wam pokaza
Ä™
,
Ň
e ów
"syndrom niesko
ı
czono
Ä»
ci" jest jedynie paradoksem, a sama rekurencja jest bardzo eleganck
Ä¢
konstrukcj
Ä¢
cz
ħ
sto wykorzystywan
Ä¢
w
programowaniu. Przy czym w tej lekcji poznacie rekurencyjne wywołania podprogramów, natomiast w lekcji 4 - najprostsz
Ä¢
rekurencyjn
Ä¢
struktur
ħ
danych.
Rekurencyjna funkcja odwołuje si
ħ
w sposób po
Ä»
redni b
Ä¢
d
Å…
bezpo
Ä»
redni do samej siebie. Bezpo
Ä»
redni
Ä¢
rekurencj
ħ
bardzo Å‚atwo
zaobserwowa
Ä™
. Je
Ä»
li gdziekolwiek w kodzie programu napotkacie co
Ä»
takiego:
void
ZROB_COS (){
...
ZROB_COS();
// wywołanie funkcji przez sam
Ä¢
siebie
...
}
to wła
Ä»
nie oznacza,
Ň
e natkn
ħ
li
Ä»
cie si
ħ
na kod rekurencyjny.
2008-03-07 18:49:14
Algorytmy i Struktury danych, wer. C/C++, Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Strona 4
Do czego wykorzystuje si
ħ
rekurencj
ħ
? Zanim przedstawimy Wam proste matematycznie przykłady, poka
Ň
emy,
Ň
e zwykłe codzienne
czynno
Ä»
ci te
Ň
mo
Ň
na zapisa
Ä™
w sposób rekurencyjny. Popatrzcie na taki przykład, którego pomysł jest podawany w wielu miejscach za
informatykiem A.P. Jerszowem:
void
JEDZ_KASZK
Ħ
() {
zjedz_Å‚y
Ň
k
ħ
_kaszki;
if
(! talerz_pusty)
JEDZ_KASZK
Ħ
();
// tu funkcja wywołuje sam
Ä¢
siebie;
}
Cykliczna czynno
Ļę
zjadania kaszki Å‚y
Ň
ka po Å‚y
Ň
ce została tu zapisana...bez u
Ň
ycia p
ħ
tli. Ale ta p
ħ
tla istnieje, tyle
Ň
e w sposób niejawny
- ukryta jest wła
Ä»
nie w rekurencji. Ka
Ň
dorazowe wywołanie funkcji JEDZ_KASZK
Ħ
powoduje zjedzenie kolejnej Å‚y
Ň
ki i ponowne jej
wywołanie, czyli znowu zjedzenie jednej łyzki i kolejne wywołanie funkcji - i tak w kółko, a
Ň
do momentu, gdy talerz b
ħ
dzie pusty.
Mo
Ň
na by powiedzie
Ä™
: a po co tu stosowa
Ä™
rekurencj
ħ
? To samo mo
Ň
na przecie
Ň
zapisa
Ä™
pro
Ä»
ciej, z u
Ň
yciem p
ħ
tli, któr
Ä¢
dobrze znamy:
void
JEDZ_KASZK
Ħ
() {
do
zjedz_Å‚y
Ň
k
ħ
_kaszki;
while
(! talerz_pusty);
}
I rzeczywi
Ä»
cie, w tym przypadku tak jest. Ale ten banalny zdawałoby si
ħ
pomysł dobrze słu
Ň
y pokazaniu idei zapisu rekurencyjnego i
pozwala zrozumie
Ä™
jego zasad
ħ
. I zaraz zobaczycie,
Ň
e nie ka
Ň
d
Ä¢
rekurencj
ħ
da si
ħ
tak Å‚atwo zast
Ä¢
pi
Ä™
iteracj
Ä¢
.
Najpierw jednak zaczniemy od przykładu bardzo w swej konstrukcji podobnego do tego powy
Ň
ej. Załó
Ň
my,
Ň
e mamy
wczytywa
Ä™
i
drukowa
Ä™
kolejne liczby całkowite a
Ň
do napotkania zera
(zero te
Ň
trzeba drukowa
Ä™
).Funkcj
ħ
realizuj
Ä¢
c
Ä¢
to zadanie mo
Ň
na bardzo
Å‚atwo napisa
Ä™
w sposób nierekurencyjny, przy u
Ň
yciu p
ħ
tli repeat:
1.
void
CZYTAJ_i_PISZ() {
// wersja iteracyjna
2.
int
x;
// zmienna lokalna
3.
do
{
4.
cin >> x;
// wczytanie liczby
5.
cout << x <<
' '
;
// wydrukowanie liczby wczytanej
6.
}
while
(! x==0);)
// dopóki nie napotkano zera
7.
}
Z rekurencyjn
Ä¢
wersj
Ä¢
te
Ň
powinni
Ä»
cie ju
Ň
sobie poradzi
Ä™
: trzeba to zrobi
Ä™
prawie tak samo, jak w przykładzie z kaszk
Ä¢
:
1.
2.
void
CZYTAJ_i_PISZ() {
// wersja rekurencyjna
3.
int
x;
// zmienna lokalna
4.
cin >> x;
// wczytanie liczby
5.
cout << x <<
' '
;
// wydrukowanie liczby wczytanej
6.
if
(! x==0)
// je
Ä»
li nie wczytano zera
7.
CZYTAJ_i_PISZ;
// funkcja wywołuje sam
Ä¢
siebie
8.
}
Jak to działa
Przedstawione powy
Ň
ej przykłady zawieraj
Ä¢
najprostsze postaci rekurencji - tzw. rekurencj
ħ
ogonow
Ä¢
. Charakteryzuje si
ħ
ona tym,
Ň
e:
wywołanie rekurencyjne nast
ħ
puje na samym ko
ı
cu działania funkcji, tzn. w momencie wywołania funkcji nie ma ju
Ň
w niej
nic wi
ħ
cej do wykonania
wywołanie to jest jedynym wywołaniem rekurencyjnym w tej funkcji.
Mo
Ň
na by tak
Ä¢
funkcj
ħ
rekurencyjn
Ä¢
uzna
Ä™
za sztuk
ħ
dla sztuki (cho
Ä™
w niektórych j
ħ
zykach taki udoskonalony zapis p
ħ
tli bywa
przydatny czy wr
ħ
cz konieczny), gdyby nie to,
Ň
e ten pomysł pomo
Ň
e Wam zrozumie
Ä™
zasad
ħ
zapisu znacznie trudniejszych
algorytmów rekurencyjnych. Załó
Ň
my wi
ħ
c,
Ň
e mamy napisa
Ä™
funkcj
ħ
, która
wczytuje liczby a
Ň
do napotkania zera i drukuje w
kolejno
Ä»
ci odwrotnej
(wstecz), poczynaj
Ä¢
c od zera.
Gdyby
Ä»
cie próbowali napisa
Ä™
to z p
ħ
tl
Ä¢
, okazałoby si
ħ
natychmiast,
Ň
e nie da si
ħ
tego ju
Ň
tak prosto zrobi
Ä™
- bo trzeba gdzie
Ä»
te
wczytywane liczby przechowywa
Ä™
. Mo
Ň
na by zastosowa
Ä™
tablic
ħ
- tylko trzeba by j
Ä¢
zdefiniowa
Ä™
"na wyrost" i potem wykorzysta
Ä™
2008-03-07 18:49:14
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 2: Rekurencja i zło
Ň
ono
Ļę
obliczeniowa
Strona 5
tylko tyle miejsc, ile liczb wczytano. Nale
Ň
ałoby wi
ħ
c wczytywa
Ä™
do tablicy liczby od przodu, a potem wypisywa
Ä™
poruszaj
Ä¢
c si
ħ
wstecz. Ale okazuje si
ħ
,
Ň
e za pomoc
Ä¢
rekurencji mo
Ň
na to napisa
Ä™
znacznie pro
Ä»
ciej, i to bez nadmiarowej rezerwacji pami
ħ
ci.
Wystarczy tylko przestawi
Ä™
jedn
Ä¢
linijk
ħ
w poprzedniej funkcji - i nic wi
ħ
cej. Popatrzcie:
1.
void
PISZ_WSTECZ() {
// wersja rekurencyjna
2.
int
x;
// zmienna lokalna
3.
cin >> x;
// wczytanie liczby
4.
if
(! x==0)
// je
Ä»
li nie wczytano zera
5.
PISZ_WSTECZ();
// funkcja wywołuje sam
Ä¢
siebie
6.
cout << x <<
' '
;
// wydrukowanie liczby wczytanej
7.
}
Napiszcie sobie cały program z t
Ä¢
funkcj
Ä¢
(wystarczy j
Ä¢
po prostu wywoła
Ä™
z poziomu funkcji main) i sprawd
Å…
cie,
Ň
e to działa, cho
Ä™
na
pierwszy rzut oka wcale tego nie wida
Ä™
. Nie martwcie si
ħ
, je
Ä»
li to nie jest dla Was oczywiste. Trzeba dobrze zrozumie
Ä™
, co si
ħ
tu dzieje
i jak to wykonuje kompilator. Najwa
Ň
niejsze to zauwa
Ň
y
Ä™
,
Ň
e:
1.
funkcja wywołuj
Ä¢
c sam
Ä¢
siebie zaczyna wszystko od pocz
Ä¢
tku, czyli wczytuje liczb
ħ
, sprawdza j
Ä¢
, po czym albo j
Ä¢
drukuje i
ko
ı
czy działanie, albo nie ko
ı
czy działania, tylko ponownie wywołuje sam
Ä¢
siebie (a wi
ħ
c - zaczyna wszystko od pocz
Ä¢
tku,
czyli wczytuje liczb
ħ
...itd.)
2.
w momencie, gdy funkcja wywołuje sam
Ä¢
siebie, nie zrobiła jeszcze wszystkiego, co zawiera si
ħ
w jej tre
Ä»
ci - i
Ň
e to trzeba
b
ħ
dzie kiedy
Ä»
doko
ı
czy
Ä™
. Kiedy
Ä»
- czyli gdy zako
ı
czy si
ħ
realizacja tego samowywołania, a wi
ħ
c po zako
ı
czeniu działania
instrukcji
if
x<>0
then
PISZ_WSTECZ.
Popatrzmy dla przykładu, jak wykona si
ħ
funkcja po wczytaniu 3 liczb niezerowych i zera na ko
ı
cu:
wczytaj liczb
ħ
, a poniewa
Ň
nie jest ona zerem, wywołaj sam
Ä¢
siebie, czyli...
wczytaj liczb
ħ
, a poniewa
Ň
nie jest ona zerem, wywołaj sam
Ä¢
siebie, czyli...
wczytaj liczb
ħ
, a poniewa
Ň
nie jest ona zerem, wywołaj sam
Ä¢
siebie, czyli...
wczytaj liczb
ħ
, a poniewa
Ň
jest ona zerem, wydrukuj t
ħ
liczb
ħ
doko
ı
cz to, co zostało do zrobienia w poprzednim wywołaniu funkcji, czyli wydrukuj poprzednio wczytan
Ä¢
liczb
ħ
doko
ı
cz to, co zostało do zrobienia w jeszcze wcze
Ä»
niejszym wywołaniu funkcji, czyli wydrukuj jeszcze wcze
Ä»
niej wczytan
Ä¢
liczb
ħ
doko
ı
cz to, co zostało do zrobienia w jeszcze wcze
Ä»
niejszym wywołaniu funkcji, czyli wydrukuj jeszcze wcze
Ä»
niej wczytan
Ä¢
liczb
ħ
Schematycznie mo
Ň
na to zapisa
Ä™
nast
ħ
puj
Ä¢
co:
cin >> x;
// wczytanie pierwszej liczby
cin >> x;
// wczytanie drugiej liczby
cin >> x;
// wczytanie trzeciej liczby
cin >> x;
// wczytanie czwartej liczby
// czwarta liczba okazała si
ħ
zerem
cout << x <<
' '
;
// wydrukowanie czwartej liczby
cout << x <<
' '
;
// wydrukowanie trzeciej liczby
cout << x <<
' '
;
// wydrukowanie drugiej liczby
cout << x <<
' '
;
// wydrukowanie pierwszej liczby
Zapis taki b
ħ
dzie jednak prawidłowy tylko przy zało
Ň
eniu,
Ň
e kolejno u
Ň
ywane zmienne x to nie s
Ä¢
te same zmienne, tylko kopie
zmiennej lokalnej x, kolejno tworzone przy ka
Ň
dym wywołaniu funkcji, by nie straci
Ä™
poprzednio wczytanej warto
Ä»
ci. I tak to
rzeczywi
Ä»
cie wykonuje kompilator:
po pierwszym wywołaniu tej funkcji (czyli z poziomu funkcji main) wczytuje pierwsz
Ä¢
liczb
ħ
je
Ä»
li jest ona zerem, to j
Ä¢
drukuje i wraca do miejsca wywołania w funkcji main
je
Ä»
li za
Ä»
nie jest zerem, to zapami
ħ
tuje miejsce w funkcji main, do ktorego ma powróci
Ä™
, i zapami
ħ
tuje wczytan
Ä¢
liczb
ħ
zaczyna wykonywa
Ä™
funkcj
ħ
PISZ_WSTECZ od nowa - czyli wczytuje nast
ħ
pn
Ä¢
liczb
ħ
, ale u
Ň
ywaj
Ä¢
c nowej zmiennej lokalnej
x do jej przechowywania
je
Ä»
li nie jest ona zerem, to znowu zapami
ħ
tuje miejsce, do którego nale
Ň
y powróci
Ä™
w funkcji wywołuj
Ä¢
cej (czyli w funkcji
PISZ_WSTECZ) i zapami
ħ
tuje kolejn
Ä¢
wczytan
Ä¢
liczb
ħ
za ka
Ň
dym razem, gdy funkcja PISZ_WSTECZ wywoła sam
Ä¢
siebie, i wczyta warto
Ļę
niezerow
Ä¢
, wszystko wykonuje si
ħ
tak
samo - czyli wci
ĢŇ
nic si
ħ
nie drukuje, a tylko kolejne liczby
zapami
ħ
tywane s
Ä¢
przy u
Ň
yciu kolejnych
zmiennych
pomocniczych b
ħ
d
Ä¢
ch kopiami zmiennej lokalnej x
2008-03-07 18:49:14
  [ Pobierz całość w formacie PDF ]