Egyszerűbb algoritmusminták (sorozatszámítás, eldöntés, kiválasztás, keresés, megszámolás, maximumkiválasztás)

Feladataink egy jelentős csoportjában egyetlen bemenő sorozat alapján kell meghatároznunk egy értéket eredményként.

Az elő-, illetve az utófeltételben pontosan meg kellene fogalmaznunk azt is, hogy a bemenő adatok, paraméterek értéke a megoldás során változatlan marad, ettől azonban az egyszerűbb felírás miatt – általában – eltekintünk. A pontos használat bemutatásaként – mintaként – ezen a helyen így is megadjuk. Az aposztróf jelöli a paraméterváltozó régi (azaz bemenetkori) értékét.

Ez a csoport több feladattípust tartalmaz, nézzük végig ezeket!

1. Sorozatszámítás

Kezdjük a legelső témakört néhány feladattal!

Vizsgáljuk meg, mi a közös az előbbi öt feladatban! Mindegyikben adatok valamilyen sorozatával kell foglalkoznunk, e sorozathoz kell hozzárendelnünk egyetlen értéket. Ezt az értéket egy, az egész sorozaton értelmezett függvény adja (N szám összege, M betű egymás után írása, K halmaz uniója, N szám szorzata). Ezt a függvényt azonban felbonthatjuk értékpárokon kiszámított függvények sorozatára (2 „valami” összegére, egymás után írására, uniójára, szorzatára).

A specifikáció

Az algoritmus

Így tehát minden olyan művelet szerepelhet e feladattípusban, amelyre a matematika valamilyen „egységes” jelölést használ: összeg, szorzat, unió, metszet, logikai műveletek, konkatenáció, .... Mindegyik művelet visszavezethető egy bináris műveletre, és megadható mindegyikhez egy semleges elem (nullelem) is, amelyre egy tetszőleges elemmel és vele elvégzett 2 operandusú művelet az adott elemet adja.

Variációk F-re és hozzátartozó F₀-ra:

A megoldás a nullelemre, valamint a 2 operandusú műveletre épül, a matematikában is szokásos módszer, az indukció alapján:

• 0 elemre tudjuk az eredményt: F₀,
• ha i-1 elemre tudjuk az eredményt (F^i-1), akkor i elemre (Fⁱ) a következőképpen kell kiszámítani: Fⁱ=f(F^i-1,X[i]).

Az F-re vonatkozó alábbi rekurzív definícióból:

– a korábbiak alapján, a specialitásokat figyelembe véve – így kapható az algoritmus első változata:

a bevezetésbeli jelölésekkel	a specialitások figyelembe vétele
k:=0 Ciklus amíg nem T(x) x:=i(x); k:=k+1 Ciklus vége x*:=x; hx:=f(x*) Ciklus l=1-től k-ig hx:=g(hx) Ciklus vége h:=hx	[T(x) ≡ i=0] k:=N; x:=() [i:(X[1],..X[i])→(X[1],X[i-1])] x*:=(); hx:=F [h()=F] hx:=f(hx,X) F:=hx

A „fölösleges” dolgokat kihagyva mindössze ennyi marad:

Algoritmusleíró nyelven	Struktogrammal
hx:=F0 Ciklus l=1-től N-ig hx:=f(hx,X) Ciklus vége F:=hx

Végezetül az algoritmikus nyelvünkben szokásos jelölésekkel a feladatot megoldó algoritmus:

Algoritmusleíró nyelven	Struktogrammal
Sorozatszámítás(N,X,S): S:=F0 Ciklus I=1-től N-ig S:=f(S,X[I]) Ciklus vége Eljárás vége.

Az animáció bemutat néhány feladatot, amit a sorozatszámítási tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Alkalmazzuk az általános megoldást a fejezet elején kitűzött egyes feladatokra!

F1. Egy osztály N db tanuló osztályzatának ismeretében adjuk meg az osztály átlagát! ⇒ N szám összege.

Adatok, műveletek	Algoritmus
Elemek száma: N Osztályzatok: X N db elem F, f, F0: ∑, +, 0	Összegzés(N,X,S): S:=0 Ciklus I=1-től N-ig S:=S+X[I] Ciklus vége Eljárás vége.

F2. Egy M elemű betűsorozat betűit fűzzük össze egyetlen szöveg típusú változóba! ⇒ M betű egymás után írása.

