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.
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
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): |  |
Egy példa megoldása
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): |
 |
Az animáció bemutatja a másolás tételt és használatát:
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.
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): |  |
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): |  |
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.
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): |  |
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.
Í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): | |
Egy példa megoldása
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
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:
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.
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. |  |
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. |  |
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. |  |
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!
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ó
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:
4. Metszet
A következő három feladattípus újabb feladattípus-osztályba tartozik, ezekben több sorozathoz kell egyet rendelni.
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] Ciklus vége Ha J≤M akkor Db:=Db+1; Z[Db]:=X[I] Ciklus vége Eljárás vége. |  |
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.
- Eldöntés: van-e a két halmaznak közös eleme?
- Kiválasztás: adjuk meg a két sorozat egyik közös elemét (ha tudjuk, hogy biztosan van ilyen)!
- Keresés: ha van, akkor adjuk meg a két sorozat egyik közös elemét!
- Megszámolás: hány közös eleme van a két sorozatnak?
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: Metszet tétel |  |
5. Egyesítés (unió)
Ha halmazokról van szó, akkor a metszet mellett természetesen meg kell jelennie az uniónak is.
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): 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. |  |
Rokonfeladat – alkalmazás
A példák megoldása helyett itt is egy alkalmazást nézzünk!
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: Unió tétel |  |
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.
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.
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. |  |
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. |  |
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. |  |
