Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a modul kezdőlapjáraUgrás a tananyag előző oldalára (28)Ugrás a tananyag következő oldalára (30)Fogalom megjelenítés (nem elérhető funckió)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintéseSúgó megtekintése

Tanulási útmutató

Összefoglalás

Algoritmusminták együttes alkalmazása – programozási tételek egymásra építése; feltételes maximum, K-adik adott tulajdonságú elem.

Követelmény

Önállóan megoldható feladatok

Algoritmusminták együttes alkalmazása

Gyakran előfordul, hogy programozási tételeket egymás után kell használnunk. Ezen egymásutániságnál azonban sok esetben a két megoldó algoritmus egybeépítése egyszerűbb, rövidebb, hatékonyabb megoldást eredményez. Ebben a részben ezekkel foglalkozunk. Az egymásra építés mindig két programozási tétel összefogását jelenti, a fejezeteket a korábban alkalmazandó tétel szerint fogalmaztuk meg.

Az animáció bemutatja a tételek összeépítésével kapcsolatos alapgondolatot:

Az animáció bemutatja a tételek összeépítésének értelmét.

Flash lejátszó letöltése

Tételek összeépítése

1. Másolással összeépítés

Másolással bármelyik programozási tétel egybeépíthető, hiszen csupán annyi a teendő, hogy a programozási tételben szereplő X[i] bemenő adatra hivatkozást kicseréljük g(X[i])-re.

Ha például egy számsorozat elemeinek négyzetösszegét kellene megadnunk, az egy másolást (számokhoz számok négyzetei rendelése) és egy sorozatszámítást (összegzés) tartalmaz. Nézzük meg e két tétel általános egymásra építését!

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami1],

F:Valami2*→Valami2, g:Valami1→Valami2

Kimenet

S:Valami2

Előfeltétel

∃F0∈Valami2 és

∃f:Valami2 x Valami2→Valami2 és

F(Y[1],...,Y[N])=f(F(Y[1],...,Y[N-1]),Y[N]) és F()=F0

Utófeltétel

S=F(g(X[1]),...,g(X[N]))

Az algoritmus

A megoldásban – mint azt a sorozatszámításnál tettük – induljunk ki a nullelemből, alkalmazzuk a f függvényt az addig kiszámított értékre és a sorozat eleméből kiszámított értékre!

Pszeudókód

Struktogram

Másolás_sorozatszámítás(N,X,S):

S:=F0

Ciklus I=1-től N-ig

S:=f(S,g(X[I]))

Ciklus vége

Eljárás vége.

Másolás + sorozatszámítás tétel algoritmusa, struktogrammal.

Második példaként vegyük a másolás és a maximumkiválasztás összeépítését! Ebben a maximális elem értékét és az indexét is meghatározzuk. (Az előző feladat analógiájára ilyen lehet a legnagyobb abszolútértékű szám abszolútértékének meghatározása egy számsorozatból.)

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami1], RendezettE(X),

g:Valami1→Valami2

Kimenet

MAX:Egész

Előfeltétel

N≥1

Utófeltétel

1≤MAX≤N és ∀i(1≤i≤N): g(X[MAX])≥g(X[i])

Az algoritmus

Ebben a megoldásban – a maximumkiválasztás alapján – vegyük az első elemből kiszámított függvényértéket induló maximumnak, ezt hasonlítsuk a további elemekből kiszámított függvényértékekkel, és a legnagyobbat őrizzük meg!

Pszeudókód

Struktogram

Másolás_maximumkiválasztás(N,X,MAX,MAXERT):

MAX:=1; MAXERT:=g(X[1])

Ciklus I=2-től N-ig

Ha MAXERT<g(X[I]) akkor

MAXERT:=g(X[I]); MAX:=I

Elágazás vége

Ciklus vége

Eljárás vége.

Másolás + maximumkiválasztás tétel algoritmusa, struktogrammal.

Vissza a tartalomjegyzékhez

2. Megszámolással összeépítés

A megszámolást három elemi programozási tétellel érdemes egybeépíteni, az eldöntéssel, a kiválasztással, valamint a kereséssel.

Az animáció bemutatja az eldöntési tétellel való egybeépítés lehetőségeit:

Az animáció bemutatja hogy hogyan kell összeépíteni az eldöntési tételt más tételekkel.

Flash lejátszó letöltése

Tételek összeépítése az eldöntési tétellel

Itt olyan kérdéseket tehetünk fel, hogy van-e egy sorozatban legalább K db T tulajdonságú elem, adjuk meg a sorozat K-adik T tulajdonságú elemét stb.

Az általánossága miatt nézzük a megszámolás és a keresés egymásra építését! Az eldöntésnél, illetve a kiválasztásnál hasonlóan kellene eljárnunk, hiszen e két típusalgoritmus megoldásszövege része a keresés megoldásszövegének.

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami]