Adatok, műveletek	Algoritmus
Elemek száma: M Betűk: X M db elem F, f, F0: &, +, ""	Egymásután(M,X,SZ): SZ:="" [üres szöveg] Ciklus I=1-től M-ig SZ:=SZ+X[I] Ciklus vége Eljárás vége.

F4. Készítsünk algoritmust, amely egy autóversenyző körönkénti ideje alapján meghatározza a versenyző egy kör megtételéhez szükséges átlagidejét! ⇒ K halmaz uniója.

Adatok, műveletek	Algoritmus
Elemek száma: K Megfigyelések: X N db elem F, f, F0: U, ∪,	Unió(K,X,H): H:= [üres halmaz] Ciklus I=1-től K-ig H:=H∪X[I)] Ciklus vége Eljárás vége.

Vissza a tartalomjegyzékhez

2. Eldöntés

Az előző programozási tétel két speciális esetében az ott közölt megoldás sok felesleges lépést tartalmazhat. Ez a tétel annak a hiányosságait pótolja e speciális esetekben. Az alábbi példákban keressük meg a közös vonást (ami speciális esetét jelenti az előzőnek)!

E feladatok közös jellemzője, hogy a bemenetként megadott sorozathoz egy logikai értéket kell rendelni: a feltett kérdésre igen vagy nem választ adhatunk. A vizsgált sorozat elemei tetszőlegesek lehetnek, egyetlen jellemzőt kell feltételeznünk róluk: egy tetszőleges elemről el lehet dönteni, hogy rendelkezik-e egy bizonyos tulajdonsággal.

A feladatok így két csoportba sorolhatók, az egyikben azt kell eldönteni, hogy egy sorozatban létezik-e adott tulajdonságú elem, a másikban pedig azt, hogy mindegyik elemre jellemző-e ez a tulajdonság. Vizsgáljuk először az elsőfajtájúakat!

A specifikáció

Az algoritmus

A feladattípus megoldására az előző programozási tétel is alkalmas a következő megfeleltetéssel: F = ∨ (sokváltozós), f = ∨ (kétváltozós), F₀ = hamis.

Észrevehetünk azonban egy fontos tulajdonságot. Ha a megoldásban az S változó értéke egyszer igazra változik, akkor a megoldás végéig biztosan az is marad. Tehát az ez utáni műveletek elvégzése teljesen felesleges. Ezt a tulajdonságot kihasználva készíthetjük el az igazi megoldást.

Ebben az esetben egy olyan ciklus a megoldás, amely vagy akkor áll le, ha találtunk egy, a keresett tulajdonságú elemet, vagy pedig akkor, ha ilyen elem a sorozatban már nem létezhet, azaz elfogytak a megvizsgálandó elemek.

Algoritmusleíró nyelven	Struktogram
Eldöntés(N,X,VAN): I:=1 Ciklus amíg I≤N és nem T(X[I]) I:=I+1 Ciklus vége VAN:=(I≤N) Eljárás vége.

Fordítsuk most figyelmünket a másik csoportra! Azt, hogy mindegyik elem sajátossága egy adott tulajdonság, átfogalmazhatjuk arra, hogy nem létezik az adott tulajdonsággal nem rendelkező elem. Ezek alapján a fenti megoldásban két helyen tagadást alkalmazva megkapjuk ennek a csoportnak a megoldástípusát is. (Ez a sorozatszámítás az F = ∧ (sokváltozós), f = ∧ (kétváltozós), F₀ = igaz értékekkel).

Algoritmusleíró nyelven	Struktogram
Eldöntés(N,X,MIND): I:=1 Ciklus amíg I≤N és T(X[I]) I:=I+1 Ciklus vége MIND:=(I>N) Eljárás vége.

Az eldöntés tipikusan olyan feladat, amelynél kódolási problémák merülhetnek fel. Ilyenekkel foglalkozunk az algoritmusok kódolásával kapcsolatos,

A programozási nyelvek egy jelentős részében a logikai kifejezések kiértékelésekor az és, illetve a vagy műveletek mindkét operandusát kiértékelik futáskor, még akkor is, ha az egyik operandus értéke alapján a végeredmény egyértelműen eldönthető lenne. E programozási tételnél így az I≤N feltétel nem teljesülése esetén is meg kell vizsgálni a T(X[I]) értékét. Ha a felhasznált tömb pontosan N elemű, akkor ez tömbindexelési hibához vezet. Többféle megoldással élhetünk a kódolás során:

