Programoz´as I. 10. el˝ oad´as Rendezett t¨ omb¨ ok
Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar Alkalmazott Informatikai Int´ ezet
2014. november 10.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
1 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
2 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
3 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
4 / 53
Line´aris keres´es rendezett t¨ombben V´altoztat´asi ¨otlet A line´aris keres´esn´el a t¨ omb¨ ot az elej´et˝ ol a v´ege fel´e haladva j´arjuk be. A bej´ar´ast addig v´egezz¨ uk, am´ıg meg nem tal´aljuk a keresett elemet, illetve a t¨omb v´eg´ere nem ´er¨ unk. Rendezett t¨ omb¨ ok eset´en a bej´ar´ast befejezhetj¨ uk akkor is, ha m´ar a keresett elemn´el nagyobb elemhez jutunk.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
5 / 53
Liner´ais keres´es rendezett t¨ombben Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz (t¨ omb m´erete), ´ert´ek − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai, idx − eg´ esz ´ risKerese ´sRendezettben(x, n, ´ert´ek) f¨ uggv´ eny Linea i ←1 ciklus am´ıg (i ≤ n) ∧ (x[i] < ´ert´ek) i ←i +1 ciklus v´ ege van ← (i ≤ n) ∧ (x[i] = ´ert´ek) ha van akkor idx ← i vissza (van, idx) k¨ ul¨ onben vissza van el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
6 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
7 / 53
Logaritmikus keres´es Algoritmus ¨otlete Kiv´alasztjuk a t¨ omb k¨ oz´eps˝ o elem´et. Ha a k¨ oz´eps˝ o elem nagyobb a keresett ´ert´ekn´el, akkor az biztos a t¨ omb els˝ o fel´eben tal´ alhat´ o. Ha a k¨ oz´eps˝ o elem kisebb a keresett ´ert´ekn´el, akkor az biztos a t¨ omb m´ asodik fel´eben tal´ alhat´ o.
Folytassuk a keres´est hasonl´ o m´ odon a megfelel˝ o r´eszt¨ombben. A keres´est akkor hagyjuk abba, ha megtal´ altuk a keresett ´ert´eket, elfogyott a t¨ omb”. ”
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
8 / 53
Logaritmikus keres´es iterat´ıv megval´os´ıt´asa Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz, ´ ert´ ek − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai, idx − eg´ esz ´s(x, n, ´ f¨ uggv´ eny LogaritmikusKerese ert´ ek) bal ← 1 jobb ← n ciklus k j center ← bal+jobb 2 ha x[center ] > ´ ert´ ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ ert´ ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (x[center ] 6= ´ ert´ ek) van ← (bal ≤ jobb) ha van akkor idx ← center vissza (van, idx) k¨ ul¨ onben vissza van el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
9 / 53
Logaritmikus keres´es Fut´asi id˝o H´anyszor fut le a ciklus? Ha a k¨ oz´eps˝ o elem a keresett ´ert´ek, akkor csak egyszer. Ez a legjobb eset. A ciklus minden lefut´asakor felez˝ odik a t¨ omb. Ez h´anyszor lehets´eges? Egy n elem˝ u t¨ omb¨ ot dlog2 ne-szer lehet felezni. Legrosszabb esetben – p´eld´aul, ha keresett ´ert´ek nincs a t¨ombben – d1 + log2 ne-szer fut le a ciklus. ´ Atlagos esetben a ciklus dlog2 ne-szer fut le. A fut´asi id˝ o: T (n) = O (log n).
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
10 / 53
Logaritmikus keres´es iterat´ıv megval´os´ıt´asa Feladat Keress¨ uk meg a 12 ´ert´eket az x t¨ ombben. ´s(x, n, ´ f¨ uggv´ eny LogaritmikusKerese ert´ ek) bal ← 1 jobb ← n ciklus j k center ← bal+jobb 2 ha x[center ] > ´ ert´ ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ ert´ ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (x[center ] 6= ´ ert´ ek) van ← (bal ≤ jobb) ha van akkor idx ← center vissza (van, idx) k¨ ul¨ onben vissza van idx el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege
x:
1
3
bal Sergy´ an (OE NIK AII)
6
7
9
12
Kimenet
van = igaz; igaz idx = 6
14
17
18
19
23
25
26
28
30
center bal center jobb center
jobb
Programoz´ as I.
2014. november 10.
11 / 53
Logaritmikus keres´es rekurz´ıv megval´os´ıt´asa Pszeudok´od Bemenet: x − T rendezett t¨ omb, bal − eg´ esz, jobb − eg´ esz, ´ert´ek − T; ahol T o ¨sszehasonl´ıthat´ o Kimenet: Az ´ert´ek-kel megegyez˝ o elem indexe, illetve ha nincs ilyen, akkor 0. ´sRekurz´ıv(x, bal, jobb, ´ert´ek) f¨ uggv´ eny LogaritmikusKerese ha bal > jobb akkor vissza 0 k¨ ul¨ onben center ← bal+jobb 2 ha x[center ] = ´ert´ek akkor vissza center k¨ ul¨ onben ha x[center ] > ´ert´ek akkor ´sRekurz´ıv(x, bal, center − 1, ´ert´ek) vissza LogaritmikusKerese k¨ ul¨ onben ´sRekurz´ıv(x, center + 1, jobb, ´ert´ek) vissza LogaritmikusKerese el´ agaz´ as v´ ege el´ agaz´ as v´ ege el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
13 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
16 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
17 / 53
Eld¨ont´es Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz (t¨ omb m´erete), ´ert´ek − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai ¨ nte ´sRendezettben(x, n, ´ert´ek) f¨ uggv´ eny Eldo bal ← 1 jobb ← n ciklus k j center ← bal+jobb 2 ha x[center ] > ´ert´ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ert´ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (x[center ] 6= ´ert´ek) van ← (bal ≤ jobb) vissza van f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
18 / 53
M´odos´ıtott eld¨ont´es Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz (t¨ omb m´erete), als´ohat´ar − T, fels˝ohat´ar − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai ´ dos´ıtottEldo ¨ nte ´sRendezettben(x, n, als´ohat´ar, fels˝ohat´ar) f¨ uggv´ eny Mo bal ← 1 jobb ← n ciklus k j center ← bal+jobb 2 ha x[center ] > fels˝ ohat´ar akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < als´ ohat´ar akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ ¬ ((als´ ohat´ar ≤ x[center ]) ∧ (x[center ] ≤ fels˝ohat´ar )) van ← (bal ≤ jobb) vissza van f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
19 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
21 / 53
Kiv´alaszt´as Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz, ´ert´ek − T; ahol T ¨osszehasonl´ıthat´o Kimenet: idx − eg´ esz ´ laszta ´ sRendezettben(x, n, ´ert´ek) f¨ uggv´ eny Kiva bal ← 1 jobb ← n ciklus k j center ← bal+jobb 2 ha x[center ] > ´ert´ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ert´ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg x[center ] 6= ´ert´ek idx ← center vissza idx f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
22 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
23 / 53
Kiv´alogat´as Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz, ´ ert´ ek − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai, bal − eg´ esz, jobb − eg´ esz f¨ uggv´ eny Kiv´ alogat´ asRendezettben(x, n, ´ ert´ ek) bal ← 1 jobb ← n ciklus j k bal+jobb center ← 2 ha x[center ] > ´ ert´ ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ ert´ ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (x[center ] 6= ´ ert´ ek) van ← (bal ≤ jobb) ha van akkor bal ← center ciklus am´ıg (bal > 1) ∧ (x[bal − 1] = ´ ert´ ek) bal ← bal − 1 ciklus v´ ege jobb ← center ciklus am´ıg (jobb < n) ∧ (x[jobb + 1] = ´ ert´ ek) jobb ← jobb + 1 ciklus v´ ege vissza (van, bal, jobb) k¨ ul¨ onben vissza van el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
24 / 53
M´odos´ıtott kiv´alogat´as Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz, als´ ohat´ ar − T, fels˝ ohat´ ar − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: van − logikai, bal − eg´ esz, jobb − eg´ esz f¨ uggv´ eny M´ odos´ıtottKiv´ alogat´ asRendezettben(x, n, als´ ohat´ ar, fels˝ ohat´ ar) bal ← 1 jobb ← n ciklus k j bal+jobb center ← 2 ha x[center ] > fels˝ ohat´ ar akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < als´ ohat´ ar akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ ¬ ((als´ ohat´ ar ≤ x[center ]) ∧ (x[center ] ≤ fels˝ ohat´ ar )) van ← (bal ≤ jobb) ha van akkor bal ← center ciklus am´ıg (bal > 1) ∧ (x[bal − 1] ≥ als´ ohat´ ar ) bal ← bal − 1 ciklus v´ ege jobb ← center ciklus am´ıg (jobb < n) ∧ (x[jobb + 1] ≤ fels˝ ohat´ ar ) jobb ← jobb + 1 ciklus v´ ege vissza (van, bal, jobb) k¨ ul¨ onben vissza van el´ agaz´ as v´ ege f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
26 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
27 / 53
Megsz´aml´al´as Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz, ´ ert´ ek − T; ahol T ¨ osszehasonl´ıthat´ o Kimenet: db − eg´ esz f¨ uggv´ eny Megsz´ aml´ al´ asRendezettben(x, n, ´ ert´ ek) bal ← 1 jobb ← n ciklus j k bal+jobb center ← 2 ha x[center ] > ´ ert´ ek akkor jobb ← center − 1 k¨ ul¨ onben ha x[center ] < ´ ert´ ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (x[center ] 6= ´ ert´ ek) ha bal ≤ jobb akkor bal ← center ciklus am´ıg (bal > 1) ∧ (x[bal − 1] = ´ ert´ ek) bal ← bal − 1 ciklus v´ ege jobb ← center ciklus am´ıg (jobb < n) ∧ (x[jobb + 1] = ´ ert´ ek) jobb ← jobb + 1 ciklus v´ ege db ← jobb − bal + 1 k¨ ul¨ onben db ← 0 el´ agaz´ as v´ ege vissza db f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
28 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
29 / 53
Halmazok Halmazok reprezent´al´asa A halmazokat olyan n¨ ovekv˝ o m´ odon rendezett t¨ omb¨ okk´ent ´abr´azoljuk, amelyekben nincs ism´etl˝ od´es. Jel¨ ol´es¨ uk a pszeudok´ odban: halmaz
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
30 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
31 / 53
Halmaztulajdons´ag vizsg´alata Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz (t¨ omb m´erete); ahol T ¨osszehasonl´ıthat´o Kimenet: l − logikai f¨ uggv´ eny HalmazE(x, n) i ←2 ciklus am´ıg (i ≤ n) ∧ (x[i] 6= x[i − 1]) i ←i +1 ciklus v´ ege l ← (i > n) vissza l f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
32 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
33 / 53
Halmaz l´etrehoz´asa Pszeudok´od Bemenet: x − T rendezett t¨ omb, n − eg´ esz (t¨ omb m´erete); ahol T ¨osszehasonl´ıthat´o Kimenet: a − T halmaz, db − eg´ esz ´trehoza ´ s(x, n) f¨ uggv´ eny HalmazLe ´trehoz(T)[n] a ← Le db ← 1 a[db] ← x[1] ciklus i ← 2-t˝ ol n-ig ha x[i] 6= a[db] akkor db ← db + 1 a[db] ← x[i] el´ agaz´ as v´ ege ciklus v´ ege vissza (a, db) f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
34 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
36 / 53
Tartalmaz´as vizsg´alat Pszeudok´od Bemenet: a − T halmaz, n − eg´ esz (halmaz m´erete), ´ert´ek − T; ahol T ¨osszehasonl´ıthat´o Kimenet: l − logikai f¨ uggv´ eny TartalmazzaE(a, n, ´ert´ek) bal ← 1 jobb ← n ciklus k j center ← bal+jobb 2 ha a[center ] > ´ert´ek akkor jobb ← center − 1 k¨ ul¨ onben ha a[center ] < ´ert´ek akkor bal ← center + 1 el´ agaz´ as v´ ege am´ıg (bal ≤ jobb) ∧ (a[center ] 6= ´ert´ek) l ← (bal ≤ jobb) vissza l f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
37 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
38 / 53
R´eszhalmaz vizsg´alat Pszeudok´od Bemenet: a − T halmaz, m − eg´ esz (a m´erete), b − T halmaz, n − T halmaz (b m´erete) Kimenet: l − logikai ´szhalmaz e(a, m, b, n) f¨ uggv´ eny Re i ←1 j ←1 ciklus am´ıg (i ≤ m) ∧ (j ≤ n) ∧ (a[i] ≥ b[j]) ha a[i] = b[j] akkor i ←i +1 el´ agaz´ as v´ ege j ←j +1 ciklus v´ ege l ← (i > m) vissza l f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
39 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
42 / 53
Halmazok uni´oja Pszeudok´od Bemenet: a1 − T halmaz, n1 − eg´ esz (halmaz m´ erete), a2 − T halmaz, n2 − eg´ esz (halmaz m´ erete) Kimenet: b − T halmaz, db − eg´ esz f¨ uggv´ eny HalmazUni´ o(a1 , n1 , a2 , n2 ) b ← L´ etrehoz(T)[n1 + n2 ] i ← 1 j ← 1 db ← 0 n1 ← n1 + 1 a1 [n1 ] ← +∞ n2 ← n2 + 1 a2 [n2 ] ← +∞ ciklus am´ıg i < n1 ∨ j < n2 db ← db + 1 ha a1 [i] < a2 [j] akkor b[db] ← a1 [i] i ← i +1 k¨ ul¨ onben ha a1 [i] > a2 [j] akkor b[db] ← a2 [j] j ← j +1 k¨ ul¨ onben b[db] ← a1 [i] i ← i +1 j ← j +1 el´ agaz´ as v´ ege el´ agaz´ as v´ ege ciklus v´ ege vissza (b, db) f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
43 / 53
Halmazok uni´oja Feladat Hat´arozzuk meg az a1 ´es a2 halmazok uni´ oj´at! f¨ uggv´ eny HalmazUni´ o(a1 , n1 , a2 , n2 ) b ← L´ etrehoz(T)[n1 + n2 ] i ← 1 j ← 1 db ← 0 n1 ← n1 + 1 a1 [n1 ] ← +∞ n2 ← n2 + 1 a2 [n2 ] ← +∞ ciklus am´ıg i < n1 ∨ j < n2 db ← db + 1 ha a1 [i] < a2 [j] akkor b[db] ← a1 [i] i ← i +1 k¨ ul¨ onben ha a1 [i] > a2 [j] akkor b[db] ← a2 [j] j ← j +1 k¨ ul¨ onben b[db] ← a1 [i] i ← i +1 j ← j +1 el´ agaz´ as v´ ege el´ agaz´ as v´ ege ciklus v´ ege vissza (b, db) f¨ uggv´ eny v´ ege
a1 :
a2 :
b:
2
3
4
5
8
∞
i
i
i
i
i
i
1
3
5
7
∞
j
j
j
j
j
1
2
3
4
5
7
8
db
db
db
db
db
db
db db Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
44 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
45 / 53
Halmazok metszete Pszeudok´od Bemenet: a1 − T halmaz, n1 − eg´ esz (halmaz m´ erete), a2 − T halmaz, n2 − eg´ esz (halmaz m´ erete) Kimenet: b − T halmaz, db − eg´ esz f¨ uggv´ eny HalmazMetszet(a1 , n1 , a2 , n2 ) ´trehoz(T)[min(n1 , n2 )] b ← Le i ←1 j ←1 db ← 0 ciklus am´ıg (i ≤ n1 ) ∧ (j ≤ n2 ) ha a1 [i] < a2 [j] akkor i ←i +1 k¨ ul¨ onben ha a1 [i] > a2 [j] akkor j ←j +1 k¨ ul¨ onben db ← db + 1 b[db] ← a1 [i] i ←i +1 j ←j +1 el´ agaz´ as v´ ege ciklus v´ ege vissza (b, db) f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
46 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
48 / 53
Halmazok k¨ul¨onbs´ege Pszeudok´od Bemenet: a1 − T halmaz, n1 − eg´ esz (halmaz m´ erete), a2 − T halmaz, n2 − eg´ esz (halmaz m´ erete) Kimenet: b − T halmaz, db − eg´ esz f¨ uggv´ eny HalmazMetszet(a1 , n1 , a2 , n2 ) ´trehoz(T)[n1 ] b ← Le i ←1 j ←1 db ← 0 ciklus am´ıg (i ≤ n1 ) ∧ (j ≤ n2 ) ha a1 [i] < a2 [j] akkor db ← db + 1 b[db] ← a1 [i] i ←i +1 k¨ ul¨ onben ha a1 [i] > a2 [j] akkor j ←j +1 k¨ ul¨ onben i ←i +1 j ←j +1 el´ agaz´ as v´ ege ciklus v´ ege ciklus am´ıg i ≤ n1 db ← db + 1 b[db] ← a1 [i] i ←i +1 ciklus v´ ege vissza (b, db) f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
49 / 53
Tartalom 1
Keres´esek rendezett t¨ omb¨ okben Line´aris keres´es Logaritmikus keres´es
2
Programoz´asi t´etelek Eld¨ont´es Kiv´alaszt´as Kiv´alogat´as Megsz´aml´al´as
3
Halmazok Halmaztulajdons´ag vizsg´alata Halmaz l´etrehoz´asa Tartalmaz´as vizsg´alat R´eszhalmaz vizsg´alat Halmazok uni´ oja Halmazok metszete Halmazok k¨ ul¨ onbs´ege Halmazok szimmetrikus differenci´aja Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
51 / 53
Halmazok szimmetrikus differenci´aja Pszeudok´od Bemenet: a1 − T halmaz, n1 − eg´ esz (halmaz m´ erete), a2 − T halmaz, n2 − eg´ esz (halmaz m´ erete) Kimenet: b − T halmaz, db − eg´ esz f¨ uggv´ eny HalmazMetszet(a1 , n1 , a2 , n2 ) b ← L´ etrehoz(T)[n1 + n2 ] i ← 1 j ← 1 db ← 0 ciklus am´ıg i ≤ n1 ∧ j ≤ n2 ha a1 [i] < a2 [j] akkor db ← db + 1 b[db] ← a1 [i] i ← i +1 k¨ ul¨ onben ha a1 [i] > a2 [j] akkor db ← db + 1 b[db] ← a2 [j] j ← j +1 k¨ ul¨ onben i ← i +1 j ← j +1 el´ agaz´ as v´ ege ciklus v´ ege ciklus am´ıg i ≤ n1 db ← db + 1 b[db] ← a1 [i] i ← i +1 ciklus v´ ege ciklus am´ıg j ≤ n2 db ← db + 1 b[db] ← a2 [j] j ← j +1 ciklus v´ ege vissza (b, db) f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. november 10.
52 / 53
