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 (19)Ugrá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

Az ún. összetett programozási tételekkel ismerkedhetünk meg ebben a fejezetben. Az „összetett” jelző arra utal, hogy a szóba kerülő tételekben több sorozat is szerepet kap. Lesznek olyanok, amelyek bemenetén van egynél több, és lesz olyan, amelyiknél a kimeneten keletkezik több.

Követelmény

Önállóan megoldható feladatok

Összetettebb algoritmusminták (másolás, kiválogatás, szétválogatás, metszet, egyesítés, összefuttatás)

A soron következő feladattípusokban már a bemeneti és a kimeneti oldalon is egy-egy sorozat jelenik meg, majd a későbbiekben valamelyiket több sorozattal helyettesítjük.

1. Másolás

Ezt a feladattípust is konkrét példákkal kezdjük, mint tettük azt az elemi tételekkel foglalkozó leckében.

Feladat

F22. Egy osztály tanulóinak átlageredménye alapján határozzuk meg, hogy bizonyítványukba jeles, jó, közepes vagy elégséges kerül-e! Tegyük fel, hogy bukott tanuló nincs!

F23. Egy szöveg minden magánhangzóját cseréljük ki az e betűre!

E feladatok közös jellemzője, hogy az eredmény mindig ugyanannyi elemszámú, mint a bemenet volt, és az i. tagját a bemenet i. tagjából lehet meghatározni. Tehát a bemenő sorozatot le kell másolni, és közben egy – elemre vonatkozó – átalakítást lehet végezni rajta. (Gyakran e tulajdonságot hívják elemenkénti feldolgozhatóságnak.)

Specifikáció

Bemenet

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

Kimenet

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

Előfeltétel

N≥0

Utófeltétel

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

Algoritmus

Egy ilyen feladat esetén először is szükség van egy olyan függvény definiálására, amely a bemeneti sorozat egy-egy eleméből a kimeneti sorozat egy-egy elemét előállítja. Pontosabban:

Függvény:

f:Valami1→Valami2

Megjegyzés

Ennek a programozási tételnek a másik nevét: függvényszámítás tétel, ezután már világosan értjük. A fenti függvénynek különlegesen fontos, – mondhatjuk – központi szerep jut a tételben. Az eredeti névhez, a másoláshoz hű feladat esetén e függvényt egy nagyon speciális függvény testesíti meg: az identikus.

A bemenő sorozatból az eredmény elemenként kiszámítható, így nagyon egyszerű megoldást kapunk.

Mondatszerű leírás

Struktogram

Másolás(N,X,Y):
Ciklus I=1-től N-ig
Y[I]:=f(X[I])
Ciklus vége
Eljárás vége.

A másolás tétel algoritmusa, struktogrammal.

Egy példa megoldása

Feladat

F23. Magánhangzó-cserélés.

A specifikációbeli fogalmak aktualizálása:

elemek száma: N

bemeneti tömb: X N db karakter

kimeneti tömb: Y N db karakter

f(x): ’e’,ha magán(x), különben x

Ahol a magán függvényt definiáltnak vesszük, és igaz értéket rendel a paraméterül adott karakterhez akkor, ha az magánhangzó.

Mondatszerű leírás

Struktogram

Másolás(N,X,Y):
Ciklus I=1-től N-ig
Ha magán(X[I])
akkor Y[I]:=’e’
különben Y[I]:=X[I]
Ciklus vége
Eljárás vége.

A magánhangzó 'e'-re cserélése feladat struktogramja.

Az animáció bemutatja a másolás tételt és használatát:

Az animáció bemutatja a másolás tételt és használatát.

Flash lejátszó letöltése

Másolás tétel

Vissza a tartalomjegyzékhez

2. Kiválogatás

Nem minden esetben kell lemásolni a teljes bemenő sorozatot, hanem annak csupán egy részére kell korlátozni a vizsgálatot. Legegyszerűbb esetben a „vizsgálat” mindössze elemmásolás. Ilyen feladatok szerepelnek ebben a fejezetben.

Feladat

F24. Egy személyzeti nyilvántartásban emberek neve és személyi száma szerepel. Adjuk meg a 20 évesnél fiatalabb lányokat!

F25. Adjuk meg egy természetes szám összes osztóját!

F26. Adjuk meg egy osztály azon tanulóit, akik jeles átlagúak!