• vegyünk fel egy fiktív (N+1)-dik elemet a tömb végére;
• a ciklus egy lépéssel hamarabb álljon le, és vizsgáljuk a leállás okát;
• válasszuk szét a két részfeltétel kiértékelését, és a T(X[I])-t csak akkor értékeljük ki, amikor szükséges.

Az animáció bemutat néhány feladatot, amit eldöntési tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Néhány feladat megoldása következik.

F6. Döntsük el egy számról, hogy prímszám-e! ⇔ Létezik-e a számnak 1-től és önmagától különböző osztója?

Adatok, műveletek	Algoritmus
Elemek száma: N-2 Osztók: 2,3, ..., N-1 T(e)=T'(e,N): e|N (T'(e,N) : a valódi függést kifejező leképezés)	Eldöntés(N,PRIM): I:=2 Ciklus amíg I≤N-1 és nem I|N I:=I+1 Ciklus vége PRIM:=(I>N-1) Eljárás vége.

F9. Júniusban minden nap délben megmértük, hogy a Balaton Siófoknál hány fokos. Döntsük el a mérések alapján, hogy a víz hőfoka folyamatosan emelkedett-e! ⇔ A hőmérsékletek sorozata monoton növekedő-e?

Adatok, műveletek	Algoritmus
Elemek száma: N-1 Hőmérsékletek: X N db elem T(X[e])=T'(e): X[e]≤X[e+1] (T'(e) : a valódi függést kifejező leképezés)	Eldöntés(N,X,MONOTON): I:=1 Ciklus amíg I≤N-1 és X[I]≤X[I+1] I:=I+1 Ciklus vége MONOTON:=(I>N-1) Eljárás vége.

Vissza a tartalomjegyzékhez

3. Kiválasztás

Ha kicsit belegondolunk, az előző programozási tétel megoldása a tőle vártnál több eredményt is adhat. Ennél a tételnél ezt a többet vizsgáljuk.

Keressük itt is a közös jellemzőket! A feladattípus első ránézésre nagyon hasonlít az előzőre, csupán itt nem egy eldöntendő kérdésre kell válaszolni, hanem meg kell adni a sorozat egyik, adott tulajdonságú elemét. Kicsit részletesebb, pontosabb vizsgálódás után még az is kiderül, hogy ha e feladatokra az eldöntendő kérdést tennénk fel, akkor biztosan igen választ kapnánk.

Azt kell még eldöntenünk, hogy az elemet hogyan adhatjuk meg. Erre két lehetőségünk van: vagy a sorszámát, vagy pedig az értékét adjuk meg. Felhívjuk a figyelmet arra, hogy az előbbi változatból az utóbbi megoldását nagyon könnyen megkaphatjuk, fordítva viszont korántsem ez a helyzet. Emiatt mi az első változatot részesítjük előnyben, ez az általánosabb eset.

A specifikáció

Az algoritmus

A megoldás sokban fog hasonlítani az előző feladattípus megoldásához, annak az esetnek a vizsgálatát kell kihagyni belőle, amely a keresett tulajdonságú elem nem létezése esetén állította le a megoldás keresését.

Algoritmusleíró nyelven	Struktogram
Kiválasztás(N,X,SORSZ): I:=1 Ciklus amíg nem T(X[I]) I:=I+1 Ciklus vége SORSZ:=I Eljárás vége.

A megoldásról könnyen megállapíthatjuk, hogy ha több, a kívánt tulajdonságú elem is előfordul a sorozatban, akkor azok közül az elsőt (helyesebben annak sorszámát) adja.

A program utófeltétele lehet szigorúbb, mint a feladatbeli utófeltétel. Itt ez a következőképpen néz ki:

Könnyen átalakíthatjuk olyanra is, amely ilyenkor az utolsót adja közülük. Ekkor csupán annyi a teendő, hogy a sorozat elemeit hátulról visszafelé dolgozzuk fel.

Az animáció bemutat néhány feladatot, amit a kiválasztási tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Nézzük meg a bevezető feladatok egyikének megoldását!

