Algoritmusminták együttes alkalmazása – programozási tételek egymásra építése; feltételes maximum, K-adik adott tulajdonságú elem.
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:
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!
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]))
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á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.)
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])
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. |
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.
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.
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])
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 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. |
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.
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 ö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. |
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.
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.
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]])
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. |
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.
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]
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. |
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.
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]])
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): 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. |
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.