A feladat részben a keresésre hasonlít, részben pedig a megszámlálásra. Adott tulajdonságú elemet kell megadni, de nem egyet, hanem mindegyiket; illetve nem(csak) megszámolni kell az adott tulajdonságú elemeket, hanem megadni.

Az eredmény tárolásához egy új tömböt használunk, amelynek elemszámát előre sajnos nem tudjuk megállapítani, csupán egy felső korlátot ismerünk: a lehetséges elemek számát.

Kiválogatás kigyűjtéssel

Többféle megoldást készíthetnénk a feladatra. Az első változatban a keresett elemek sorszámait gyűjtjük ki egy vektorba. A megoldás hasonlít a megszámolásra, csupán a számolás mellett még az elemek sorszámait is feljegyezzük. Éppen ezért e változat neve: kiválogatás kigyűjtéssel.

Specifikáció – kiválogatás kigyűjtéssel

Bemenet

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

Kimenet

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

Előfeltétel

N≥0

Utófeltétel

Db=SZUM(i=1..N;T(X[i])) 1 és

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

Y⊆(1,2,...,N)

Algoritmus – kiválogatás kigyűjtéssel

A tulajdonság-függvény a szokásos szignatúrájú:

Függvény:

T:Valami→Logikai

Mondatszerű leírás

Struktogram

Kiválogatás(N,X,Db,Y):
Db:=0
Ciklus I=1-től N-ig
Ha T(X[I]) akkor Db:=Db+1; Y[Db]:=I
Ciklus vége
Eljárás vége.

A kiválogatás tétel algoritmusa, struktogrammal.
Megjegyzés

Minimális változtatásra lenne szükség, ha nem a sorszámokat, hanem magukat az elemeket kellene kigyűjteni. Az Y[Db]:=I értékadás helyett az Y[Db]:=X[I] kell, érdemes a specifikáció átalakulását is meggondolni:

Utófeltétel

Db=SZUM(i=1..N;T(X[i])) 1 és

Y⊆X és

∀i(1≤i≤Db): T(Y[i])

Kiválogatás kiírással

A második változat, a kiválogatás kiírással még ennél is egyszerűbb, ebben nincs szükség számolásra, a megtalált elemet azonnal kiírhatjuk. Ez természetesen csak akkor alkalmazható, ha a kiválogatott elemekre további feldolgozás miatt nincs szükség.

Algoritmus – kiválogatás kiírással

Mondatszerű leírás

Struktogram

Kiválogatás(N,X):
Ciklus I=1-től N-ig
Ha T(X[I]) akkor Ki:X[I]
Ciklus vége
Eljárás vége.

A kiválogatás tétel 'kiírással' változatásnak algoritmusa, struktogrammal.

Kiválogatás helyben

A harmadik változatban az elemeket gyűjtjük ki, de – feltételezve, hogy az eredeti sorozatra már nincs szükség – ezeket az eredeti vektorban hagyjuk; ez lesz a kiválogatás helyben.

Feladat

Fogalmazza meg a feladat specifikációját!

Problémák, amikre választ kell adnia:

1.) Hogyan fogalmazható meg, hogy a kimeneti tömb azonos a bemenetivel?

2.) Kell-e törődnie a kihagyottakkal, vagy elegendő a megmaradt T-tulajdonságúakkal?

Algoritmus – kiválogatás helyben

Mondatszerű leírás

Struktogram

Kiválogatás(N,X,Db):
Db:=0
Ciklus I=1-től N-ig
Ha T(X[I]) akkor Db:=Db+1; X[Db]:=X[I]
Ciklus vége
Eljárás vége.

A kiválogatás tétel 'helyben' változatásnak algoritmusa, struktogrammal.

Kiválogatás kihúzással

Az utolsó változatban sem lesz szükség a kihagyott elemekre, de a megmaradtakat sem akarjuk mozgatni. Emiatt a felesleges elemek helyére egy speciális értéket teszünk, ezzel jelölve a kihagyásukat. Természetesen e megoldás akkor célszerű, ha a későbbi feldolgozások során e speciális érték vizsgálata jóval egyszerűbb, mint maga a kiválogatás volt. E módszer neve: kiválogatás kihúzással.

Feladat

Írja meg a feladat specifikációját!

Hogy fogalmazható meg az, hogy egy elem „ki van húzva”?

