Programoz´as I. 3. el˝ oad´as Egyszer˝ u programoz´asi t´etelek
Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar Alkalmazott Informatikai Int´ ezet
2015. szeptember 21.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
1 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
2 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
3 / 49
Programoz´asi t´etelek A programoz´asi t´etelek j´ ol megv´alasztott, egyszer˝ u feladatok megold´asai Seg´ıts´eg¨ ukkel a gyakorlatban el˝ ofordul´ o feladatok jelent˝os r´esze megoldhat´ o Helyess´eg¨ uk egyszer˝ uen bizony´ıthat´ o Haszn´alatuk c´elszer˝ u, hiszen (m´asok ´altal is) j´ ol ´attekinthet˝o k´odot eredm´enyeznek
Egy lehets´eges csoportos´ıt´asuk Egyszer˝ u programoz´asi t´etelek Egy sorozathoz egy ´ert´eket rendel˝ o feladatok
¨ Osszetett programoz´asi t´etelek Egy sorozathoz egy sorozatot rendel˝ o feladatok Egy sorozathoz t¨ obb sorozatot rendel˝ o feladatok T¨ obb sorozathoz egy sorozatot rendel˝ o feladatok
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
4 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
5 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
6 / 49
Sorozatsz´am´ıt´as T´ıpusfeladatok 1
Egy oszt´aly N darab tanul´ oj´anak oszt´alyzata alapj´an adjuk meg az oszt´aly ´atlag´at!
2
Egy M elem˝ u bet˝ usorozat bet˝ uit f˝ uzz¨ uk ¨ ossze egyetlen sz¨oveg t´ıpus´ u v´altoz´ oba!
3
K´esz´ıts¨ unk algoritmust, amely egy aut´ oversenyz˝ o k¨or¨onk´enti ideje alapj´an meghat´arozza a versenyz˝ o egy k¨ or megt´etel´ehez sz¨ uks´eges ´atlagidej´et!
4
A Balaton ment´en K darab madar´asz v´egzett megfigyel´eseket. Mindegyik megadta, hogy milyen madarakat l´atott. K´esz´ıts¨ unk algoritmust, amely a megfigyel´esek alapj´an megadja a Balatonon el˝ofordul´o mad´arfajokat!
5
Adjuk meg az els˝o N darab pozit´ıv eg´esz sz´am szorzat´at!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
7 / 49
Sorozatsz´am´ıt´as Feladat Egy t¨omb minden eleme k¨ oz¨ ott akarunk egy adott m˝ uveletet (pl. ¨osszead´as) elv´egezni. Eredm´eny¨ ul a t¨ombelemek k¨ oz¨ ott az adott m˝ uvelet ´altal szolg´altatott ´ert´eket adjuk vissza.
Megval´os´ıt´as L´etrehozunk egy v´altoz´ ot, amiben a m˝ uveleti eredm´enyt t´aroljuk el. Ennek kezdeti ´ert´eket is adunk. Sz´aml´al´os ciklussal v´egigmegy¨ unk a t¨ omb ¨ osszes elem´en. A m˝ uveleti eredm´enyhez az adott m˝ uvelettel hozz´akapcsoljuk (pl. hozz´aadjuk) az aktu´alis t¨ ombelemet.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
8 / 49
Sorozatsz´am´ıt´as Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz (t¨ omb m´erete) Kimenet: ´ert´ek − T ´ m´ıta ´ s(x, n) f¨ uggv´ eny Sorozatsza ´ert´ek ← ´ert´ek0 ciklus i ← 1-t˝ol n-ig ´ert´ek ← ´ert´ek ⊕ x[i] ciklus v´ ege vissza ´ert´ek f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
9 / 49
Sorozatsz´am´ıt´as Megjegyz´esek Adatok sorozat´ahoz egy ´ert´eket rendel˝ o f¨ uggv´enyt helyettes´ıt Minden olyan esetben haszn´alhat´ o, ha ezt a f¨ uggv´enyt felbonthatjuk ´ert´ekp´arokon kisz´am´ıtott m˝ uveletek (⊕) sorozat´ara Az indul´askor haszn´alt null´ert´eket ´ertelemszer˝ uen a k´erd´eses m˝ uvelet (esetleg a feladat) alapj´an kell megv´alasztani
´ert´ek0 ⊕
¨osszegz´es 0
faktori´alis 1
elemek uni´oja {}
´ert´ek ← ´ert´ek + x[i]
´ert´ek ← ´ert´ek ∗ x[i]
´ert´ek ← ´ert´ek ∪ x[i]
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
10 / 49
Sorozatsz´am´ıt´as
Pszeudok´od
Fut´asi id˝o
´ m´ıta ´ s(x, n) f¨ uggv´ eny Sorozatsza ´ert´ek ← ´ert´ek0 ciklus i ← 1-t˝ ol n-ig ´ert´ek ← ´ert´ek ⊕ x[i] ciklus v´ ege vissza ´ert´ek f¨ uggv´ eny v´ ege
A ⊕ m˝ uveletet minden ciklusban egyszer v´egezz¨ uk el ´es az eredm´enyt elt´aroljuk az ´ert´ek-ben. A fut´asi id˝o n-nel ar´anyos: T (n) = O (n)
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
11 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
13 / 49
Eld¨ont´es T´ıpusfeladatok 1
D¨onts¨ uk el egy sz´or´ol a h´ onapnevek sorozata alapj´an, hogy egy h´onap neve-e!
2
D¨onts¨ uk el egy tanul´ o ´ev v´egi oszt´alyzata alapj´an, hogy kit˝ un˝o tanul´o-e!
3
J´ uniusban minden nap d´elben megm´ert¨ uk, hogy a Balaton Si´ofokn´al h´any fokos. D¨onts¨ uk el a m´er´esek alapj´an, hogy a v´ız h˝ofoka folyamatosan emelkedett-e!
4
D¨onts¨ uk el egy sz´amr´ ol, hogy pr´ımsz´am-e!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
14 / 49
Eld¨ont´es Feladat El akarjuk d¨onteni, hogy egy t¨ ombben (x) van-e legal´abb egy adott tulajdons´ag´ u (P) elem. Eredm´eny¨ ul egy logikai ´ert´eket adunk vissza, mely pontosan akkor igaz, ha tal´altunk legal´abb egy P tulajdons´ag´ u elemet az x-ben.
Megval´os´ıt´as A t¨omb¨ot bej´arjuk az elej´et˝ ol a v´ege fel´e haladva. A bej´ar´ast akkor hagyjuk abba, ha v´egigment¨ unk az o¨sszes elemen ´es nem tal´altunk egyetlen P tulajdons´ag´ u elemet sem; ha az aktu´alis elem P tulajdons´ag´ u.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
15 / 49
Eld¨ont´es Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz (t¨ omb m´erete), P − logikai (tulajdons´ag) Kimenet: van − logikai ¨ nte ´s(x, n, P) f¨ uggv´ eny Eldo i ←1 ciklus am´ıg (i ≤ n) ∧ ¬P(x[i]) i ←i +1 ciklus v´ ege van ← (i ≤ n) vissza van f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
16 / 49
Eld¨ont´es
Pszeudok´od ¨ nte ´s(x, n, P) f¨ uggv´ eny Eldo i ←1 ciklus am´ıg (i ≤ n)∧ ¬P(x[i]) i ←i +1 ciklus v´ ege van ← (i ≤ n) vissza van f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Fut´asi id˝o A P tulajdons´ ag f¨ uggv´enyt legal´ abb egyszer ´es legfeljebb n-szer ´ert´ekelj¨ uk ki. Az index n¨ ovel´eshez legrosszabb esetben n-szer ker¨ ul a vez´erl´es. A fut´ asi id˝ o: T (n) = O (n)
Programoz´ as I.
2015. szeptember 21.
17 / 49
Eld¨ont´es Megjegyz´esek A P tulajdons´ag helyes megv´alaszt´as´aval a t´etel sokf´ele szitu´aci´oban alkalmazhat´o. A ”minden elem P tulajdons´ag´ u” feladatot egyszer˝ uen visszavezethetj¨ uk az eld¨ ont´esre a P tulajdons´ag tagad´as´aval. A sorozatsz´am´ıt´asn´al megismert m´ odszerrel ellent´etben ez az algoritmus az els˝o P tulajdons´ag´ u elem megtal´al´asa ut´an m´ar nem folytatja a keres´est.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
19 / 49
Eld¨ont´es: minden elem P tulajdons´ag´u-e? Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz (t¨ omb m´erete), P − logikai (tulajdons´ag) Kimenet: van − logikai ¨ nte ´s Minden(x, n, P) f¨ uggv´ eny Eldo i ←1 ciklus am´ıg (i ≤ n) ∧ P(x[i]) i ←i +1 ciklus v´ ege van ← (i > n) vissza van f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
20 / 49
Pr´ımteszt Pszeudok´od Bemenet: N − eg´ esz (N ≥ 2) Kimenet: pr´ım − logikai 1: f¨ uggv´ eny Pr´ımTeszt(N) 2: i ←2 √ ´ ja(i, N) 3: ciklus am´ıg (i ≤ N) ∧ ¬Oszto 4: i ←i +1 5: ciklus v´ ege √ 6: pr´ım ← (i > N) 7: vissza pr´ım 8: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
21 / 49
N¨ovekv˝o rendezetts´eg vizsg´alat Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz; ahol T ¨ osszehasonl´ıthat´o Kimenet: rendezett − logikai 1: f¨ uggv´ eny Rendezett E(x, n) 2: i ←1 3: ciklus am´ıg (i ≤ n − 1) ∧ (x[i] ≤ x[i + 1]) 4: i ←i +1 5: ciklus v´ ege 6: rendezett ← (i > n − 1) 7: vissza rendezett 8: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
22 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
24 / 49
Kiv´alaszt´as T´ıpusfeladatok 1
Ismerj¨ uk egy h´onap nev´et. A h´ onapnevek sorozata alapj´an mondjuk meg a h´onap sorsz´am´at!
2
Adjuk meg egy egyn´el nagyobb term´eszetes sz´am legkisebb, 1-t˝ol k¨ ul¨onb¨oz˝o oszt´oj´at!
3
A napt´arban tal´alhat´ o n´evnapok alapj´an adjuk meg a legjobb bar´atunk n´evnapj´at!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
25 / 49
Kiv´alaszt´as Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz, P − logikai Kimenet: idx − eg´ esz ´ laszta ´ s(x, n, P) 1: f¨ uggv´ eny Kiva 2: i ←1 3: ciklus am´ıg ¬P (x[i]) 4: i ←i +1 5: ciklus v´ ege 6: idx ← i 7: vissza idx 8: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
26 / 49
Kiv´alaszt´as Megjegyz´esek Az eld¨ ont´essel ellent´etben ez visszaadja az els˝ o P tulajdons´ag´ u elem sorsz´am´at A t´etel felt´etelezi, hogy biztosan van legal´abb egy P tulajdons´ag´ u elem Sorsz´am helyett visszaadhatjuk az elem ´ert´ek´et is, de c´elszer˝ ubb a sorsz´am haszn´alata (ez alapj´an az elem is egyszer˝ uen meghat´arozhat´o) Az algoritmus m˝ uk¨od´ese ´es fut´asi ideje hasonl´ o az eld¨ont´eshez
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
27 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
28 / 49
Line´aris keres´es T´ıpusfeladatok 1
Ismerj¨ uk egy u ¨zlet egy havi forgalm´at: minden napra megadjuk, hogy mennyi volt a bev´etel ´es mennyi a kiad´as. Adjunk meg egy olyan napot – ha van –, amelyik nem volt nyeres´eges!
2
A Budapest-Nagykanizsa vas´ uti menetrend alapj´an k´et adott ´allom´ashoz adjunk meg egy olyan vonatot, amellyel el lehet jutni ´atsz´all´as n´elk¨ ul az egyikr˝ ol a m´asikra!
3
Egy tetsz˝oleges (nem 1) term´eszetes sz´amnak adjuk meg egy oszt´oj´at, ami nem az 1 ´es nem is ¨ onmaga!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
29 / 49
Line´aris keres´es Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz, P − logikai Kimenet: van − logikai, idx − eg´ esz ´ risKerese ´s(x, n, P) 1: f¨ uggv´ eny Linea 2: i ←1 3: ciklus am´ıg (i ≤ n) ∧ ¬P (x[i]) 4: i ←i +1 5: ciklus v´ ege 6: van ← (i ≤ n) 7: ha van akkor 8: idx ← i 9: vissza (van, idx) 10: k¨ ul¨ onben 11: vissza van 12: el´ agaz´ as v´ ege 13: f¨ uggv´ eny v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
30 / 49
Line´aris keres´es Megjegyz´esek Tekinthet˝o az eld¨ont´es ´es a kiv´alaszt´as t´etel ¨ otv¨ ozet´enek is: v´alaszt ad arra, hogy van-e P tulajdons´ag´ u elem a sorozatban, ´es ha van, akkor visszaadja a sorsz´am´at is. ´ Ertelemszer˝ uen nem felt´etelezi, hogy biztosan van P tulajdons´ag´ u elem a sorozatban. Ha nincs, akkor a van ´ert´eke hamis, ilyenkor az idx v´altoz´o nem kap ´ert´eket. Az algoritmus m˝ uk¨od´ese ´es fut´asi ideje hasonl´ o az eld¨ont´eshez.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
32 / 49
Adott ´ert´ek keres´ese Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz, ´ert´ek − T Kimenet: van − logikai, idx − eg´ esz ´ risKerese ´s(x, n, ´ert´ek) 1: f¨ uggv´ eny Linea 2: i ←1 3: ciklus am´ıg (i ≤ n) ∧ (x[i] 6= ´ert´ek) 4: i ←i +1 5: ciklus v´ ege 6: van ← (i ≤ n) 7: ha van akkor 8: idx ← i 9: vissza (van, idx) 10: k¨ ul¨ onben 11: vissza van 12: el´ agaz´ as v´ ege 13: f¨ uggv´ eny v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
33 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
34 / 49
Megsz´aml´al´as T´ıpusfeladatok 1
Csal´adok l´etsz´ama, illetve j¨ ovedelme alapj´an ´allap´ıtsuk meg, hogy h´any csal´ad ´el a l´etminimum alatt!
2
Egy fut´overseny id˝oeredm´enyei alapj´an hat´arozzuk meg, hogy a versenyz˝ok h´any sz´azal´eka teljes´ıtette az olimpiai indul´ashoz sz¨ uks´eges szintet!
3
Adjuk meg egy sz¨oveg mag´anhangz´ oinak sz´am´at!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
35 / 49
Megsz´aml´al´as Feladat Egy t¨ombben (x) szeretn´enk az adott tulajdons´ag´ u (P) elemek sz´am´at meghat´arozni. Kimenetk´ent a x t¨omb P tulajdons´ag´ u elemeinek sz´am´at adjuk vissza.
Megval´os´ıt´as Az x t¨ omb minden elem´et meg kell vizsg´alni, hogy P tulajdons´ag´ u-e. Emiatt sz´aml´al´os ciklussal bej´arjuk az eg´esz t¨ omb¨ot. Ha az aktu´alis t¨ombelem (x[i]) P tulajdons´ag´ u, akkor egy sz´aml´al´o (db) ´ert´ek´et eggyel n¨ ovelj¨ uk. A db sz´aml´al´onak kezdetben null´anak kell lennie.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
36 / 49
Megsz´aml´al´as Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz (t¨ omb m´erete), P − logikai (tulajdons´ag) Kimenet: db − eg´ esz (darabsz´am) ´ mla ´ la ´ s(x, n, P) f¨ uggv´ eny Megsza db ← 0 ciklus i ← 1-t˝ol n-ig ha P (x[i]) akkor db ← db + 1 el´ agaz´ as v´ ege ciklus v´ ege vissza db f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
37 / 49
Megsz´aml´al´as
Pszeudok´od ´ mla ´ la ´ s(x, n, P) f¨ uggv´ eny Megsza db ← 0 ciklus i ← 1-t˝ ol n-ig ha P (x[i]) akkor db ← db + 1 el´ agaz´ as v´ ege ciklus v´ ege vissza db f¨ uggv´ eny v´ ege
Fut´asi id˝o A P tulajdons´ag teljes¨ ul´es´et minden elemre meg kell vizsg´alni. Csak akkor n¨ovelj¨ uk db ´ert´ek´et, ha a P (x[i]) igaz volt. A fut´asi id˝ o ar´anyos a t¨omb m´eret´evel: T (n) = O (n)
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
38 / 49
Megsz´aml´al´as Megjegyz´esek Amennyiben nincs P tulajdons´ag´ u elem a sorozatban, akkor ´ertelemszer˝ uen 0 ker¨ ul a db v´altoz´ oba. Val´oj´aban egy sorozatsz´am´ıt´as, amely minden P tulajdons´ag´ u elem eset´en 1-et hozz´aad a db ´ert´ek´ehez.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
40 / 49
Tartalom
1
Programoz´asi t´etelek
2
Egyszer˝ u programoz´asi t´etelek Sorozatsz´am´ıt´as Eld¨ont´es Kiv´alaszt´as Line´aris keres´es Megsz´aml´al´as Maximumkiv´alaszt´as
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
41 / 49
Maximumkiv´alaszt´as T´ıpusfeladatok 1
Egy k´ orh´azban megm´ert´ek minden beteg l´az´at. Adjuk meg, hogy ki a legl´azasabb!
2
Egy csal´ad havi bev´etelei ´es kiad´asai alapj´an adjuk meg, hogy melyik h´onapban tudtak a legt¨ obbet megtakar´ıtani!
3
Egy oszt´aly tanul´oinak nevei alapj´an adjuk meg a n´evsorban legels˝o tanul´ot!
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
42 / 49
Maximumkiv´alaszt´as Feladat Adott egy t¨omb (x), melynek elemei ¨ osszehasonl´ıthat´oak. Keress¨ uk meg, hogy melyik elem a legnagyobb a t¨ombben.
Megval´os´ıt´as Tekints¨ uk el˝osz¨or a t¨omb els˝ o elem´et a legnagyobbnak. A legnagyobb elem index´et t´aroljuk el a max v´altoz´oban. (Ez kezdetben 1.) Egy sz´aml´al´os ciklussal j´arjuk be a t¨ omb¨ ot a m´asodik elemt˝ol az utols´oig. Ha az aktu´alis t¨ombelem (x[i]) nagyobb, mint az eddig legnagyobb elem (x[max]), akkor tekints¨ uk az aktu´alis elemet a legnagyobbnak, azaz az aktu´alis elem indexek legyen a max. Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
43 / 49
Maximumkiv´alaszt´as Pszeudok´od Bemenet: x − T t¨ omb, n − eg´ esz (t¨ omb m´erete); ahol T ¨ osszehasonl´ıthat´o Kimenet: max − eg´ esz ´ laszta ´ s(x, n) f¨ uggv´ eny Maximumkiva max ← 1 ciklus i ← 2-t˝ol n-ig ha x[i] > x[max] akkor max ← i el´ agaz´ as v´ ege ciklus v´ ege vissza max f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
44 / 49
Maximumkiv´alaszt´as
Pszeudok´od ´ laszta ´ s(x, n) f¨ uggv´ eny Maximumkiva max ← 1 ciklus i ← 2-t˝ ol n-ig ha x[i] > x[max] akkor max ← i el´ agaz´ as v´ ege ciklus v´ ege vissza max f¨ uggv´ eny v´ ege
Fut´asi id˝o Az ¨ osszehasonl´ıt´ast (n − 1)-szer v´egezz¨ uk el. Az ´ert´ekad´ashoz legfeljebb (n − 1)-szer, de lehet, hogy egyszer sem ker¨ ul a vez´erl´es. A fut´asi id˝ o ar´anyos a t¨omb m´eret´evel: T (n) = O (n)
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
45 / 49
Maximumkiv´alaszt´as Megjegyz´esek Rel´aci´ o megford´ıt´as´aval ´ertelemszer˝ uen minimumkiv´alaszt´as lesz a t´etel c´elja. Index helyett visszaadhatjuk az elem ´ert´ek´et is, de c´elszer˝ ubb az index haszn´alata (ez alapj´an az elem is azonnal meghat´arozhat´o). Felt´etelezz¨ uk, hogy legal´abb egy elem l´etezik a t¨ ombben. T¨obb maxim´alis elem eset´en az els˝ ot adja vissza.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
47 / 49
Gyakorl´o feladat Kir´andul´as sor´an 100 m´eterenk´ent feljegyezt¨ uk a tengerszint feletti magass´ag ´ert´ekeket. 1
Volt a kir´andul´as sor´an olyan szakasz, amikor s´ık terepen haladtunk?
2
H´any olyan sz´az m´eteres szakasz volt, amikor emelked˝on haladtunk? ´ a Mekkora volt a kir´andul´as sor´an a teljes szintemelked´es? (Es szintcs¨okken´es?)
3
4
H´anyszor 100 m´eteres volt az a leghosszabb szakasz, ahol folyamatosan emelked˝ on haladtunk?
5
Mekkora volt a 100 m´eter alatt megtett legnagyobb szintemelked´es?
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 21.
48 / 49
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)
Programoz´ as I.
2015. szeptember 21.
49 / 49