F12. A naptárban található névnapok alapján adjuk meg legjobb barátunk (barátnőnk) névnapját! (Itt nem a „legjobbság” megfogalmazása okozza az algoritmikai problémát.) ⇒ Ki a legjobb barát (barátnő) ⇒ Mi a névnapja?

Adatok, műveletek	Algoritmus
Elemek száma: N Névnapok: X N db elem; Rekord(név,névnap) T(e): e.név=BARÁT	Kiválasztás(N,X,BARÁT,NAP): I:=1 Ciklus amíg X[I].név≠BARÁT I:=I+1 Ciklus vége NAP:=X[I].névnap Eljárás vége.

Vissza a tartalomjegyzékhez

4. (Lineáris) keresés

Foglaljuk össze az előző két programozási tétel feladatát: az új feladattípusban a feltett kérdés az előző kettő mindegyikét tartalmazza!

Tehát a közös jellemző, hogy egy adott tulajdonságú elemet kell megadnunk, ha egyáltalán van ilyen. Ha nincs, akkor a válasznak ezt a tényt kell tartalmaznia.

A specifikáció

Az algoritmus

Vegyük az eldöntés algoritmusát, és egészítsük ki a kiválasztás megfelelő eredményével!

Algoritmusleíró nyelven	Struktogram
Keresés(N,X,VAN,SORSZ): I:=1 Ciklus amíg I≤N és nem T(X[I]) I:=I+1 Ciklus vége VAN:=(I≤N) Ha VAN akkor SORSZ:=I Eljárás vége.

Az animáció bemutat néhány feladatot, amit a keresési tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Az egyik kitűzött feladat megoldása a következő lehet:

F13. Ismerjük egy üzlet egy havi forgalmát: minden napra megadjuk, hogy mennyi volt a bevétel és mennyi a kiadás. Adjunk meg egy olyan napot – ha van –, amelyik nem volt nyereséges! ⇒ A nem nyereséges nap megadása.

Adatok, műveletek	Algoritmus
Elemek száma: N Bevételek: B N db elem Kiadások: K N db elem T(k-b): k-b≥0	Keresés(N,X,VAN,NAP): I:=1 Ciklus amíg I≤N és K[I]-B[I]<0 I:=I+1 Ciklus vége VAN:=(IN) Ha VAN akkor NAP:=I Eljárás vége.

Vissza a tartalomjegyzékhez

5. Megszámolás

Az előző feladatokban előfordulhatott, hogy több elemre is jellemző a vizsgált tulajdonság. Ekkor érdekes lehet annak megvizsgálása, hogy hány ilyen elem van.

A közös jellemző itt tehát a számlálás. Vegyük észre, hogy a feladatot sorozatszámításként is felfoghatjuk, amelyben 1-eseket kell összeadnunk, de bizonyos feltételtől függően!

A specifikáció

Az algoritmus

A feladat sorozatszámítás (sőt összegzés), tehát egy ciklust kell alkalmazni a megoldáshoz. A ciklus belsejében egy unió jellegű (0/1 értékű) adatot kell feldolgozni, ezt egy elágazással tehetjük meg.

Algoritmusleíró nyelven	Struktogram
Megszámolás(N,X,DB): DB:=0 Ciklus I=1-től N-ig Ha T(X[I]) akkor DB:=DB+1 Ciklus vége Eljárás vége

Az animáció bemutat néhány feladatot, amit a megszámolási tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Nézzük meg két feladat megoldását!

F16. Családok létszámának, illetve jövedelmének alapján állapítsuk meg, hogy hány család él a létminimum alatt! ⇒

Minden családi létszámhoz megadható az a jövedelem, amely a létminimumhoz kell, a megoldásban ezt használjuk fel.

Adatok, műveletek	Algoritmus
Elemek száma: N Létszámok: L N db elem Jövedelmek: J N db elem Létminimumok: MIN sorozat T(l,j)=j-MIN(l)≥0	Megszámolás(N,J,L,DB): DB:=0 Ciklus I=1-től N-ig Ha J[I]≤MIN[L[I]] akkor DB:=DB+1 Ciklus vége Eljárás vége.

F17. Egy futóverseny végeredménye határozzuk meg, hogy a versenyzők hány százaléka teljesítette az olimpiai induláshoz szükséges szintet! ⇒ Mennyien teljesítették az indulási szintet? ⇒ Hány százalék?