Algoritmus – kiválogatás kihúzással

Mondatszerű leírás

Struktogram

Kiválogatás(N,X):
Ciklus I=1-től N-ig
Ha nem T(X[I]) akkor X[I]:=spec. érték
Ciklus vége
Eljárás vége.

A kiválogatás tétel 'helyben' változatásnak algoritmusa, struktogrammal.

Egy példa megoldása

Feladat

F26. Jeles átlagú tanulók neve.

A specifikációbeli fogalmak aktualizálása:

bemeneti elemek száma: N

bemeneti tömb: Tanulók N db elem, ahol az elem=Rekord(név,átl)

kimeneti elemek száma: Db

kimeneti tömb: Nevek Db név (jeles tanuló neve), Db a jelesek száma;

maximum: N lehet (ezt a deklaráció miatt fontos tisztázni!)

T(x): JelesE(x):=x>4,5 (azaz igaz, ha a paraméterül adott átlag jeles)

A specifikációban egyetlen szokatlan dolgot vehetünk észre: nem az indexeket, hanem a neveket kell felsorolni a kimeneti tömbben. Ez azt jelenti, hogy az utófeltételben az indexek egyértelműsége helyett a nevek egyértelműségét kell kifejezni. Ezt persze garantálni csak akkor lehet, ha minden név különböző, ami miatt bonyolítanunk kell az előfeltételt. Ezek után a specifikáció ennyi:

Bemenet

N:Egész, Tanulók:Tömb[1..N:elem],

ahol elem=Rekord(név:Szöveg,átl:Valós)

Kimenet

Db:Egész, Nevek:Tömb[1..N:Szöveg]

Előfeltétel

N≥0 és ∀i≠j(1≤i,j≤N): Tanulók[i].név≠Tanulók[j].név

Utófeltétel