T:Valami→Logikai

Kimenet

VAN:Logikai, SORSZ:Egész

Előfeltétel

N>0

Utófeltétel

DB=SZUM(i=1..N, T(X[i])) 1 és VAN≡(DB≥K) és

VAN→1≤SORSZ≤N és T(X[SORSZ])

Az algoritmus

Induljunk ki a keresés megoldásából! A keresés ciklusa akkor állt le, amikor megtaláltuk az első T tulajdonságú elemet. Ezt kell kicserélni arra, hogy csak a K.-nál álljon le (ha egyáltalán van K). A ciklusmagban viszont számolnunk kell a T tulajdonságú elemeket – ahogyan azt a megszámolásnál tettük!

Pszeudókód

Struktogram

Keresés(N,X,K,VAN,SORSZ):

I:=0; DB:=0

Ciklus amíg Iés DB<K

I:=I+1

Ha T(X[I]) akkor DB:=DB+1

Ciklus vége

VAN:=(DB=K)

Ha VAN akkor SORSZ:=I

Eljárás vége.

Megszámolás + keresés tétel algoritmusa, struktogrammal.

Vissza a tartalomjegyzékhez

3. Maximumkiválasztással összeépítés

Maximumkiválasztással kapcsolatban azt a kérdést fogalmazhatjuk meg, hogy hány darab maximális értékű elem van, s hogy melyek a maximális értékű elemek.

Itt tehát a maximumkiválasztást kell egybeépíteni a megszámolással, illetve a kiválogatással.

Az a kérdés, hogy van-e egyáltalán több maximális értékű elem, egy menetben nem dönthető el, azaz a három tételt nem lehet egymásba építeni, hanem csak egymás után alkalmazni.

A korábbiakban megállapítottuk, hogy a kigyűjtéses kiválogatás mindig tartalmaz egy megszámolást, így csak a kiválogatással kell foglalkoznunk.

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami]

Kimenet

DB:Egész, Y:Tömb[1..N:Egész], MAXERT:Valami

Előfeltétel

N≥0 és RendezettE(X)

Utófeltétel

DB=SZUM(i=1..N, X[i]=MAXERT) 1 és Y∈{1..N}DB és HalmazE(Y) és

∀i,j(1≤i≤N, 1≤j≤DB): X[i]≤X[Y[i]] és

MAXERT=X[Y[1]]

Az algoritmus

Az összeépítés alapgondolata, hogy a lokális maximumok megőrzésével együtt válogassuk is ki a lokális maximumokat. Természetesen új lokális maximum megtalálásakor a korábbi kigyűjtést el kell felejteni. A kiválasztó ciklus végén a lokális maximum éppen a keresett maximumérték, tehát az éppen kigyűjtött sorszámok a maximumok sorszámai lesznek.

Pszeudókód

Struktogram

Maximumkiválogatás(N,X,DB,Y,MAXERT):

MAXERT:=X[1]; DB:=1; Y[DB]:=1

Ciklus I=2-től N-ig

Elágazás

X[I]>MAXERT esetén MAXERT:=X[I]; DB:=1; Y[DB]:=I

X[I]=MAXERT esetén DB:=DB+1; Y[DB]:=I

Elágazás vége

Ciklus vége

Eljárás vége.

Maximumkiválogatás = Kiválogatás + maximumkiválasztás tétel algoritmusa, struktogrammal.

Az animáció bemutatja a maximumkiválasztással egybeépítés lehetőségeit:

Az animáció bemutatja hogy hogyan kell összeépíteni a maximumkiválasztási tételt más tételekkel.

Flash lejátszó letöltése

Tételek összeépítése a maximumkiválasztási tétellel

Vissza a tartalomjegyzékhez

4. Kiválogatással összeépítés

Elsőként a kiválogatást a sorozatszámítással építjük egybe. Olyan feladatoknál alkalmazható ez, amikor a számítást egy sorozat T tulajdonságú elemeire kell csak elvégeznünk.

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami],

F:Valami*→Valami, T:Valami→Logikai

Kimenet

DB:Egész, Y:Tömb[1..N:Egész], S:Valami

Előfeltétel

N≥0 és DB≥0 és ∃F0{/SUB}∈Valami és

∃f:Valami x Valami→Valami és

F(X[1],...,X[N])=f(F(X[1],...,X[N-1]),X[N]) és

F()=F0{/SUB}

Utófeltétel

DB=SZUM(i=1..N, T(X[i])) 1 és Y∈{1..N}DB és HalmazE(Y) és

∀i(1≤i≤DB): T(X[Y[i]]) és

S=F(X[Y[1]],...,X[Y[DB]])

Az algoritmus

A megoldásban vegyük a sorozatszámítás algoritmusát, de a műveletet ne minden esetben végezzük el, hanem csak akkor, ha a megfelelő elem T tulajdonságú! Sokszor nincs az eredményhez szükség a DB-re, a mostani megoldásban ezt is képezzük.

