¨ Osszetett programoz´asi t´etelek 3. el˝ oad´as Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar
2011. szeptember 19.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
1 / 37
Felhaszn´alt irodalom Szl´avi P´eter, Zsak´o L´aszl´ o: M´ odszeres programoz´as: Programoz´asi t´etelek (Mikrol´ogia 19). ELTE TTK, 2002
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
2 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
3 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
4 / 37
M´asol´as T´ıpusfeladatok 1
Egy oszt´aly tanul´oinak ´atlageredm´enye alapj´an hat´arozzuk meg, hogy bizony´ıtv´anyukba jeles, j´ o, k¨ ozepes vagy el´egs´eges ker¨ ul-e. (Tegy¨ uk fel, hogy bukott tanul´ o nincs.)
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
5 / 37
M´asol´as T´ıpusfeladatok 1
Egy oszt´aly tanul´oinak ´atlageredm´enye alapj´an hat´arozzuk meg, hogy bizony´ıtv´anyukba jeles, j´ o, k¨ ozepes vagy el´egs´eges ker¨ ul-e. (Tegy¨ uk fel, hogy bukott tanul´ o nincs.)
2
Egy sz¨oveg minden mag´anhangz´ oj´at cser´elj¨ uk ki az e bet˝ ure.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
5 / 37
M´asol´as T´ıpusfeladatok 1
Egy oszt´aly tanul´oinak ´atlageredm´enye alapj´an hat´arozzuk meg, hogy bizony´ıtv´anyukba jeles, j´ o, k¨ ozepes vagy el´egs´eges ker¨ ul-e. (Tegy¨ uk fel, hogy bukott tanul´ o nincs.)
2
Egy sz¨oveg minden mag´anhangz´ oj´at cser´elj¨ uk ki az e bet˝ ure.
K¨oz¨os jellemz˝ok Az eredm´eny ugyanannyi elemsz´am´ u mint a bemenet
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
5 / 37
M´asol´as T´ıpusfeladatok 1
Egy oszt´aly tanul´oinak ´atlageredm´enye alapj´an hat´arozzuk meg, hogy bizony´ıtv´anyukba jeles, j´ o, k¨ ozepes vagy el´egs´eges ker¨ ul-e. (Tegy¨ uk fel, hogy bukott tanul´ o nincs.)
2
Egy sz¨oveg minden mag´anhangz´ oj´at cser´elj¨ uk ki az e bet˝ ure.
K¨oz¨os jellemz˝ok Az eredm´eny ugyanannyi elemsz´am´ u mint a bemenet Az eredm´eny i. elem´et a bemenet i. elem´eb˝ ol lehet meghat´arozni
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
5 / 37
M´asol´as Bemenet X : Feldolgozand´o t¨ omb N: T¨omb elemeinek sz´ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
6 / 37
M´asol´as Bemenet
Kimenet
X : Feldolgozand´o t¨ omb
Y : Eredm´eny t¨omb
N: T¨omb elemeinek sz´ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
6 / 37
M´asol´as Bemenet
Kimenet
X : Feldolgozand´o t¨ omb
Y : Eredm´eny t¨omb
N: T¨omb elemeinek sz´ama
Pszeudok´od Elj´ar´as M´asol´as(N, X , Y ) Ciklus i := 1-t˝ol N-ig Y [i] := m˝ uvelet X [i] Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
6 / 37
M´asol´as Megjegyz´esek Az eredm´eny mindig ugyanannyi elemsz´am´ u mint a bemenet
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
7 / 37
M´asol´as Megjegyz´esek Az eredm´eny mindig ugyanannyi elemsz´am´ u mint a bemenet A m˝ uvelet seg´ıts´eg´evel az egyszer˝ u m´asol´ason t´ ul az egyes elemekkel egy-egy elemi m˝ uveletet is el lehet v´egezni (pl. m´asoljuk ´at a sz´amok abszolut´ert´ekeit)
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
7 / 37
M´asol´as Megjegyz´esek Az eredm´eny mindig ugyanannyi elemsz´am´ u mint a bemenet A m˝ uvelet seg´ıts´eg´evel az egyszer˝ u m´asol´ason t´ ul az egyes elemekkel egy-egy elemi m˝ uveletet is el lehet v´egezni (pl. m´asoljuk ´at a sz´amok abszolut´ert´ekeit) Nem lehet az elemek k¨ oz¨ otti ¨ osszef¨ ugg´est kihaszn´alni
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
7 / 37
M´asol´as Mag´anhangz´ok e-re cser´el´ese Elj´ar´as M´asol´as(N, X , Y ) Ciklus i := 1-t˝ol N-ig Ha mag´anhangz´o(X [i]) akkor Y [i] :=’e’ k¨ ul¨onben Y [i] := X [i] El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
8 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
9 / 37
Kiv´alogat´as T´ıpusfeladatok 1
Egy szem´elyzeti nyilv´antart´asban emberek neve ´es szem´elyi sz´ama szerepel, adjuk meg a 20 ´evn´el fiatalabb l´anyokat.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
10 / 37
Kiv´alogat´as T´ıpusfeladatok 1
Egy szem´elyzeti nyilv´antart´asban emberek neve ´es szem´elyi sz´ama szerepel, adjuk meg a 20 ´evn´el fiatalabb l´anyokat.
2
Adjuk meg egy term´eszetes sz´am ¨ osszes oszt´ oj´at.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
10 / 37
Kiv´alogat´as T´ıpusfeladatok 1
Egy szem´elyzeti nyilv´antart´asban emberek neve ´es szem´elyi sz´ama szerepel, adjuk meg a 20 ´evn´el fiatalabb l´anyokat.
2
Adjuk meg egy term´eszetes sz´am ¨ osszes oszt´ oj´at.
3
Adjuk meg egy oszt´aly azon tanul´ oit, akik jeles ´atlag´ uak.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
10 / 37
Kiv´alogat´as T´ıpusfeladatok 1
Egy szem´elyzeti nyilv´antart´asban emberek neve ´es szem´elyi sz´ama szerepel, adjuk meg a 20 ´evn´el fiatalabb l´anyokat.
2
Adjuk meg egy term´eszetes sz´am ¨ osszes oszt´ oj´at.
3
Adjuk meg egy oszt´aly azon tanul´ oit, akik jeles ´atlag´ uak.
K¨oz¨os jellemz˝ok Hasonl´ıtanak a feladatok a keres´esre, mert adott tulajdons´ag´ u elem(ek)et kell megadni, de nem csak egyet.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
10 / 37
Kiv´alogat´as T´ıpusfeladatok 1
Egy szem´elyzeti nyilv´antart´asban emberek neve ´es szem´elyi sz´ama szerepel, adjuk meg a 20 ´evn´el fiatalabb l´anyokat.
2
Adjuk meg egy term´eszetes sz´am ¨ osszes oszt´ oj´at.
3
Adjuk meg egy oszt´aly azon tanul´ oit, akik jeles ´atlag´ uak.
K¨oz¨os jellemz˝ok Hasonl´ıtanak a feladatok a keres´esre, mert adott tulajdons´ag´ u elem(ek)et kell megadni, de nem csak egyet. Hasonl´ıtanak a megsz´aml´al´asra is, de nem megsz´amolni kell az elemeket, hanem megadni/m´asolni.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
10 / 37
Kiv´alogat´as Bemenet X : Feldolgozand´o t¨ omb N: T¨omb elemeinek sz´ama T : Tulajdons´ag f¨ uggv´eny
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
11 / 37
Kiv´alogat´as Bemenet
Kimenet
X : Feldolgozand´o t¨ omb
Y : Eredm´eny t¨omb
N: T¨omb elemeinek sz´ama
DB: T¨ omb elemeinek sz´ama
T : Tulajdons´ag f¨ uggv´eny
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
11 / 37
Kiv´alogat´as Bemenet
Kimenet
X : Feldolgozand´o t¨ omb
Y : Eredm´eny t¨omb
N: T¨omb elemeinek sz´ama
DB: T¨ omb elemeinek sz´ama
T : Tulajdons´ag f¨ uggv´eny
Pszeudok´od Elj´ar´as Kiv´alogat´as(N, X , DB, Y ) DB := 0 Ciklus i := 1-t˝ol N-ig Ha T (X [i]) akkor DB := DB + 1 Y [DB] := X [i] El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
11 / 37
Kiv´alogat´as Megjegyz´esek Az eredm´eny t¨omb elemsz´am´at nem lehet el˝ ore pontosan meghat´arozni, de biztos, hogy nincs t¨ obb eleme mint a bemeneti t¨ombnek.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
12 / 37
Kiv´alogat´as Megjegyz´esek Az eredm´eny t¨omb elemsz´am´at nem lehet el˝ ore pontosan meghat´arozni, de biztos, hogy nincs t¨ obb eleme mint a bemeneti t¨ombnek. X [i] helyett n´eha csak i-t m´asoljuk Y -ba, azaz a felt´etelnek megfelel˝o elemek index´et t´aroljuk
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
12 / 37
Kiv´alogat´as Ha a bemeneti sorozatra m´ar nincs sz¨ uks´eg a k´es˝obbiekben, akkor a kiv´alogat´as eredm´enye a bemeneti sorozat elej´ere is ker¨ ulhet.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
13 / 37
Kiv´alogat´as Ha a bemeneti sorozatra m´ar nincs sz¨ uks´eg a k´es˝obbiekben, akkor a kiv´alogat´as eredm´enye a bemeneti sorozat elej´ere is ker¨ ulhet. Ebben az esetben kevesebb mem´ ori´at kell lefoglalnunk.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
13 / 37
Kiv´alogat´as Ha a bemeneti sorozatra m´ar nincs sz¨ uks´eg a k´es˝obbiekben, akkor a kiv´alogat´as eredm´enye a bemeneti sorozat elej´ere is ker¨ ulhet. Ebben az esetben kevesebb mem´ ori´at kell lefoglalnunk.
Pszeudok´od Elj´ar´as Kiv´alogat´as(N, X , DB) DB:=0 Ciklus i := 1-t˝ol N-ig Ha T (X [i]) akkor DB := DB + 1 X [DB] := X [i] El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
13 / 37
Kiv´alogat´as Lehets´eges megval´os´ıt´as az is, ha a kihagyand´ o elemeket megjel¨olj¨ uk valamilyen m´odon.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
14 / 37
Kiv´alogat´as Lehets´eges megval´os´ıt´as az is, ha a kihagyand´ o elemeket megjel¨olj¨ uk valamilyen m´odon. Ebben az esetben is elvesz´ıtj¨ uk az eredeti sorozatot.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
14 / 37
Kiv´alogat´as Lehets´eges megval´os´ıt´as az is, ha a kihagyand´ o elemeket megjel¨olj¨ uk valamilyen m´odon. Ebben az esetben is elvesz´ıtj¨ uk az eredeti sorozatot.
Pszeudok´od Elj´ar´as Kiv´alogat´as(N, X ) Ciklus i := 1-t˝ol N-ig Ha ¬ (T (X [i])) akkor X [i] := speci´alis ´ert´ek El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
14 / 37
Kiv´alogat´as Jeles ´atlag´u tanul´ok neve Elj´ar´as Kiv´alogat´as(N, X , DB, NEV ) DB := 0 Ciklus i := 1-t˝ol N-ig Ha X [i].atlag ≥ 4.71 akkor DB := DB + 1 NEV [DB] := X [i].nev El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
15 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
16 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
2
Az oszt´aly tanul´ oit n´evsoruk alapj´an v´alogassuk sz´et l´anyokra ´es fi´ ukra.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
2
Az oszt´aly tanul´ oit n´evsoruk alapj´an v´alogassuk sz´et l´anyokra ´es fi´ ukra.
3
Az oszt´aly tanul´ oinak f´el´evi ´atlageredm´enyei alapj´an v´alogassuk sz´et jelesekre, j´ okra, k¨ ozepesekre, el´egs´egesekre, valamint el´egtelenekre.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
2
Az oszt´aly tanul´ oit n´evsoruk alapj´an v´alogassuk sz´et l´anyokra ´es fi´ ukra.
3
Az oszt´aly tanul´ oinak f´el´evi ´atlageredm´enyei alapj´an v´alogassuk sz´et jelesekre, j´ okra, k¨ ozepesekre, el´egs´egesekre, valamint el´egtelenekre.
K¨oz¨os jellemz˝ok Egy sorozathoz t¨ obb sorozatot rendel¨ unk
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
2
Az oszt´aly tanul´ oit n´evsoruk alapj´an v´alogassuk sz´et l´anyokra ´es fi´ ukra.
3
Az oszt´aly tanul´ oinak f´el´evi ´atlageredm´enyei alapj´an v´alogassuk sz´et jelesekre, j´ okra, k¨ ozepesekre, el´egs´egesekre, valamint el´egtelenekre.
K¨oz¨os jellemz˝ok Egy sorozathoz t¨ obb sorozatot rendel¨ unk L´enyeg´eben egym´as ut´an kett˝ o (vagy t¨ obb) kiv´alogat´assal megoldhat´ok a feladatok
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as T´ıpusfeladatok 1
Adott N darab k¨ ul¨ onb¨ oz˝ o term´eszetes sz´am, v´alogassuk sz´et a p´arosakat ´es a p´aratlanokat.
2
Az oszt´aly tanul´ oit n´evsoruk alapj´an v´alogassuk sz´et l´anyokra ´es fi´ ukra.
3
Az oszt´aly tanul´ oinak f´el´evi ´atlageredm´enyei alapj´an v´alogassuk sz´et jelesekre, j´ okra, k¨ ozepesekre, el´egs´egesekre, valamint el´egtelenekre.
K¨oz¨os jellemz˝ok Egy sorozathoz t¨ obb sorozatot rendel¨ unk L´enyeg´eben egym´as ut´an kett˝ o (vagy t¨ obb) kiv´alogat´assal megoldhat´ok a feladatok K´et kiv´alogat´assal megval´ os´ıtani viszont felesleges, mert amely elemeket nem v´alasztunk ki a kiv´alogat´asn´al az egyik csoportba, azok tartoznak a m´asik csoportba Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
17 / 37
Sz´etv´alogat´as Bemenet X : Feldolgozand´ o t¨ omb N: T¨ omb elemeinek sz´ ama T : Tulajdons´ ag f¨ uggv´ eny
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
18 / 37
Sz´etv´alogat´as Bemenet
Kimenet Y : Egyik eredm´ eny t¨ omb
X : Feldolgozand´ o t¨ omb
Z : M´ asik eredm´ eny t¨ omb
N: T¨ omb elemeinek sz´ ama T : Tulajdons´ ag f¨ uggv´ eny
DBY : Y elemeinek sz´ ama DBZ : Z elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
18 / 37
Sz´etv´alogat´as Bemenet
Kimenet Y : Egyik eredm´ eny t¨ omb
X : Feldolgozand´ o t¨ omb
Z : M´ asik eredm´ eny t¨ omb
N: T¨ omb elemeinek sz´ ama
DBY : Y elemeinek sz´ ama
T : Tulajdons´ ag f¨ uggv´ eny
DBZ : Z elemeinek sz´ ama
Pszeudok´od Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DBY , Y , DBZ , Z ) DBY := 0 DBZ := 0 Ciklus i := 1-t˝ ol N-ig Ha T (X [i]) akkor DBY := DBY + 1 Y [DBY ] := X [i] k¨ ul¨ onben DBZ := DBZ + 1 Z [DBZ ] := X [i] El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
18 / 37
Sz´etv´alogat´as Megjegyz´esek Y ´es Z elemsz´ama nem hat´arozathat´ o meg el˝ ore, ´ıgy N elem˝ u t¨omb¨oknek foglalunk helyet a mem´ ori´aban
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
19 / 37
Sz´etv´alogat´as Az eredm´enyek egyetlen t¨ ombbe is helyezhet˝ ok u ´gy, hogy a T tulajdons´ag´ uak az elej´en, a t¨ obbi pedig a v´eg´en lesznek
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
20 / 37
Sz´etv´alogat´as Az eredm´enyek egyetlen t¨ ombbe is helyezhet˝ ok u ´gy, hogy a T tulajdons´ag´ uak az elej´en, a t¨ obbi pedig a v´eg´en lesznek
Pszeudok´od Elj´ar´as Sz´etv´alogat´as(N, X , DBY , Y ) DBY := 0 INDZ := N + 1 Ciklus i := 1-t˝ ol N-ig Ha T (X [i]) akkor DBY := DBY + 1 Y [DBY ] := X [i] k¨ ul¨onben INDZ := INDZ − 1 Y [INDZ ] := X [i] El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
20 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o
Pszeudok´od Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =1 Pszeudok´od U = 11
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’informatika’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =2 Pszeudok´od U = 11
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’anformatika’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =2 Pszeudok´od U = 10
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’anformatikn’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =3 Pszeudok´od U=9
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’aiformatikn’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =3 Pszeudok´od U=8
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’aiformatfkn’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =4 Pszeudok´od U=7
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’aiaormatfkn’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =5 Pszeudok´od U=6
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’aiaormrtfkn’
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as Az elemek helyben, azaz a bemeneti t¨ ombben t¨ ort´en˝o sz´etv´alogat´asa is megoldhat´o E =5 Pszeudok´od U=5
Elj´ ar´ as Sz´ etv´ alogat´ as(N, X , DB) E := 1; U := N; seged := X [E ] Ciklus am´ıg E < U Ciklus am´ıg E < U ´ es ¬ (T (X [U])) U := U − 1 Ciklus v´ ege Ha E < U akkor X [E ] := X [U]; E := E + 1 Ciklus am´ıg E < U ´ es T (X [E ]) E := E + 1 Ciklus v´ ege Ha E < U akkor X [U] := X [E ]; U := U − 1 El´ agaz´ as v´ ege El´ agaz´ as v´ ege Ciklus v´ ege X [E ] := seged Ha T (X [E ]) akkor DB := E k¨ ul¨ onben DB := E − 1 El´ agaz´ as v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
seged =’i’ X =’aiaoimrtfkn’ DB = 5
AAO 03
2011. szeptember 19.
21 / 37
Sz´etv´alogat´as P´aros-p´aratlan sz´etv´alogat´as Elj´ar´as Sz´etv´alogat´as(N, X , DB, Y ) DB := 0 IND := N + 1 Ciklus i := 1-t˝ol N-ig Ha p´aros(X [i]) akkor DB := DB + 1 Y [DB] := X [i] k¨ ul¨onben IND := IND − 1 Y [IND] := X [i] El´agaz´as v´ege ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
22 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
23 / 37
Metszet T´ıpusfeladatok 1
Adjuk meg k´et term´eszetes sz´am oszt´ oinak ismeret´eben az ¨osszes k¨oz¨os oszt´ojukat.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
24 / 37
Metszet T´ıpusfeladatok 1
Adjuk meg k´et term´eszetes sz´am oszt´ oinak ismeret´eben az ¨osszes k¨oz¨os oszt´ojukat.
2
Ny´aron ´es t´elen is v´egezt¨ unk mad´armegfigyel´eseket a Balatonon. Ismerj¨ uk, hogy ny´aron, illetve t´elen mely mad´arfajok fordultak el˝o. ´ Allap´ ıtsuk meg ezek alapj´an, hogy melyek a nem k¨olt¨oz˝o madarak.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
24 / 37
Metszet T´ıpusfeladatok 1
Adjuk meg k´et term´eszetes sz´am oszt´ oinak ismeret´eben az ¨osszes k¨oz¨os oszt´ojukat.
2
Ny´aron ´es t´elen is v´egezt¨ unk mad´armegfigyel´eseket a Balatonon. Ismerj¨ uk, hogy ny´aron, illetve t´elen mely mad´arfajok fordultak el˝o. ´ Allap´ ıtsuk meg ezek alapj´an, hogy melyek a nem k¨olt¨oz˝o madarak.
3
N´egy ember heti szabad est´ei ismeret´eben ´allap´ıtsuk meg, hogy a h´eten melyik este mehetnek el egy¨ utt moziba.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
24 / 37
Metszet T´ıpusfeladatok 1
Adjuk meg k´et term´eszetes sz´am oszt´ oinak ismeret´eben az ¨osszes k¨oz¨os oszt´ojukat.
2
Ny´aron ´es t´elen is v´egezt¨ unk mad´armegfigyel´eseket a Balatonon. Ismerj¨ uk, hogy ny´aron, illetve t´elen mely mad´arfajok fordultak el˝o. ´ Allap´ ıtsuk meg ezek alapj´an, hogy melyek a nem k¨olt¨oz˝o madarak.
3
N´egy ember heti szabad est´ei ismeret´eben ´allap´ıtsuk meg, hogy a h´eten melyik este mehetnek el egy¨ utt moziba.
K¨oz¨os jellemz˝ok T¨obb sorozathoz egyet rendel¨ unk
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
24 / 37
Metszet T´ıpusfeladatok 1
Adjuk meg k´et term´eszetes sz´am oszt´ oinak ismeret´eben az ¨osszes k¨oz¨os oszt´ojukat.
2
Ny´aron ´es t´elen is v´egezt¨ unk mad´armegfigyel´eseket a Balatonon. Ismerj¨ uk, hogy ny´aron, illetve t´elen mely mad´arfajok fordultak el˝o. ´ Allap´ ıtsuk meg ezek alapj´an, hogy melyek a nem k¨olt¨oz˝o madarak.
3
N´egy ember heti szabad est´ei ismeret´eben ´allap´ıtsuk meg, hogy a h´eten melyik este mehetnek el egy¨ utt moziba.
K¨oz¨os jellemz˝ok T¨obb sorozathoz egyet rendel¨ unk K´et sorozat elemei k¨ oz¨ ul azokat kell kiv´alogatnunk, amelyek mindkett˝oben el˝ofordulnak
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
24 / 37
Metszet Megval´os´ıt´asi o¨tlet V´alogassuk ki az egyik sorozat (X ) azon elemeit, amelyek a m´asikban (Y ) is el˝ofordulnak
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
25 / 37
Metszet Megval´os´ıt´asi o¨tlet V´alogassuk ki az egyik sorozat (X ) azon elemeit, amelyek a m´asikban (Y ) is el˝ofordulnak Ehhez egy kiv´alogat´as ´es egy eld¨ ont´es t´etelt kell egym´asba ´ep´ıteni
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
25 / 37
Metszet Bemenet X : Egyik feldolgozand´ o t¨ omb Y : M´ asik feldolgozand´ o t¨ omb M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
26 / 37
Metszet Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
26 / 37
Metszet Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Pszeudok´od Elj´ ar´ as Metszet(M, X , N, Y , DB, Z ) DB := 0 Ciklus i := 1-t˝ ol M-ig j := 1 Ciklus am´ıg j ≤ N ´ es X [i] 6= Y [j] j := j + 1 Ciklus v´ ege Ha j ≤ N akkor DB := DB + 1 Z [DB] := X [i] El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
26 / 37
Metszet Megjegyz´esek Kis m´odos´ıt´assal a metszet t´etel nem csak k´et sorozat k¨oz¨os elemeinek meghat´aroz´as´ara alkalmazhat´ o
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
27 / 37
Metszet Megjegyz´esek Kis m´odos´ıt´assal a metszet t´etel nem csak k´et sorozat k¨oz¨os elemeinek meghat´aroz´as´ara alkalmazhat´ o Eld¨ ont´es: van-e k´et sorozatnak k¨ oz¨ os eleme?
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
27 / 37
Metszet Megjegyz´esek Kis m´odos´ıt´assal a metszet t´etel nem csak k´et sorozat k¨oz¨os elemeinek meghat´aroz´as´ara alkalmazhat´ o Eld¨ ont´es: van-e k´et sorozatnak k¨ oz¨ os eleme? Kiv´alaszt´as: adjuk meg a k´et sorozat egyik k¨ oz¨ os elem´et (ha tudjuk, hogy van ilyen)
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
27 / 37
Metszet Megjegyz´esek Kis m´odos´ıt´assal a metszet t´etel nem csak k´et sorozat k¨oz¨os elemeinek meghat´aroz´as´ara alkalmazhat´ o Eld¨ ont´es: van-e k´et sorozatnak k¨ oz¨ os eleme? Kiv´alaszt´as: adjuk meg a k´et sorozat egyik k¨ oz¨ os elem´et (ha tudjuk, hogy van ilyen) Keres´es: ha van, akkor adjuk meg a k´et sorozat egyik k¨oz¨os elem´et
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
27 / 37
Metszet Megjegyz´esek Kis m´odos´ıt´assal a metszet t´etel nem csak k´et sorozat k¨oz¨os elemeinek meghat´aroz´as´ara alkalmazhat´ o Eld¨ ont´es: van-e k´et sorozatnak k¨ oz¨ os eleme? Kiv´alaszt´as: adjuk meg a k´et sorozat egyik k¨ oz¨ os elem´et (ha tudjuk, hogy van ilyen) Keres´es: ha van, akkor adjuk meg a k´et sorozat egyik k¨oz¨os elem´et Megsz´amol´as: h´any k¨ oz¨ os eleme van a k´et sorozatnak?
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
27 / 37
Metszet Keress¨ uk meg X egyik olyan elem´et, amely benne van Y -ban is.
K¨oz¨os elem keres´ese Elj´ ar´ as MetszetbeliElem(M, X , N, Y , VAN, E ) i := 1 VAN :=hamis Ciklus am´ıg i ≤ M ´es ¬VAN j := 1 Ciklus am´ıg j ≤ N ´es X [i] 6= Y [j] j := j + 1 Ciklus v´ege Ha j ≤ N akkor VAN :=igaz E := X [i] k¨ ul¨ onben i := i + 1 El´ agaz´ as v´ege Ciklus v´ege Elj´ ar´ as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
28 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
29 / 37
Egyes´ıt´es (uni´o) T´ıpusfeladatok 1
K´et sz´am pr´ımoszt´oinak ismeret´eben adjuk meg legkisebb k¨oz¨os t¨obbsz¨or¨os¨ uk pr´ımoszt´ oit.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
30 / 37
Egyes´ıt´es (uni´o) T´ıpusfeladatok 1
K´et sz´am pr´ımoszt´oinak ismeret´eben adjuk meg legkisebb k¨oz¨os t¨obbsz¨or¨os¨ uk pr´ımoszt´ oit.
2
Egy iskola k´et f¨oldrajztan´ara ´ orarendj´enek ismeret´eben adjuk meg azokat az ´or´akat, amikor valamelyik¨ uk tud egy ´ or´at helyettes´ıteni.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
30 / 37
Egyes´ıt´es (uni´o) T´ıpusfeladatok 1
K´et sz´am pr´ımoszt´oinak ismeret´eben adjuk meg legkisebb k¨oz¨os t¨obbsz¨or¨os¨ uk pr´ımoszt´ oit.
2
Egy iskola k´et f¨oldrajztan´ara ´ orarendj´enek ismeret´eben adjuk meg azokat az ´or´akat, amikor valamelyik¨ uk tud egy ´ or´at helyettes´ıteni.
K¨oz¨os jellemz˝ok K´et sorozathoz egy sorozatot rendel
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
30 / 37
Egyes´ıt´es (uni´o) T´ıpusfeladatok 1
K´et sz´am pr´ımoszt´oinak ismeret´eben adjuk meg legkisebb k¨oz¨os t¨obbsz¨or¨os¨ uk pr´ımoszt´ oit.
2
Egy iskola k´et f¨oldrajztan´ara ´ orarendj´enek ismeret´eben adjuk meg azokat az ´or´akat, amikor valamelyik¨ uk tud egy ´ or´at helyettes´ıteni.
K¨oz¨os jellemz˝ok K´et sorozathoz egy sorozatot rendel Azokat az elemeket keress¨ uk, amelyek a k´et sorozatb´ol legal´abb az egyikben benne vannak
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
30 / 37
Egyes´ıt´es (uni´o) Bemenet X : Egyik feldolgozand´ o t¨ omb Y : M´ asik feldolgozand´ o t¨ omb M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
31 / 37
Egyes´ıt´es (uni´o) Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
31 / 37
Egyes´ıt´es (uni´o) Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Pszeudok´od Elj´ ar´ as Egyes´ıt´ es(M, X , N, Y , DB, Z ) Z := X DB := M Ciklus j := 1-t˝ ol N-ig i := 1 Ciklus am´ıg i ≤ M ´ es X [i] 6= Y [j] i := i + 1 Ciklus v´ ege Ha i > M akkor DB := DB + 1 Z [DB] := Y [j] El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
31 / 37
Egyes´ıt´es (uni´o) Kis m´odos´ıt´assal k´esz´ıthet¨ unk olyan algoritmust, amely egy sorozatb´ol halmazt k´esz´ıt, azaz egy sorozatot u ´gy alak´ıt ´at, hogy az azonos elemek csak egyszer szerepeljenek.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
32 / 37
Egyes´ıt´es (uni´o) Kis m´odos´ıt´assal k´esz´ıthet¨ unk olyan algoritmust, amely egy sorozatb´ol halmazt k´esz´ıt, azaz egy sorozatot u ´gy alak´ıt ´at, hogy az azonos elemek csak egyszer szerepeljenek.
Halmazfelsorol´as k´esz´ıt´es Elj´ ar´ as Halmazfelsorol´ asK´esz´ıt´es(N, X , DB, Z ) DB := 0 Ciklus i := 1-t˝ ol N-ig j := 1 Ciklus am´ıg j ≤ DB ´es X [i] 6= Z [j] j := j + 1 Ciklus v´ege Ha j > DB akkor DB := DB + 1 Z [DB] := X [i] El´ agaz´ as v´ege Ciklus v´ege Elj´ ar´ as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
32 / 37
¨ Osszetett programoz´asi t´etelek 1
M´asol´as
2
Kiv´alogat´as
3
Sz´etv´alogat´as
4
Metszet
5
Egyes´ıt´es
6
¨ Osszefuttat´ as
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
33 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) T´ıpusfeladatok 1
Egy oszt´aly l´any-, illetve fi´ u tanul´ oinak n´evsora alapj´an ´all´ıtsuk el˝o az oszt´alyn´evsort.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
34 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) T´ıpusfeladatok 1
Egy oszt´aly l´any-, illetve fi´ u tanul´ oinak n´evsora alapj´an ´all´ıtsuk el˝o az oszt´alyn´evsort.
2
Egy iskol´aban n´egy szak¨ orre j´arnak tanul´ ok (van aki t¨obbre is). A szakk¨orn´evsorok alapj´an ´all´ıtsuk el a szakk¨ orre j´ar´o tanul´ok n´evsor´at.
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
34 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) T´ıpusfeladatok 1
Egy oszt´aly l´any-, illetve fi´ u tanul´ oinak n´evsora alapj´an ´all´ıtsuk el˝o az oszt´alyn´evsort.
2
Egy iskol´aban n´egy szak¨ orre j´arnak tanul´ ok (van aki t¨obbre is). A szakk¨orn´evsorok alapj´an ´all´ıtsuk el a szakk¨ orre j´ar´o tanul´ok n´evsor´at.
K¨oz¨os jellemz˝ok Az ´altal´anos egyes´ıt´eshez k´epest itt specialit´as, hogy mindegyik sorozat rendezett
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
34 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) Bemenet X : Egyik feldolgozand´ o t¨ omb Y : M´ asik feldolgozand´ o t¨ omb M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
35 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
35 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) Bemenet
Kimenet
X : Egyik feldolgozand´ o t¨ omb
Z : Eredm´ eny t¨ omb
Y : M´ asik feldolgozand´ o t¨ omb
DB: Z elemeinek sz´ ama
M: X elemeinek sz´ ama N: Y elemeinek sz´ ama
Pszeudok´od ¨ Elj´ ar´ as Osszefuttat´ as(M, X , N, Y , DB, Z ) i := 1; j := 1; DB := 0 Ciklus am´ıg (i ≤ M) ´ es (j ≤ N) DB := DB + 1 El´ agaz´ as X [i] < Y [j] eset´ en Z [DB] := X [i]; i := i + 1 X [i] = Y [j] eset´ en Z [DB] := X [i]; i := i + 1; j := j + 1 X [i] > Y [j] eset´ en Z [DB] := Y [j]; j := j + 1 El´ agaz´ as v´ ege Ciklus v´ ege Ciklus am´ıg i ≤ M DB := DB + 1; Z [DB] := X [i]; i := i + 1 Ciklus v´ ege Ciklus am´ıg j ≤ N DB := DB + 1; Z [DB] := Y [j]; j := j + 1 Ciklus v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
35 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) Ha X [M] = Y [N], akkor az utols´ o k´et ciklusra nincs sz¨ uks´eg. Ezt a helyzetet magunk is el˝oid´ezhetj¨ uk.
Pszeudok´od ¨ Elj´ar´as Osszefuttat´ as(M, X , N, Y , DB, Z ) i := 1; j := 1; DB := 0 X [M + 1] := +∞; Y [N + 1] := +∞ Ciklus am´ıg (i < M + 1) vagy (j < N + 1) DB := DB + 1 El´agaz´as X [i] < Y [j] eset´en Z [DB] := X [i]; i := i + 1 X [i] = Y [j] eset´en Z [DB] := X [i]; i := i + 1; j := j + 1 X [i] > Y [j] eset´en Z [DB] := Y [j]; j := j + 1 El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
36 / 37
¨ Osszefuttat´ as (rendezettek uni´oja) Ha nincs a k´et sorozatban azonos elem, akkor a megval´os´ıt´as m´eg egyszer˝ ubb.
Pszeudok´od ¨ Elj´ar´as Osszefuttat´ as(M, X , N, Y , DB, Z ) i := 1; j := 1; DB := 0 X [M + 1] := +∞; Y [N + 1] := +∞ Ciklus am´ıg (i < M + 1) vagy (j < N + 1) DB := DB + 1 Ha X [i] < Y [j] akkor Z [DB] := X [i]; i := i + 1 k¨ ul¨onben Z [DB] := Y [j]; j := j + 1 El´agaz´as v´ege Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 03
2011. szeptember 19.
37 / 37
