Eljárások és függvények

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.

Az eljárások és függvények közös tulajdonságai:

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.

Deklarálás, indítás:

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ának menete:

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

 

Érték szerinti paraméterátadás:

A formális paraméterlistában lévő változó a hívásnál megadott értéket veszi fel.

 

Cím szerinti paraméterátadás:

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

Rekurzió:

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ó hátránya:

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!

 

Quicksort (gyorsrendezés):

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.

Back-track keresés:

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

Szűcs Tamás - szucs_t@freestart.hu