A feladat megoldása egy megszámolás, majd az eredményből és a résztvevők számából százalékot számolunk.

Adatok, műveletek	Algoritmus
Elemek száma: N Idők: ID N db elem T(id): id≤SZINT	Megszámolás(N,ID,SZAZ): DB:=0 Ciklus I=1-től N-ig Ha ID[I]≤SZINT akkor DB:=DB+1 Ciklus vége SZAZ:=Kerekít(100*DB/N) Eljárás vége.

Vissza a tartalomjegyzékhez

6. Maximumkiválasztás

A sorozatszámítás egy újabb speciális esetével ismerkedünk meg a következő feladattípusban, először néhány feladaton keresztül.

Közös jellemzőjük e feladatoknak, hogy minden esetben egy sorozat elemei közül kell kiválasztani a legnagyobbat (ill. a legkisebbet). Itt is meggondolandó – mint a kiválasztásnál –, hogy elem értéket vagy pedig elem sorszámot várunk eredményként. Az ottani gondolatmenethez hasonlóan most is a sorszám meghatározását választjuk.

A specifikáció

Az algoritmus

Vezessük vissza a sorozatszámítás tételre! A sorozatszámításbeli F függvényként a MAX(A[1],A[2],…,A[N]) függvényt használjuk! Az ehhez kapcsolódó f függvényt a következőképpen értelmezzük:

f(x,y):=max(x,y).

Legyen ehhez F₀:=A[1]! A választás megengedhető, annak ellenére, hogy nem feltétlenül lesz az A[1] neutrális (nullelem) a max műveletre nézve! A korrekt választás ugyanis a H minimum eleme lenne, ami vagy ismert, vagy nem. Egy tetszőleges A-beli elem neutrálisnak akkor fog tűnni, ha a max operátor értelmezési tartományát leszűkítjük a H azon részhalmazára, amely az adott elemnél nem kisebb értékű elemeket tartalmazza. Ennek is eleme lesz garantáltan a sorozat maximális eleme. Tehát hibát nem követünk el, ha F₀-nak az A[1]-et tekintjük.

Alakítsuk át úgy a sorozatszámítás megoldását, hogy ne értéket, hanem sorszámot kapjunk eredményül! (Annyi észrevennivalónk van csak az algoritmizáláskor, hogy most a sorozat feldolgozása a 2. elemmel kezdődhet, hiszen az első értékét már F₀ gyanánt figyelembe vettük. Továbbá, hogy a max függvényt egy elágazással valósíthatjuk meg.)

Algoritmusleíró nyelven	Struktogram
Maximumkiválasztás(N,X,MAX): MAX:=1 Ciklus I=2-től N-ig Ha X[MAX]<X[I] akkor MAX:=I Ciklus vége Eljárás vége.

Sok esetben túlságosan sok időbe kerül a sorozat egy elemének meghatározása (az sorszáma ismeretében). Ekkor olyan megoldást készíthetünk, amely a maximális értéket határozza meg, vagy pedig a sorszámot is és az értéket is.

Algoritmusleíró nyelven	Struktogram
Maximumkiválasztás (N,X,MAX,MAXERT): MAX:=1; MAXERT:=X[1] Ciklus I=2-től N-ig Ha MAXERT<X[I] akkor MAX:=I MAXERT:=X[I] Elágazás vége Ciklus vége Eljárás vége.

Ha a feladat minimumkiválasztás, akkor pedig nincs más teendőnk, mint az elágazás feltételében szereplő < reláció átírása >-ra. Erre példa az egyik kitűzött feladat megoldása.

F21. Egy osztály tanulói nevei alapján adjuk meg a névsorban legelső tanulót! ⇒ Ki a legelső, a névsorszerint?

Adatok, műveletek	Algoritmus
Elemek száma: N Tanulók neve: X N db elem	Minimum(N,X,MIN,NEV): MIN:=1; NEV:=X[1] Ciklus I=2-től N-ig Ha NEV>X[I] akkor MIN:=I; NEV:=X[I] Ciklus vége Eljárás vége.

Az animáció bemutat néhány feladatot, amit a maximumkiválasztás tétellel oldhatunk meg, és megfogalmazza az absztrakt tételt is:

Vissza a tartalomjegyzékhez