Az Adatszerkezetek 2. rész ismertetése előtt fontosnak tartottuk bemutatni az eljárásokat és függvényeket.
Hogy az eljárások és függvények ismertetése, bemutatása ne csak egyszerű elmélet legyen ezért összefűztük hasznos dolgokkal (algoritmusokkal), mint pl. a különböző rendezési/keresési módszerekkel, a Fibonacci sorozat számításával, egy- illetve kétismeretlenes egyenletek megoldásával, faktoriális számítással stb.
Az eljárások és a függvények tulajdonképpen alprogramok - a Turbo Pascal erősen támogatja őket.
Az eljárások elkülönült, önálló feladattal rendelkező programegységek. Általában akkor használjuk őket, ha részfeladatokra kell bontani az algoritmust vagy bizonyos összefüggő utasításokat kell ismételgetni.
A függvények olyanok, mint az eljárások, de van egy visszatérő értékük. Végrehajt egy algoritmust, és egy visszatérő értéket ad.
Vannak saját változójuk, amelyek az eljárás tevékenységében segédkeznek. Ezek a lokális változók.
Hivatkozhatnak a főprogram vagy a fölöttük álló, őket meghívó alprogramok változóira. A főprogram minden alprogram által látható változói globális változók.
Paraméterezhetők: adott bemeneti értéket adhatunk nekik. Ha van paraméter, akkor az is lokális környezetbe tartozik.
ELJÁRÁS Eljárásnév(formális paraméterlista)
Lokális változók deklarálása
ELKEZD
-
EVÉGE
FŐPROGRAM
Elkezd
-
Eljárásnév(aktuális paraméterlista)
-
Fvége
FÜGGVÉNY Függvénynév(formális paraméterlista):típus
Lokális változók deklarálása
Elkezd
-
Függvénynév:=érték
Fvége
FŐPROGRAM
Elkezd
-
Változó:=Függvénynév(aktuális paraméterlista)
-
Fvége
Példa:
ELJÁRÁS Lkeres(X:Egész)
I:Egész
Elkezd
Ciklus I:=1-től N-ig
Ha T[I]=X akkor
Ki: I
Havége
Cvége
Evége
FŐPROGRAM
Elkezd
Ciklus I:=1-től N-ig
Be: T[I]
Cvége
Be: A
Lkeres(A)
Be: A
Lkeres(A-1)
Lkeres(4)
Fvége
X lokális változó, T globális változó. Változó hatásköre azt mutatja meg, hogy a változó a program mely területén van értelmezve. A globális változók a program tetszőleges területén használhatók, a lokális változók egy eljárás vagy függvény területén belül használhatóak. Ha a lokális változó jele egyenlő a globális változó jelével, akkor a lokális változót használja az alprogram.
Az eljárások és függvények végrehajtását az eljárás nevének leírásával tudjuk aktiválni.
Az eljárás vagy függvény elindulása után létrejönnek a formális paraméterlistában lévő változók.
Ezután ezek a változók felveszik az eljáráshívásnál megadott kezdőértékeket.
Létrejönnek az eljárás lokális változói.
Végrehajtódnak az eljárásban leírt utasítások, amíg az Evége kulcsszóhoz nem ér a program.
Az Evége sor végrehajtásakor megszűnnek a lokális változók.
Az aktuális paraméterlista értékeit felveszi a formális paraméterlistában lévő változó, de a paraméter a globális változó értékeit nem befolyásolja.
Az alprogram aktuális paraméterlistája az alprogram hívásának pillanatában a konkrét értékeket tartalmazza. Az aktuális és a formális paraméterlista értékeinek száma és típusa egyenlő legyen!
Példa:
Program Elso
T:tomb[1..10] Egészből
Db:Egész
ELJÁRÁS Megszamol(x: Egész; T:tömb; N: Egész)
I:Egész
Elkezd
Db:=0
Ciklus I:=1-től 10-ig
Ha T[I]=x akkor
Db:=Db+1
Havége
Cvége
Evége
FŐPROGRAM
Megszamol(14; T; N)
Ki: Db
Fvége
A formális paraméterlistában lévő változó a hívásnál megadott értéket veszi fel.
A formális paraméterlistában lévő változó a hívásnál megadott változó memóriacímét veszi fel, így az aktuális paraméterlistában megadott változó értékét is automatikusan változtatja.
Példa:
ELJÁRÁS Rendez(CSZ A:tömb; N:Egész)
I,J,C:Egész
Elkezd
-
Evége
FŐPROGRAM
Rendez(T,10)
Fvége
A formális paraméterlistában feltüntetett változó memóriacíme ugyanoda fog kerülni, mint az aktuális paraméterlistában megadott változó memóriacíme. Így, ha az egyik értékét változtatjuk, a másik értéke is változik.
Cím szerinti paraméterátadáskor az aktuális paraméter csak változó lehet. Érték szerinti paraméterátadáskor az aktuális paraméter érték, konstans, kifejezés és változó is lehet.
Érték szerinti paraméterátadás: kifejezés (azonos típusú) - bemenő
Cím szerinti paraméterátadás: kifejezés (azonos típusú) - bemenő és kimenő
Példa 1.:
Egyismeretlenes egyenlet megoldása:
AX+B=0
a)
FÜGGVÉNY Egyismmegold(A,B:Egész):Valós
Elkezd
Egyismmegold:=B/A
Fvége
FÜGGVÉNY Egyism(A,B:Egész):Logikai
Elkezd
Ha A<>0 akkor
Egyism:=Igaz
Különben
Egyism:=Hamis
Havége
Fvége
FŐPROGRAM
Elkezd
-
Ha Egyism(-2,4) akkor
Ki: ’Van megoldása.’
Ki: Egyismmegold(-2,4)
Különben
Ki: ’Nincs megoldása.’
Havége
Fvége
b)
FÜGGVÉNY Egyism(A,B:Egész; CSZ X:Valós):Logikai
Elkezd
Ha A<>0 akkor
Egyism:=Igaz
X:=-B/A
Különben
Egyism:=Hamis
Havége
Fvége
FŐPROGRAM
X:Valós
ELKEZD
-
Ha Egyism(-2,4,X)=Igaz akkor
Ki: ’Van megoldása.’
Ki: X
Különben
Ki: ’Nincs megoldása.’
Havége
Fvége
Példa 2.:
Kétismeretlenes egyenlet megoldása:
a)
FÜGGVÉNY Ketism(A,B,C:Egész; CSZ X1,X2:Valós):Egész {0: nincs megoldás, 1: 1 megoldás, 2: 2 megoldás}
b)
ELJÁRÁS Ketism(A,B,C:Egész; CSZ X1,X2:Valós)
a)
FŐPROGRAM
M1,M2:Valós
-
Ha Kétism(-2,4,8,M1,M2)=0 akkor
Ki: ’Nincs megoldása.’
Különben
Ha Ketism(-2,4,8,M1,M2)=1 akkor
Ki: ’Egy megoldása van.’
Ki: M1
Különben
Ki: ’Két megoldása van.’
Ki: M1, M2
Havége
Fvége
Hátránya az algoritmusnak, hogy többször is elvégzi a függvényszámolást.
b)
FŐPROGRAM
M1,M2:Valós
Db:Egész
-
Db:=Ketism(-2,4,8,M1,M2)
Elágazás
Ha Db=0 akkor
Ki: ’Nincs megoldása.’
Ha Db=1 akkor
Ki: M1
Különben
Ki: M1, M2
Evége
Fvége
c)
Ketism(-2,4,8,M1,M2)
A függvényt eljárásként is meghívhatjuk, de csak akkor, ha biztosak vagyunk a visszatérési értékében. Ezt a szándékunkat előre meg kell adnunk a fordítónak.
d)
Ketism(-2,4,8,M1,M2)
Ha Db:=-
Példa 3.:
Maximum-kiválasztás tétele:
FÜGGVÉNY Max(A,B:Valós):Valós
Elkezd
Ha A>B akkor
Max:=A
Különben
Max:=B
Havége
Fvége
Példa 4.:
Tömbből adja meg a maximális elem sorszámát.
FÜGGVÉNY Max(CSZ T:Tömb):Egész
M,I:Egész
Elkezd
M:=1
Ciklus I:=2-től Elemszam(T)-ig
Ha T[I]> T[M] akkor
M:=I
Havége
Max:=M
Fvége
Példa 5.:
Hatványozás (alap és kitevő):
AN
FÜGGVÉNY Hatvany(A:Valós; N:Egész):Valós
I:Egész
H:Valós
Elkezd
H:=1
Ciklus I:=1-től N-ig
H:=H*A
Cvége
Hatvany:=H
Fvége
Példa 6.:
Csere:
ELJÁRÁS Swap(CSZ A, B:Valós)
C:Valós
Elkezd
C:=A
A:=B
B:=C
Evége
Példa 7.:
Minimumkeresés:
FÜGGVÉNY Minkeres(CSZ T:Tömb; Also,Felso:Egész):Egész
I,J:Egész
Elkezd
J:=Also
Ciklus I:=Also+1-től Felso-ig
Ha T[J]> T[I] akkor
J:=I
Havége
Cvége
Minkeres:=J
Fvége
FŐPROGRAM
-
Ciklus I:=1-től N-1-ig
J:=Minkeres(A,I,N)
Swap(A[I],A[J])
Cvége
Fvége
A rekurzió saját magát használja fel, önmagára hivatkozik. Az eljárás és függvény önmagát indítja.
Példa 1.:
Faktoriális-számítás:
1, ha N=0 <- megállító (bázis) feltétel
N!
N*(N-1)!, ha N>0 <- csökkentő kifejezés
4!=4*(3)!, 3!=3*(2)!, 2!=2*(1)!, 1!=1*(0)!, 0!=1
4!=24
A rekurzió végrehajtása során véges lépésben el kell jutni a bázisfeltételhez.
a)
J:=1
Ciklus I:=1-től N-ig
J:=J*I
Cvége
Ki: J
b)
FÜGGVÉNY Fakt(N:Egész):Egész
Elkezd
Ha N=0 akkor
Fakt:=1
Különben
Fakt:=N*Fakt(N-1)
Fvége
A rekurzió vermet használ. A rekurzió, mivel önmagát hívogatja egyre mélyebb szinten, a vermet hamar feltöltheti.
Példa 2.:
Fibonacci számsor:
0, ha N=1
Fib(N) 1, ha N=2
Fib(N-1)+Fib(N-2), ha N>2
Fib(4)=Fib(3)+ Fib(2), Fib(3)=Fib(2)+ Fib(1), Fib(2)=1, Fib(1)=0
Fib(4)=2
FÜGGVÉNY Fib(N:Egész):Egész
Elkezd
Elágazás
Ha N=1 akkor
Fib:=0
Ha N=2 akkor
Fib:=1
Különben
Fib:= Fib(N-1)+Fib(N-2)
Fvége
Példa 3.:
Festés:
A kék határolásáig fessük be pirosra a mátrixot.
ELJÁRÁS Fest(X,Y,MinX,MaxX,MinY,MaxY:Egész)
Elkezd
{Csak a mátrix határáig fest:}
Ha X>=MinX és X<=MaxX és Y>=MinY és Y<=MaxY akkor
Tomb[X,Y]:=Piros
Ha X-1>=MinX és Tomb[X-1,Y]<>Kék és Tomb[X-1,Y]<>Piros akkor
Fest(X-1,Y)
Havége
Ha X+1<=MaxX és Tomb[X+1,Y]<>Kék és Tomb[X+1,Y]<>Piros akkor
Fest(X+1,Y)
Havége
Ha Y-1>=MinY és Tomb[X,Y-1]<>Kék és Tomb[X,Y-1]<>Piros akkor
Fest(X,Y-1)
Havége
Ha Y+1<=MaxY és Tomb[X,Y+1]<>Kék és Tomb[X,Y+1]<>Piros akkor
Fest(X,Y+1)
Havége
Havége
Evége
Csak addig fest, amíg az egyik irányba sem kék vagy piros a mátrix pontja, vagy el nem éri a mátrix szélét. Megtalálja a lyukat is!
Rekurzívan rendezi a vektort.
ELJÁRÁS Quicksort(CSZ T:Tömb; Also, Felso: Egész)
I,J:Egész; X:Valós
Elkezd
I:=Also
J:=Felso
X:=T[I+J/2] {középső elem sorszáma}
Ciklus
Ciklus amíg T[I]<X
I:=I+1
Cvége
Ciklus amíg T[J]>X
J:=J-1
Cvége
Ha I<J akkor
Swap(T[I], T[J])
Havége
Ha I<=J akkor {ha I=J, akkor nem kell cserélni, csak az értékeket változtatni}
I:=I+1
J:=J-1
Havége
Amíg I>J
Ha Also<J akkor
Quicksort(T,Also,J)
Havége
Ha I<Felso Akkor
Quicksort(T,I,Felso)
Havége
Evége
FŐPROGRAM
-
Elkezd
-
Quicksort(A,1,N)
Fvége
A legalsó és a legfelső elemtől csökkenti az összehasonlítandó elemeket, és azokat cseréli addig, amíg középre nem ér. Ezután, ha a legalsó elem nagyobb, mint a középső elem, akkor a közepétől a legalsó elemig hasonlítja és szükség szerint cseréli az elemeket, vagy ha a legfelső elem nagyobb, mint a középső elem, akkor a közepétől a legfelső elemig hasonlítja és szükség szerint cseréli az elemeket.
Veremfoglalása elég nagy, de kisebb tömböknél nem foglal túl sok memóriát. 160 elemnél 7 mélység, 80 elemnél 6 mélység, 40 elemnél 5 mélység, 20 elemnél 4 mélység, 10 elemnél 3 mélység, 5 elemnél 2 mélység, 2 elemnél 1 mélység.
Rekurzívan keresi a megoldást.
Ha van n db sorozatom, rendre M(1), M(2),-,M(N) elemszámmal mindegyik sorozatból ki kell választani pontosan egy elemet oly módon, hogy ezek páronként ne kerüljenek összeütközésbe egymással.
8 vezér problémája:
8 vezér problémájánál 8db sorozat van, mindegyik 8 elemszámmal. Oszlop- és sorszámuk, valamint átlójuk ((sor-X és oszlop-X) vagy (sor+X és oszlop+X) vagy (sor-X és oszlop+X) vagy (sor+X és oszlop-X)) nem egyezhet egymással.
a)
Minden lehetőséget kipróbál:
Ciklus V1:=1-től 8-ig
Ciklus V2:=1-től 8-ig
-
Ciklus V8:=1-től 8-ig
Kiprobal(V1,V2,-,V8)
Hátránya, hogy rengeteg, összesen 648 variáció lehetséges - nagyon hosszú a számolás. Akkor, ha megadjuk, hogy minden vezér csak a következő sorba kerülhet (Ciklus V2:=2-től 8-ig, Ciklus V3:=3-tól 8-ig stb.), akkor csak 88 variáció lehetséges, de az is rengeteg variáció.
b)
Megnézi, hogy eddig jó-e:
Ciklus V1:=1-től 8-ig
{itt fölösleges ellenőrizni, hogy jó-e, mert rossz nem lehet}
Ciklus V2:=1-től 8-ig
Ha Ellenoriz(V1,V2) akkor
Ciklus V3:=1-től 8-ig
Ha Ellenoriz(V1,V2,V3) akkor
-
Példa:
Betűszámtanos sorozat (milyen számokat takarnak a betűk):
SEND
+MORE
MONEY
Felhasznált betűk: SENDMORY
Ciklus D:=0-tól 9-ig
Ciklus E:=0-tól 9-ig
Ha Ellenoriz1(D,E) akkor
Ciklus N:=0-től 9-ig
Ha Ellenoriz2(D,E,N) akkor
-
FÜGGVÉNY Ellenoriz1(A,B:Egész):Logikai
Elkezd
Ha A<>B akkor
Ellenoriz1:=Igaz
Y:=(D+E)DIV10
Különben
Havége
Fvége
FÜGGVÉNY Ellenoriz2(A,B,C:Egész):Logikai
Elkezd
Ha A<>B és B<>C akkor
Ellenoriz2:=Igaz
-
Ha R<>D és R<>N és R<>E és R<>Y
Ha (N+R+A1)Div10=E
A2:=(N+R+A1)/10
Ha O<>D és O<>N és O<>E és O<>Y és O<>R
Ha (E+O+A2)Div10=N
A3:=(E+O+A2)/10
Ha (S+M+A3)Div10=O
A4:=(S+M+A3)/10
M=4!
M<>O
A Back-track algoritmus:
Meg is mondja, hogy nincs megoldása - ha az első sorban nincs jó eset.
FŐPROGRAM
I:=1
X[1]:=0
Ciklus amíg 1<=I és I<=N
Ha Vanjoesetasorban(I) akkor
I:=I+1
X[1]:=0
Különben
I:=I-1
Cvége
Ha I>N akkor VAN EGY MEGOLDÁSA!
-- Visszalép, ha nem jó a megoldás. Ha I elérte az utolsó elemet (N-et túllépte), akkor megtalálta a (néhány közül az egyik) megoldást.
FÜGGVÉNY Vanjoesetasorban(I):Logikai
Ciklus
X[I]:=X[I]+1
Amíg X[I]<=Max[I] és Rosszeset(I,X[I])
Vanjoesetasorban:=X[I]<=Max[I]
-- Addig fut, amíg túl nem lépne a sor végétől, és rossz a vezér helye. Ha igaz, akkor az elemnek megvan a helye (az I. az).
FÜGGVÉNY Rosszeset(I,X[I]):Logikai
J:=1
Ciklus amíg (J<I és Ütkozik(a J,X[J]. elem az I,X[I]. elemmel)
J:=J+1
Cvége
Rosszeset:=J<I {ha igaz, akkor ütközik, ha hamis, akkor nem ütközik a vezér}
-- Végignézi az összes sort az elsőtől kezdve, és ha nem ütközik az új elem helyével, akkor Hamis értékkel visszatér.
Az I azt mutatja, hogy hányadik sorban kívánunk elemet elhelyezni. Az X[I] azt mutatja, hogy az I. sor hányadik oszlopában van az elem.
8 vezér problémájának megoldása:
FŐPROGRAM
N:=8
I:=1
X[1]:=0
Ciklus amíg 1<=I és I<=N
Ha Vanjoesetasorban(I) akkor
I:=I+1
X[I]:=0
Különben
I:=I-1
--Ha az összes megoldást ki akarjuk íratni (ne lépjen ki egy megoldás után):
Havége
Ha I>N akkor
Ciklus I:=1-től N-ig
Ki: X[I]
Cvége
I:=I-1
Havége
Cvége
Ha I>N akkor
Ciklus I:=1-től N-ig
Ki: X[I]
Cvége
Havége
FÜGGVÉNY Vanjoesetasorban(I)
Ciklus
X[I]:= X[I]+1
Amíg X[I]<=N és Rosszeset(I, X[I])
Vanjoesetasorban:= X[I]<=N
FÜGGVÉNY Rosszeset(I, X[I])
J:=1
Ciklus amíg J<I és X[I]<> X[J] és I-J<>ABS(-X[J])
J:=J+1
Cvége
Rosszeset:=J<I