Pszeudókód

Struktogram

Kiválogatás_sorozatszámítás(N,X,S,DB):

S:=F0; DB:=0

Ciklus I=1-től N-ig

Ha T(X[I]) akkor DB:=DB+1; S:=f(S,X[I])

Ciklus vége

Eljárás vége.

Kiválogatás + sorozatszámítás tétel algoritmusa, struktogrammal.

Második példánkban a kiválogatást a maximumkiválasztással építjük egybe. Tipikusan ilyen feladatok azok, amelyekben meg kell határozni egy sorozat T tulajdonságú elemeinek maximumát, minimumát.

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami], VAN:Logikai

T:Valami→Logikai

Kimenet

MAX:Egész, MAXERT:Valami

Előfeltétel

N≥0

Utófeltétel

VAN=(∃i(1≤i≤N):T(X[i]) és VAN→1≤MAX≤N és

T(X[MAX]) és MAXERT=X[MAX] és

∀i(1≤i≤N):T(X[i])→X[MAX]≥X[i]

Az algoritmus

Vegyük a megoldáshoz a maximumkiválasztás algoritmusát! Ne akkor jegyezzük fel az új elemet maximumnak, amikor az nagyobb az addigi maximumnál, hanem ennek még az is legyen a feltétele, hogy az új elem T tulajdonságú! Csupán egyetlen probléma van: semmi nem garantálja, hogy az első elem T tulajdonságú, sőt hogy egyáltalán ilyen elem lesz (amit pedig a maximumkiválasztás kihasznált).

Egyik lehetséges megoldás lenne, ha megkeresnénk az első T tulajdonságú elemet, s innen indítanánk a maximumkiválasztást. A másik – s mi ezt követjük – egy fiktív kezdőértékkel indít, s elölről vizsgálja a sorozatot. (Ha e fiktív érték marad a MAXERT-ben az azt jelenti, hogy nincs T tulajdonságú elem a sorozatban.)

Pszeudókód

Struktogram

Kiválogatás_maximumkiválasztás(N,X,VAN,MAX,MAXERT):

MAXERT:=-Ľ

Ciklus I=1-től N-ig

Ha T(X[I]) és X[I]>MAXERT akkor MAXERT:=X[I]; MAX:=I

Ciklus vége

VAN:=(MAXERTš-Ľ)

Eljárás vége.

Kiválogatás + maximumkiválasztás tétel algoritmusa, struktogrammal.

A harmadik példában a kiválogatást a másolással építjük egybe. Ezt olyan feladatoknál kell alkalmazni, ahol egy sorozat T tulajdonságú elemeit kell lemásolni, rajtuk egy függvény kiszámításával.

A specifikáció

Bemenet

N:Egész, X:Tömb[1..N:Valami1]

T:Valami1→Logikai, f:Valami1→Valami2

Kimenet

DB:Egész, Y:Tömb[1..N:Egész],

Z:Tömb[1..N:Valami2]

Előfeltétel

N≥0 és DB≥0

Utófeltétel

DB=SZUM(i=1..N, T(X[i])) 1 és Y∈{1..N}DB és HalmazE(Y) és

∀i(1≤i≤DB): T(X[Y[i]]) és

∀i(1≤i≤DB): Z[i]=f(X[Y[i]])

Az algoritmus

A megoldásban vegyük a kiválogatás kigyűjtéses algoritmusát, de ne a megfelelő elemek sorszámait gyűjtsük ki, hanem az ezen elemeken kiszámított függvényértéket!

Pszeudókód

Struktogram

Kiválogatás_másolás(N,X,DB,Z):
DB:=0

Ciklus I=1-től N-ig

Ha T(X[I]) akkor DB:=DB+1; Z[DB]:=f(X[I])

Ciklus vége

Eljárás vége.

Kiválogatás + másolás tétel algoritmusa, struktogrammal.

E fejezet algoritmusai nagyon hasonlóan alkalmazhatók szétválogatással, metszettel, unióval való egymásra építésre. A szükséges módosításokat a kiválogatás ciklusa helyett a megfelelő programozási tétel ciklusában kell elvégezni. A szétválogatás specialitása lehet, hogy az eredményeként szereplő két sorozatra különböző programozási tételeket is lehetne alkalmazni (pl. lehetne feladat a T tulajdonságú elemek maximumának és a nem T tulajdonságú elemek összegének meghatározása a feladat).

Az animáció bemutatja a kiválogatási tétellel való egybeépítés lehetőségeit:

Az animáció bemutatja hogy hogyan kell összeépíteni a kiválogatási tételt más tételekkel.

Flash lejátszó letöltése

Tételek összeépítése a kiválogatási tétellel

Vissza a tartalomjegyzékhez

Fel a lap tetejére
Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.