Db=SZUM(i=1..N;JelesE(Tanuló[i].átl) 1 és

∀i(1≤i≤Db): JelesE(Tanulók[i].név) és

Nevek⊆Tanulók.név

Definíció

JelesE:Valós→Logikai

JelesE(x):=x>4,5

Feladat

Próbálja folytatni az előbbi mintát követve! Melyik algoritmusmintát, milyen behelyettesítésekkel kell alkalmazni?

Az animáció bemutatja a kiválogatás tételt és használatát:

Az animáció bemutatja a kiválogatás tételt és használatát.

Flash lejátszó letöltése

Kiválogatás tétel

Vissza a tartalomjegyzékhez

3. Szétválogatás

Feltehető az előző fejezetbeli feladattípussal kapcsolatban az a kérdés, hogy mi lesz a ki nem válogatott elemekkel. Ebben a fejezetben erre a kérdésre adunk választ.

Feladat

F27. Adott N db természetes szám, válogassuk szét a párosakat és a páratlanokat!

F28. Az osztály tanulóit névsoruk alapján válogassuk szét lányokra, illetve fiúkra!

F29. Az osztály tanulói félévi átlageredményük alapján válogassuk szét jelesekre, jókra, közepesekre, elégségesekre, valamint elégtelenekre!

Ez egy új feladattípus-osztály első tagja: itt egy sorozathoz több sorozatot kell rendelni.

A feladatok mindegyike megfogalmazható úgy, hogy végezzünk el egymás után valahány kiválogatást. Az első két feladatban pontosan kettőről van szó, az utolsóban többről, de ez utóbbi megoldható úgy, hogy először válogassuk szét jelesekre és a többiekre, majd a többieket jókra és... Ezek alapján megállapítható, hogy a szétválogatást elég megfogalmazni két sorozatra, és ha többről van szó, akkor egyszerűen csak többször kell alkalmazni.

A kétfelé szétválogatást azonban felesleges két kiválogatással megoldani, ugyanis egyértelmű, hogy amit az első menetben nem válogattunk ki, pontosan azok fognak szerepelni a másodikban.

Az első változatban a kétféle elemet két vektorba válogatjuk szét, ezek elemszáma sajnos mindkét esetben az eredeti vektor elemszáma kell legyen, ugyanis elképzelhető, hogy az összes elemet az egyik vektorba kell majd elhelyezni.

Specifikáció

Bemenet

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

Kimenet

Db:Egész, Y,Z:Tömb[1..N:Valami]

Előfeltétel

N≥0

Utófeltétel

Db=SZUM(i=1..N; T(X[i])) 1 és

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

∀i(1≤i≤N-Db): nem T(Z[i]) és

Y⊆X és Z⊆X

Nézzük tehát a szétválogatást két tömbbe!

Algoritmus

Függvény:

T:Valami→Logikai

Mondatszerű leírás

Struktogram

Szétválogatás(N,X,Y,Db,Z,DbZ):

Db:=0; DbZ:=0

Ciklus I=1-től N-ig

Ha T(X[I]) akkor Db:=Db+1; Y[Db]:=X[I]

különben DbZ:=DbZ+1; Z[DbZ]:=X[I]

Ciklus vége

Eljárás vége.

A szétválogatás tétel algoritmusa, struktogrammal.

Világos, hogy a két vektor alkalmazásával sok felesleges helyet használunk, hiszen 2*N helyet foglalunk, pedig összesen csak N-re van szükségünk.

Ha az elemeket egyetlen tömbbe helyezzük el, mégpedig úgy, hogy a T tulajdonságúakat a tömb elejétől, a nem T tulajdonságúakat pedig a végétől kezdve helyezzük el, akkor N helyet megtakaríthatunk. Ez lesz a szétválogatás egy tömbbe.

Mondatszerű leírás

Struktogram

Szétválogatás(N,X,Y,Db,Z,DbZ):

Db:=0; IndZ:=N+1

Ciklus I=1-től N-ig

Ha T(X[I]) akkor Db:=Db+1; Y[Db]:=X[I]

különben IndZ:=IndZ-1; Y[IndZ]:=X[I]

Ciklus vége

Eljárás vége.

A szétválogatás tétel 'egy tömbös' változatának algoritmusa, struktogrammal.

Vegyük észre, hogy ebben a megoldásban a nem T tulajdonságú elemek sorrendje az eredetihez képest éppen megfordul.

A kiválogatáshoz hasonlóan itt is megoldhatjuk a helyben szétválogatást is, ha nincs szükség az elemek eredeti sorrendjére. Ehhez az utófeltételt módosítani kell.

Utófeltétel

Db=SZUM(i=1..N;T(X[i]) 1 és

X’∈Permutáció(X) és

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

∀i(Db<i≤N): nem T(X[i])

Egyszerű lenne a következő algoritmus: Elindulunk a tömbben elölről és hátulról, s keresünk olyan elemeket, amelyeket fel kell cserélni. Ha találunk, akkor cserélünk, majd folytatjuk a keresést. Mi ennél egy kicsit hatékonyabb változatot fogunk vizsgálni. A megoldást úgy végezzük el, hogy a tömb első elemét kivesszük a helyéről. Az utolsó elemtől visszafelé keresünk egy olyat, amely T tulajdonságú, és ezt előrehozzuk a kivett elem helyére. Ezután a hátul felszabadult helyre elölről keresünk egy nem T tulajdonságú elemet, s ha találtunk, azt hátratesszük. Mindezt addig végezzük, amíg a tömbben két irányban haladva össze nem találkozunk.

Mondatszerű leírás

Struktogram

Szétválogatás(N,X,Y,Db,Z,DbZ):

E:=1; U:=N; segéd:=X[E]

Ciklus amíg E<U

[T tulajdonságú elem keresése:]

Ciklus amíg E<U és nem T(X[U])

U:=U-1

Ciklus vége

Ha E<U akkor

X[E]:=X[U]; E:=E+1

[nem T tulajdonságú elem keresése:]

Ciklus amíg E<U és T(X[E])

E:=E+1

Ciklus vége

Ha E<U akkor X[U]:=X[E]; U:=U-1

Elágazás vége

Ciklus vége

X[E]:=segéd

Ha T(X[E]) akkor Db:=E különben Db:=E-1

Eljárás vége.

A szétválogatás tétel 'helyben' változatásnak algoritmusa, struktogrammal.

Egy példa megoldása

Nézzük meg az egyik feladat megoldását, a szétválogatott elemeket egy tömbben elhelyezve elölről, illetve hátulról!

Feladat

F27. Párosak-páratlanok szétválogatása.

A specifikációbeli fogalmak aktualizálása:

bemeneti elemek száma: N

bemeneti tömb: X N db elem

kimeneti elemek (párosak) száma: Db

kimeneti tömb: Y N db elem

T(x): PárosE(x):=(x Mod 2)=0

azaz igaz, ha a paraméterül adott x 2-vel maradék nélkül osztható

Feladat

Gyakorlásként készítse el a megoldás algoritmusát!

Az animáció bemutatja a szétválogatás tételt és használatát:

Az animáció bemutatja a szétválogatás tételt és használatát.

Flash lejátszó letöltése

Szétválogatás tétel

Vissza a tartalomjegyzékhez

4. Metszet

A következő három feladattípus újabb feladattípus-osztályba tartozik, ezekben több sorozathoz kell egyet rendelni.

Feladat

F30. Adjuk meg két természetes szám osztói ismeretében az összes közös osztójukat!

F31. Nyáron és télen is végeztünk madármegfigyeléseket a Balatonon. Ismerjük, hogy nyáron, illetve télen mely madárfajok fordultak elő. Állapítsuk meg ezek alapján, hogy melyek a nem költöző madarak!

F32. Négy ember heti szabad estéi ismeretében állapítsuk meg, hogy a héten melyik este mehetnek el együtt moziba!

Közös jellemzőjük e feladatoknak, hogy valahány – alapesetben itt is kettő – halmaz elemei közül azokat kell kiválogatnunk, amelyek mindegyikben előfordulnak. E halmazok elemeit – a többi programozási tétel tárgyalásmódjához hasonlóan – egy sorozatban (tömbben) felsoroljuk.

Kérdés: Miért nem a sorozatszámítás tételt alkalmazzuk e feladat megoldására?

Válasz: A sorozatszámítás tételben halmazokkal végezhettünk műveleteket, itt pedig olyan sorozatokkal, amelyek halmaz módján felsorolva tartalmaznak elemeket. Emiatt a sorozatszámításban említett, két halmaz közötti metszetműveletet így lehet végrehajtani, ha a halmazokat sorozatként ábrázoljuk.

Specifikáció

Bemenet

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

Kimenet

Db:Egész, Z:Tömb[1..min(N,M):Valami]

Előfeltétel

N≥0 és M≥0 és HalmazE(X) és HalmazE(Y)

Utófeltétel

Db=SZUM(i=1..N;X[i]∈Y) 1 és

∀i(1≤i≤Db): (Z[i]∈X és Z[i]∈Y) és

HalmazE(Z)

Algoritmus

A megoldásban válogassuk ki X olyan elemeit, amelyek benne vannak Y-ban! Az algoritmus tehát egy kiválogatás, amely a belsejében egy eldöntést tartalmaz.

Mondatszerű leírás

Struktogram

Metszet(N,X,M,Y,Db,Z):

[kiválogatás:]

Db:=0

Ciklus I=1-től N-ig

[eldöntés:]

J:=1

Ciklus amíg J≤M és X[I]≠Y[J]
J:=J+1

Ciklus vége

Ha J≤M akkor Db:=Db+1; Z[Db]:=X[I]

Ciklus vége

Eljárás vége.

A metszet tétel algoritmusa, struktogrammal.

Rokonfeladatok – alkalmazás

E feladattípus hasonlítható több, az elemi programozási tételek között szerepelt feladattípushoz, ha a feladatot némileg módosítjuk.

Nézzük meg ezek közül például a keresést!

Bemenet

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

Kimenet

Van:Logikai, E:Valami

Előfeltétel

N≥0 és M≥0 és HalmazE(X) és HalmazE(Y)

Utófeltétel

Van=∃i,j(1≤i≤N és 1≤j≤M): X[i]=Y[j] és

Van→∃i,j(1≤i≤N és 1≤j≤M): X[i]=Y[j] és E=X[i]

Algoritmus – metszetbeli elemkeresés

Mondatszerű leírás

Struktogram

Metszetbeli_elem(N,X,M,Y,Van,E):

I:=1; Van:=hamis

Ciklus amíg I≤N és nem Van

J:=1

Ciklus amíg J≤M és X[I]≠Y[J]

J:=J+1

Ciklus vége

Ha J≤M akkor Van:=igaz; E:=X[I] különben I:=I+1

Ciklus vége

Eljárás vége.

Az animáció bemutatja a metszet tételt és használatát:

Az animáció bemutatja a metszet tételt és használatát.

Flash lejátszó letöltése

Metszet tétel
A metszet tétel 'keresés' változatának algoritmusa, struktogrammal.

Vissza a tartalomjegyzékhez

5. Egyesítés (unió)

Ha halmazokról van szó, akkor a metszet mellett természetesen meg kell jelennie az uniónak is.

Feladat

F33. Két szám prímosztóinak ismeretében adjuk meg legkisebb közös többszörösük prímosztóit!

F34. Egy iskola két földrajztanára órarendjének ismeretében adjuk meg azokat az órákat, amelyben valamelyikük tud egy órát helyettesíteni!

Ebben a feladattípusban tehát azon elemekre vagyunk kíváncsiak, amelyek két halmaz közül legalább az egyikben előfordulnak.

Specifikáció

Bemenet

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

Kimenet

Db:Egész, Z:Tömb[1..N+M:Valami]

Előfeltétel

N≥0 és M≥0 és HalmazE(X) és HalmazE(Y)

Utófeltétel

Db=N+SZUM(i=1..M;Y[i]∉X) 1 és

∀i(1≤i≤Db): (Z[i]∈X vagy Z[i]∈Y) és

HalmazE(Z)

Algoritmus

A megoldásban másoljuk le X elemeit Z-be, majd válogassuk ki Y olyan elemeit, amelyek nincsenek benne X-ben! Az algoritmus tehát egy másolás, majd egy kiválogatás, amely a belsejében egy eldöntést tartalmaz.

Mondatszerű leírás

Struktogram

Egyesítés(N,X,M,Y,Db,Z):
[másolás:]

Z:=X; Db:=N

[kiválogatás:]

Ciklus J=1-től M-ig

[eldöntés:]

I:=1

Ciklus amíg I≤N és X[I]≠Y[J]

I:=I+1

Ciklus vége

Ha I>N akkor Db:=Db+1; Z[Db]:=Y[J]

Ciklus vége

Eljárás vége.

Az egyesítés tétel algoritmusa, struktogrammal.

Rokonfeladat – alkalmazás

A példák megoldása helyett itt is egy alkalmazást nézzünk!

Feladat

Egy sorozatból készítsünk halmazfelsorolást! A feladat tehát az, hogy másoljuk le egy sorozat elemeit, de az azonos értékű elemek az eredményben csak egyszer szerepeljenek!

Ez egy furcsa egyesítés, ’Z:=∅; Z:=Z∪X’ képlettel írhatnánk le, azaz azokat az elemeket vegyük bele X-ből az eredménybe, amelyek még nem szerepelnek benne.

A specifikációt készítse el az egyesítésből kiindulva!

És íme a megoldás algoritmusa:

Algoritmus – halmazfelsorolás

Mondatszerű leírás

Struktogram

Halmazfelsorolás_készítés(N,X,Db,Z):

Db:=0

Ciklus I=1-től N-ig

J:=1

Ciklus amíg J≤Db és X[I]≠Z[J]

J:=J+1

Ciklus vége

Ha J>Db akkor Db:=Db+1; Z[Db]:=X[I]

Ciklus vége

Eljárás vége.

Az animáció bemutatja az unió tételt és használatát:

Az animáció bemutatja az unió tételt és használatát.

Flash lejátszó letöltése

Unió tétel
A halmazfelsorolás-készítés algoritmusa, struktogrammal.

Vissza a tartalomjegyzékhez

6. Összefuttatás (rendezettek uniója)

Bizonyos esetekben az unió feladattípus megoldása az előző fejezetbelinél hatékonyabb lehet. Ezt is konkrét feladatokon keresztül vizsgáljuk.

Feladat

F35. Egy osztály lány-, illetve fiútanulóinak névsora alapján állítsuk elő az osztálynévsort!

F36. Egy iskolában négy szakkörre járnak tanulók (van aki többre is). A szakkörnévsorok alapján állítsuk elő a szakkörre járó tanulók névsorát!

Megállapíthatjuk, hogy az általános egyesítéshez képest itt az a specialitás, hogy mindegyik sorozatként ábrázolt halmaz rendezett, s az eredménynek is rendezettnek kell lenni.

Megjegyzés

Ha nem két sorozatról van szó, akkor az a korábbiaknak megfelelően visszavezethető két sorozat feldolgozására.

Specifikáció

Bemenet

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

Kimenet

Db:Egész, Z:Tömb[1..N+M:Valami]

Előfeltétel

N≥0 és M≥0 és

HalmazE(X) és HalmazE(Y) és

RendezettE(X) és RendezettE(Y)

Utófeltétel

Db=N+SZUM(i=1..M;Y[i]∉X) 1 és

∀i(1≤i≤Db): (Z[i]∈X vagy Z[i]∈Y) és

HalmazE(Z) és RendezettE(Z)

Algoritmus

A megoldásban haladjunk párhuzamosan a két sorozatban! Az eredmény első eleme vagy X[1] vagy Y[1] lesz. Amelyik kisebb, azt az eredménysorozatba tesszük, abban a sorozatban kell továbblépni egy elemmel, s újra egy-egy elemet hasonlítani. Ha egyenlők voltak, akkor az egyiket másoljuk az eredménybe, majd mindkét sorozatban továbblépünk. Ha az egyiknek a végére értünk, akkor a másikat minden változtatás nélkül az eredménybe másoljuk.

Mondatszerű leírás

Struktogram

Összefuttatás(N,X,M,Y,Db,Z):

I:=1; J:=1; Db:=0

Ciklus amíg I≤N és J≤M

Db:=Db+1

Elágazás

X[I]<Y[J] esetén Z[Db]:= X[I]; I:=I+1

X[I]=Y[J] esetén Z[Db]:= X[I]; I:=I+1; J:=J+1

X[I]>Y[J] esetén Z[Db]:=Y[J]; J:=J+1

Elágazás vége

Ciklus vége

Ciklus amíg I≤N

Db:=Db+1; Z[Db]:=X[I]; I:=I+1

Ciklus vége

Ciklus amíg J≤M

Db:=Db+1; Z[Db]:=Y[J]; J:=J+1

Ciklus vége

Eljárás vége.

Az összefuttatás tétel alap algoritmusa, struktogrammal.

A megoldást elemezve észrevehetjük, hogy ha olyan szerencsénk volt, hogy X[N]=Y[M], akkor az utolsó két ciklusra tulajdonképpen nincs is szükség, hiszen nem maradt másolnivaló. Az a baj, hogy ez a szerencsés eset viszonylag ritkán fordul elő.

A második megoldásváltozatban mi magunk idézzük elő e szerencsét: mindkét sorozat végére egy nagyon nagy (az adott típus legnagyobb értéke: +∞), de egyező elemet teszünk.

Mondatszerű leírás

Struktogram

Összefuttatás(N,X,M,Y,Db,Z):

I:=1; J:=1; Db:=0

X[N+1]:=+∞; Y[M+1]:=+∞ [+∞ az elemtípus maximális értéke]

Ciklus amíg I<N+1 vagy J<M+1

Db:=Db+1

Elágazás

X[I]<Y[J] esetén Z[Db]:= X[I]; I:=I+1

X[I]=Y[J] esetén Z[Db]:= X[I]; I:=I+1; J:=J+1

X[I]>Y[J] esetén Z[Db]:=Y[J]; J:=J+1

Elágazás vége

Ciklus vége

Eljárás vége.

Az összefuttatás tétel 'egy-ciklusos' változatának algoritmusa, struktogrammal.

Ebben a megoldásban a hozzávett fiktív elem nem kerül be az eredménybe. Ha szükségünk lenne rá, a ciklus vége után még elhelyezhetnénk az eredmény végére.

A harmadik változatban kihasználjuk azt a – nem minden feladatban meglevő – specialitást, hogy a két sorozatban biztosan nincs közös elem. Ilyen például a fejezet elején szereplő F35. feladat. Ezt az altípust a megkülönböztetés érdekében összefésülésnek nevezzük.

Mondatszerű leírás

Struktogram

Összefuttatás(N,X,M,Y,Db,Z):

I:=1; J:=1; Db:=0

X[N+1]:=+∞; Y[M+1]:=+∞ [+∞ az elemtípus maximális értéke]

Ciklus amíg I<N+1 vagy J<M+1

Db:=Db+1

Ha X[I]<Y[J] akkor Z[Db]:=X[I]; I:=I+1

különben Z[Db]:=Y[J]; J:=J+1

Ciklus vége

Eljárás vége.

Az összefésülés tétel algoritmusa, struktogrammal.

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.