Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a modul kezdőlapjáraUgrás a tananyag előző oldaláraUgrás a tananyag következő oldalára (teszt)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

A programozási feladatok megoldásánál érdemes felhasználni a rendelkezésre álló algoritmusmintákat, tételeket. A tételek közül ebben a leckében azokat vesszük sorra, amelyek egy bemenő sorozathoz egy elemi értéket rendelnek kimenetként. Az egyes tételek kimondása mellett minden esetben az azzal az algoritmusmintával megoldható néhány feladatot is megadunk. A következő programozási tételekről lesz szó: sorozatszámítás (speciális esetben: összegzés), eldöntés, kiválasztás, keresés, megszámolás és maximumkiválasztás.

Követelmény

Önállóan megoldható feladatok

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.

Bemenet

N:Egész, X:Tömb[1..N:H], F:H*→G ← az állapottér bemeneti komponensei

Kimenet

S:G ← az állapottér kimeneti komponense(i)

Előfeltétel

N≥0

Utófeltétel

S=F(X[1],…,X[N]) ← az utófeltétel azt adja meg, megálláskor milyen tulajdonsággal

rendelkezik a program. (Most S éppen az adott értékű lesz.)

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.

Bemenet

N:Egész, X:Tömb[1..N:H], F:H*→G

Kimenet

S:G

Előfeltétel

N≥0

Utófeltétel

S=F(X[1],…,X[N]) és N=N’ és X=X’

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!

Feladat

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

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

F3. 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!

F4. A Balaton mentén K db madarász végzett megfigyeléseket. Mindegyik megadta, hogy milyen madarakat látott. Készítsünk algoritmust, amely megadja a megfigyelések alapján a Balatonon előforduló madárfajokat!

F5. Adjuk meg az első N természetes szám szorzatát (N faktoriális)!

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], F:H*→G

Kimenet

S:G

Előfeltétel

N≥0 és

∃F0∈G (nullelem) és ∃f:GxH→G és

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

F()=F0

Utófeltétel

S=F(X[1],…,X[N]) és N=N’ és X=X’

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ó F0-ra:

F

F0

∑ (szumma = számsorozat összege)

0

∏ (produktum = számsorozat szorzata)

1

∪ (unió = halmazsorozat egyesítése)

{ } vagy ∅

∩ (metszet = halmazsorozat metszete)

alaphalmaz

∨ (vagy = logikai értékek sorozatának az „összege”)

Hamis

∧ (és = logikai értékek sorozatának a „szorzata”)

Igaz

& (konkatenáció = szövegek „egymásutánírása”)

""

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:

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

Az i-edik elem kiszámításának képlete látható.

– 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 képen a sorozatszámítás algoritmusának egyszerűsített változata látható struktogrammal megadva.

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

A képen a sorozatszámítás algoritmusának első változata látható struktogrammal megadva.

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.

A képen a sorozatszámítás struktogramjának általunk használt változata látható.

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:

Az animáció a sorozatszámítási tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Sorozatszámítási tétel

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.

A képen egy sorozat elemeinek összegzése struktogramját láthatjuk.

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.

A képen egy sorozat elemeinek unióját leíró struktogramot láthatjuk.

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.

A képen egy sorozat elemeinek konkatenációját leíró struktogramot láthatjuk.

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)!

Feladat

F6. Döntsük el egy számról, hogy prímszám-e!

F7. Döntsük el egy szóról a hónapnevek sorozata alapján, hogy egy hónap neve-e!

F8. Döntsük el egy tanuló év végi osztályzatai alapján, hogy kitűnő tanuló-e!

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!

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], T:H→Logikai

Kimenet

VAN:Logikai

Előfeltétel

N≥0

Utófeltétel

VAN=(∃i(1≤i≤N): T(X[i]))

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), F0 = hamis.

A képen az eldöntési tétel struktogramjának a sorozatszámítási tételből levezetett  változata látható.

É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.

A képen az eldöntési tétel struktogramja látható.

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), F0 = 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.

A képen az eldöntési tétel struktogramja látható, amely azt mutatja meg, hogy minden elem adott tulajdonságú-e.

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:

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

Az animáció az eldöntési tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Eldöntési tétel

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.

A képen az eldöntési tétel alkalmazása prímszám meghatározására szerepel.

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.

A képen egy sorozat monotonitásának meghatározására szolgáló struktogram látható.

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.

Feladat

F10. Ismerjük egy hónap nevét, a hónapnevek sorozata alapján mondjuk meg a sorszámát!

F11. Adjuk meg egy természetes szám legkisebb, 1-től különböző osztójá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.)

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], T:H→Logikai

Kimenet

SORSZ:Egész

Előfeltétel

N≥1 és ∃i(1≤i≤N): T(X[i])

Utófeltétel

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

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 képen egy sorozat elemeiből adott tulajdonságút kiválasztására szolgáló struktogram látható.

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:

Utófeltétel

1≤SORSZ≤N és T(X[SORSZ]) és ∀i(1≤i<SORSZ): nem T(X[i]))

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:

Az animáció a kiválasztási tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Kiválasztási tétel

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.

A képen a barát névnapja feladat megoldásának strugtogramját láthatjuk.

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!

Feladat

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!

F14. A Budapest–Nagykanizsa vasúti menetrend alapján két adott állomáshoz adjunk meg egy olyan vonatot, amellyel el lehet jutni átszállás nélkül az egyikről a másikra!

F15. Egy tetszőleges (nem 1) természetes számnak adjuk meg egy osztóját, ami nem az 1 és nem is önmaga.

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], T:H→Logikai

Kimenet

VAN:Logikai, SORSZ:Egész

Előfeltétel

N≥0

Utófeltétel

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

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

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.

A képen a keresési tételt megvalósító struktogramot láthatjuk.

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

Az animáció a keresési tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Keresési tétel

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.

A képen a nem nyereséges nap feladatot megoldó struktogram látható. .

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.

Feladat

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!

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!

F18. Adjuk meg egy szöveg magánhangzóinak számát!

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], T:H→Logikai

Kimenet

DB:Egész

Előfeltétel

N≥0

Utófeltétel

DB=SZUM(i=1..N;T(X[i])) 1

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

A képen a megszámolási tétel struktogramja látható.

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

Az animáció a megszámolási tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Megszámolási tétel

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.

A képen a

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.

A képen a

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.

Feladat

F19. Egy kórházban megmérték minden beteg lázát, adjuk meg, hogy ki a leglázasabb!

F20. Egy család havi bevételei és kiadásai alapján adjuk meg, hogy melyik hónapban tudtak a legtöbbet megtakarítani!

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

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ó

Bemenet

N:Egész, X:Tömb[1..N:H], H rendezett elemtípus (∃<,≤ rendezési relációk)

Kimenet

MAX:Egész

Előfeltétel

N≥1

Utófeltétel

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

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 F0:=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 F0-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 F0 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.

A képen a maximumkiválasztási tétel struktogramja látható.

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.

A képen a maximumkiválasztási tétel egy változatának struktogramja látható.

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.

A képen a minimumkiválasztási feladatot megoldó struktogram látható.

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

Az animáció a maximumkiválasztási tételt tárgyalja konkrét feladatokon keresztül és megfogalmazza annak absztrakt változatát is.

Flash lejátszó letöltése

Maximumkiválasztási tétel

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.