Programoz´as I. 3. el˝ oad´as T¨ omb¨ ok a C#-ban Met´ odusok C#-ban Egyszer˝ u programoz´asi t´etelek
Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar Szoftvertechnol´ ogia Int´ ezet
2013. szeptember 23.
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
1 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
2 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
3 / 76
A t¨omb T¨obb, azonos t´ıpus´ u v´altoz´ o egy¨ uttes kezel´es´et teszi lehet˝ov´e
int a1; int a2; int a3; int a4; . . . helyett egyetlen ”int t¨omb” t´ıpus´ u v´altoz´o haszn´alata egy n´evvel Elemei a t¨omb¨on bel¨ uli sorsz´amukkal (index) ´erhet˝oek el (kezd˝o index: C#-ban 0, pszeudok´ odban: 1) A t¨ombben t´arolt t´ıpus ´es a t¨ omb m´erete nem m´ odos´ıthat´o → szigor´ u adatszerkezet, cser´eben nagyon gyors
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
4 / 76
T¨ombbel v´egezhet˝o tev´ekenys´egek Deklar´aci´o: a t¨omb nev´enek ´es elemei t´ıpus´anak megad´asa T¨ombl´etrehoz´as: a t¨omb m´eret´enek meghat´aroz´asa ´ ekad´as: ´ert´ek elhelyez´ese egy t¨ Ert´ ombelemben
´ ek lek´erdez´ese: egy t¨ Ert´ ombelem tartalm´anak kiolvas´asa. Az ´ert´ek a kiolvas´as ut´an is megmarad a t¨ ombelemben
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
5 / 76
T¨ombbel v´egezhet˝o tev´ekenys´egek C#-ban 1
Deklar´aci´o: int[] tomb;
2
T¨ombl´etrehoz´as: tomb = new int[10]; ´ ekad´as: tomb[5] = 25; vagy tomb[5] = 6 * 2 -29; Ert´ ´ ek lek´erdez´ese: 5 * 10 - tomb[5] + 2 Ert´
3 4
A deklar´aci´o ´es a t¨ombl´etrehoz´as ¨ ossze is vonhat´ o: int[] tomb = new int[10];
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
6 / 76
T¨ombelem el´er´ese (indexel´es) A t¨omb egy adott elem´ehez a t¨ omb neve ut´an sz¨ ogletes z´ar´ojelek k¨oz¨ott megadott sorsz´ammal (index) f´erhet¨ unk hozz´a: t¨ ombn´ ev[index] Az index csak nemnegat´ıv eg´esz sz´am lehet A t¨omb els˝o elem´enek indexe: 0 A t¨omb utols´o elem´enek indexe: elemsz´am - 1 Kisebb, vagy nagyobb index megad´asa fut´asi hib´at okoz.
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
7 / 76
T¨omb hossz´anak (elemei sz´am´anak) lek´erdez´ese ´ anos form´atum: t¨ Altal´ ombn´ ev.Length A t¨ombben l´ev˝o elemek sz´am´at adja meg
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
8 / 76
T¨omb inicializ´al´asa A t¨omb deklar´aci´oja, l´etrehoz´asa ´es elemeinek megad´asa egy utas´ıt´asban is elv´egezhet˝ o Form´atuma: t´ ıpus[] t¨ ombn´ ev = {elem1, elem2, . . ., elemN}; P´eld´ak: double[] valosak = {2.0, -3.5, 8.2, -1234.56}; bool[] logikai = {true, false, false, true, true};
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
9 / 76
T¨ombbel v´egezhet˝o tev´ekenys´egek C#-ban A tev´ekenys´egek sorrendje: 1 2 3
Deklar´aci´ o T¨ ombl´etrehoz´as ´ ekad´as egy t¨ Ert´ ombelemnek, vagy egy t¨ ombelem ´ert´ek´enek lek´erdez´ese
A fentiek k¨oz¨ ul ak´armelyik tev´ekenys´eget szeretn´enk is v´egrehajtani, el˝obb a sorrendben ˝ot megel˝ oz˝ ot kell elv´egezni A t¨ombelemeknek nem k¨ otelez˝ o ´ert´eket adni az ´ert´ek lek´erdez´ese el˝ott ´ Ert´ekad´as hi´any´aban a t¨ ombelem a t´ıpus alap´ert´ek´et veszi fel
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
10 / 76
T¨obbdimenzi´os t¨omb¨ok 2 dimenzi´os t¨omb sorok ´es oszlopok elem el´er´ese 2 indexszel
3 dimenzi´os t¨omb¨ok sorok, oszlopok, lapok elem el´er´ese 3 indexszel
N dimenzi´os t¨omb¨ok 0., 1., . . ., N. dimenzi´ o elem el´er´ese N indexszel
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
11 / 76
T¨obbdimenzi´os t¨omb¨ok – Deklar´aci´o ´ anos form´atum: t´ Altal´ ıpus[vessz˝ ok] t¨ ombn´ ev; A sz¨ogletes z´ar´ojelbe dimenzi´ osz´am - 1 darab vessz˝ot kell tenni P´eld´ak: int[,] matrix; bool[,,] haromdimenziostomb; double[,,,,] otdimenziostomb;
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
12 / 76
T¨obbdimenzi´os t¨omb¨ok – T¨ombl´etrehoz´as ´ anos form´atum: Altal´ t¨ ombn´ ev = new t´ ıpus[elemsz´ am1, . . ., elemsz´ amN]; Az egyes dimenzi´ok elemsz´amait vessz˝ okkel elv´alasztva kell megadni A deklar´aci´o ´es a t¨ombl´etrehoz´as itt is ¨ osszevonhat´o P´eld´ak matrix = new int[3, 5]; haromdimenziostomb = new bool[4, 2, 5]; int[,,] t = new int[3, 3, 3]; int[,] egeszmatrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 1, 2}};
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
13 / 76
T¨obbdimenzi´os t¨omb¨ok – T¨ombelem el´er´ese (indexel´es) A sz¨ogletes z´ar´ojelek k¨ oz´e a t¨ ombelem minden egyes dimenzi´oj´an bel¨ uli sorsz´amait kell vessz˝ okkel elv´alasztva megadni: t¨ ombn´ ev[index1, index2, . . ., indexN] Az indexekre vonatkoz´ o szab´alyok ugyanazok, mint az egydimenzi´os t¨ombn´el Pontosan annyi indexet kell megadni, ah´any dimenzi´os a t¨omb
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
14 / 76
T¨obbdimenzi´os t¨omb¨ok – T¨omb m´eret´enek lek´erdez´ese Elemek sz´am´anak lek´erdez´ese: ¨ Osszes t¨ ombben l´ev˝ o elem darabsz´ama: t¨ ombn´ ev.Length Egy adott dimenzi´ o elemsz´ama (sorok sz´ama, oszlopok sz´ama, . . .): t¨ ombn´ ev.GetLength(dimenzi´ osorsz´ am)
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
15 / 76
T¨omb bej´ar´asa – for utas´ıt´as for(inicializ´ ator; felt´ etel; iter´ ator) Az inicializ´ator ´es az iter´ator tetsz˝ oleges utas´ıt´as lehet M˝ uk¨od´ese: Bel´ep´eskor egyszer v´egrehajt´ odik az inicializ´ator Minden ciklusmenetben ki´ert´ekel˝ odik a felt´etel Amennyiben a felt´etel igaz, a ciklusmagban l´ev˝ o utas´ıt´asok egyszer v´egrehajt´ odnak A ciklusmag v´egezt´evel v´egrehajt´ odik az iter´ator ´es ism´et ki´ert´ekel˝odik a felt´etel A ciklus akkor ´er v´eget, amikor a felt´etel hamiss´a v´alik, ellenkez˝o esetben u ´jabb ciklusmenet k¨ ovetkezik
´ aban az inicializ´ator egy sz´aml´al´ Altal´ ot ´all´ıt be, az iter´ator pedig ezt a sz´aml´al´ot n¨oveli vagy cs¨ okkenti Legt¨ obbsz¨ or akkor haszn´aljuk, ha el˝ ore ismert sz´am´ u alkalommal szeretn´enk v´egrehajtani egy utas´ıt´ast
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
16 / 76
A for utas´ıt´as (p´elda) //Sz´ amm´ atrix //Ez a k¨ uls˝o ciklus fut v´ egig az ¨ osszes soron for (int i = 0; i < 100; i += 10) { //Ez a bels˝o ciklus fut v´ egig egy soron bel¨ ul //az ¨ osszes oszlopon for (int j = i; j < i + 10; j++) { Console.Write(" {0}", j); } Console.WriteLine(); }
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
17 / 76
T¨omb bej´ar´asa – foreach utas´ıt´as foreach (t´ ıpus v´ altoz´ o in gy˝ ujtem´ eny) Lehet˝ov´e teszi egy utas´ıt´as v´egrehajt´as´at egy adott gy˝ ujtem´eny ¨osszes elem´ere A ”gy˝ ujtem´eny” pontos fogalm´at k´es˝ obb r´eszletesen t´argyaljuk A t¨ omb¨ ok gy˝ ujtem´enyek, teh´at a foreach utas´ıt´as t¨omb¨okkel is haszn´alhat´ o
M˝ uk¨od´ese: Bel´ep´eskor l´etrej¨ on egy t´ ıpus t´ıpus´ u v´altoz´ o (”iter´aci´os v´altoz´o”) Ez a v´ altoz´ o csak az utas´ıt´ ason bel¨ ul haszn´ alhat´ o
Az utas´ıt´as annyiszor hajt´ odik v´egre, ah´any elemet tartalmaz a gy˝ ujtem´eny Az iter´aci´ os v´altoz´ o minden egyes v´egrehajt´asn´al felveszi a gy˝ ujtem´eny soron k¨ ovetkez˝ o elem´enek ´ert´ek´et
Az iter´aci´os v´altoz´o az utas´ıt´asban nem m´ odos´ıthat´o Erre a c´elra a for utas´ıt´as haszn´alhat´ o
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
18 / 76
A foreach utas´ıt´as (p´elda) int[] tesztt¨ omb = {1, 2, 3, 10, 20, 30, 100, 200, 300, 999}; Console.WriteLine("P´ elda a foreach utas´ ıt´ asra"); foreach (int t¨ omb´ ert´ ek in tesztt¨ omb) { Console.Write("{0} ", t¨ omb´ ert´ ek); } Console.WriteLine();
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
19 / 76
F˝ur´eszfogas t¨omb A f˝ ur´eszfogas t¨omb t¨ omb¨ ok t¨ ombje A bels˝o (azaz tartalmazott) t¨ omb¨ ok m´erete k¨ ul¨ onb¨oz˝o lehet A bels˝o t¨omb¨ok m´eret´enek fels˝ o hat´ar´at minden egyes bels˝o t¨omb k¨ ul¨on-k¨ ul¨on meg kell adni
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
20 / 76
F˝ur´eszfogas t¨omb int[][] myJagArray = new int[5][]; for (int i = 0; i < myJagArray.Length; i++) myJagArray[i] = new int[i+7]; for (int i = 0; i < 5; i++) { for (int j = 0; j < myJagArray[i].Length; j++) Console.Write(myJagArray[i][j] + " "); Console.WriteLine(); }
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
21 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
22 / 76
Met´odusok A met´odus egy k´odblokk, amely utas´ıt´asok sorozat´at tartalmazza A program az´altal futtatja ezt a k´ odblokkot, hogy megh´ıvja a met´odust ´es megszabja a sz¨ uks´eges param´etereit C#-ban minden futtatand´ o utas´ıt´as egy met´ odusban helyezkedik el Eddig programjainkat a Main() met´ odusba ´ırtuk
A t¨obbsz¨or haszn´alt k´ odr´eszeket ´ırjuk met´ odusba ”Copy-Paste” helyett C´elszer˝ u a hossz´ u met´ odusok feldarabol´asa az egyszer˝ ubb ´ertelmez´es c´elj´ab´ ol
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
23 / 76
Met´odusok Szintaktika visszat´ er´ esi t´ ıpus met´ odusn´ ev(param´ eterek) {met´ odust¨ orzs}
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
24 / 76
Met´odusok t´ıpusa A t´ıpus a visszaadott ´ert´ek t´ıpusa vagy void, ha nem adunk vissza semmit Egy met´odusnak legfeljebb egy visszat´er´esi ´ert´eke van de az lehet t¨ omb is
A visszat´er´esi ´ert´ek t´ıpus el˝ ott ´allhatnak k¨ ul¨ onf´ele m´odos´ıt´ok Pl. static, abstract, override, new, illetve l´athat´os´agot jelz˝o kulcsszavak
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
25 / 76
Met´odust¨orzs A met´odushoz tartoz´ o utas´ıt´asok, amelyek haszn´alhatj´ak a met´odusnak ´atadott param´etereket A met´odus visszat´er´esi ´ert´ek´et a return kulcssz´ o ut´an adjuk meg. Ennek hat´as´ara a met´ odusb´ ol azonnal visszat´er¨ unk a h´ıv´ohoz, akkor is, ha m´eg vannak tov´abbi utas´ıt´asok a return ut´an. Ha a met´odus t¨obb ´agon is v´eget ´erhet, akkor minden ´ag v´eg´ere kell return Visszat´er´esi ´ert´ek n´elk¨ uli (void) met´ odusn´al – ha a program mindig a met´odust¨orzs fizikai v´eg´en´el fejez˝ odik be – a return utas´ıt´as elhagyhat´o
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
26 / 76
V´altoz´ok hat´ok¨ore Egy blokkban deklar´alt v´altoz´ ok csak a deklar´al´ast´ol kezdve a blokk v´eg´eig el´erhet˝ok K¨ ovetkezm´eny: az egyik met´ odusban deklar´alt x v´altoz´o nem ugyanaz, mint a m´asik met´ odusbeli x v´altoz´ o
A h´ıv´o k¨ornyezet v´altoz´ oi nem ´erhet˝ ok el a met´ odusban Ez´ert sz¨ uks´eges a param´eter ´atad´as ´es a visszat´er´esi ´ert´ek K¨ oz¨ os adat haszn´alhat´ o: glob´alis v´altoz´ ok, de haszn´alatuk nem javasolt
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
27 / 76
Egyszer˝u p´elda T´eglalap ter¨ulet´enek sz´am´ıt´asa static int ter¨ ulet(int a, int b) //param´ eterek ´ atad´ asa { return a * b; } static void Main() { int egyikOldal = 5; int m´ asikOldal = 7; Console.WriteLine("A t´ eglalap ter¨ ulete: " + ter¨ ulet(egyikOldal, m´ asikOldal)); }
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
28 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
29 / 76
Programoz´asi t´etelek A programoz´asi t´etelek j´ ol megv´alasztott, egyszer˝ u feladatok megold´asai Seg´ıts´eg¨ ukkel a gyakorlatban sz¨ uks´eges 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 Egy sorozathoz egy ´ert´eket rendel˝ o feladatok Egy sorozathoz egy sorozatot rendel˝ o feladatok Egy sorozathoz t¨ obb sorozatot rendel˝ o feladatok T¨ obb sorozathoz egy sorozatot rendel˝ o feladatok
Feldolgozand´o intervallum alapj´an megk¨ ul¨ onb¨ oztet¨ unk R¨ ogz´ıtett intervallumos programoz´asi t´eteleket Felt´etelig tart´ o programoz´asi t´eteleket (ezeket a v´altozatokat nem t´argyaljuk) Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
30 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
31 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
32 / 76
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.
2013. szeptember 23.
33 / 76
Sorozatsz´am´ıt´as Bemenet A: N:
Kimenet
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama
R:
M˝ uvelet eredm´enye
Pszeudok´od Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R ← R0 Ciklus i ← 1-t˝ ol N-ig R ← R m˝ uvelet A[i] Ciklus v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
34 / 76
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 f¨ uggv´enyek sorozat´ara Az indul´askor haszn´alt null´ert´eket ´ertelemszer˝ uen a k´erd´eses f¨ uggv´eny (esetleg a feladat) alapj´an kell megv´alasztani
R0 m˝ uvelet
Sergy´ an (OE NIK)
¨osszegz´es 0 R ← R + A[i]
faktori´alis 1 R ← R ∗ A[i]
Programoz´ as I.
elemek uni´oja {} R ← R ∪ A[i]
2013. szeptember 23.
35 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R 1
2
3
5
8 13
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=0 1
2
3
5
Sergy´ an (OE NIK)
8 13
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=0 1
2
3
5
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=1 1
2
3
5
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=1 1
2
3
5
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=3 1
2
3
5
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=3 1
2
3
5
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=6 1
2
3
5
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R=6 1
2
3
5
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R = 11 1
2
3
5
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R = 11 1
2
3
5
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R = 19 1
2
3
5
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R = 19 1
2
3
5
8 13 i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Sorozat elemeinek ¨osszegz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R←0 Ciklus i ← 1-t˝ ol N-ig R ← R + A[i] Ciklus v´ ege Elj´ ar´ as v´ ege R = 32 1
2
3
5
8 13 i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
36 / 76
Fut´asi id˝o elemz´ese Elj´ ar´ as Sorozatsz´am´ıt´as(A, N, R) R ← R0 1 ´ert´ekad´as Ciklus i ← 1-t˝ ol N-ig 1 + N ´ert´ekad´as ´es N + 1 ¨osszeh. R ← R m˝ uvelet A[i] Ciklus v´ ege Elj´ ar´ as v´ ege
N ´ert´ekad´as
A fut´asi id˝ o minden esetben: T (N) = 1 + 2(N + 1) + N = 3N + 3 = O(N)
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
37 / 76
Sorozatsz´am´ıt´as ¨ Osszegz´ es Bemenet: X – sz´amokat tartalmaz´ o t¨ omb N – t¨omb elemsz´ama Kimenet: S – t¨omb elemeinek ¨ osszege
¨ Elj´ ar´ as Osszegz´ es(N, X , S) S ←0 Ciklus i ← 1-t˝ ol N-ig S ← S + X [i] Ciklus v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
38 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
39 / 76
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.
2013. szeptember 23.
40 / 76
Eld¨ont´es Bemenet A: N: T:
Kimenet
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama Tulajdons´ag f¨ uggv´eny
VAN:
Logikai v´altoz´o
Pszeudok´od Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
41 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
42 / 76
D¨onts¨uk el, hogy egy sorozatban van-e p´aros sz´am! Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege 1
3
5
7
8 13
Sergy´ an (OE NIK)
VAN ← true
Programoz´ as I.
2013. szeptember 23.
42 / 76
Eld¨ont´es Megjegyz´esek A T tulajdons´ag helyes megv´alaszt´as´aval a t´etel sokf´ele szitu´aci´oban alkalmazhat´o A ”minden elem T tulajdons´ag´ u” feladatot egyszer˝ uen visszavezethetj¨ uk az eld¨ ont´esre a T tulajdons´ag tagad´as´aval A sorozatsz´am´ıt´asn´al megismert m´ odszerrel ellent´etben ez az algoritmus az els˝o T tulajdons´ag´ u elem megtal´al´asa ut´an m´ar nem folytatja a keres´est
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
43 / 76
Eld¨ont´es: minden elem T tulajdons´ag´u-e? Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i > N) Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
44 / 76
Fut´asi id˝o elemz´ese Legrosszabb eset Legrosszabb esetnek azt tekinthetj¨ uk, amikor nincs a t¨ombben T tulajdons´ag´ u elem, hiszen ilyenkor az eg´esz t¨ omb¨ ot be kell j´arnunk. Elj´ ar´ as Eld¨ont´es(A, N, T , VAN) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Elj´ ar´ as v´ ege
1 ´ert´ekad´as N +1 ¨ osszeh.
N ¨osszeh.
N ´ert´ekad´as 1 ´ert´ekad´as ´es 1 ¨osszeh.
T (N) = 1 + N + 1 + N + N + 2 = 3N + 4 = O(N)
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
45 / 76
Fut´asi id˝o elemz´ese Legjobb eset Ez az eset akkor ´all el˝o, ha r¨ ogt¨ on az els˝ o elem T tulajdons´ag´ u T (N) = 1 + 1 + 1 + 0 + 2 = 5 = O(1)
´ Atlagos eset T (N) = 1 +
Sergy´ an (OE NIK)
3N N N N N + 3 = O( ) = O(N) + + + 2 = 2 2 2 2 2
Programoz´ as I.
2013. szeptember 23.
46 / 76
Eld¨ont´es Pr´ımteszt Bemenet: N – pozit´ıv eg´esz sz´am (legal´abb 2) Kimenet: PRIM – logikai v´altoz´ o; pontosan akkor igaz, ha N pr´ımsz´am
Elj´ ar´ as Eld¨ont´es(N, PRIM) i ←2 Ciklus am´ıg (i ≤ N − 1) ´es ¬(i oszt´ oja N-nek) i ←i +1 Ciklus v´ ege PRIM ← (i > N − 1) Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
47 / 76
Eld¨ont´es Monoton n¨oveked´es Bemenet: X – feldolgozand´ o t¨ omb N – X elemsz´ama Kimenet: MONOTON – logikai v´altoz´ o; pontosan akkor igaz, ha X elemei monoton n¨ oveked˝oek
Elj´ ar´ as Eld¨ont´es(N, X , MONOTON) i ←1 Ciklus am´ıg (i ≤ N − 1) ´es (X [i] ≤ X [i + 1]) i ←i +1 Ciklus v´ ege MONOTON ← (i > N − 1) Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
48 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
49 / 76
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.
2013. szeptember 23.
50 / 76
Kiv´alaszt´as Bemenet A: N: T:
Kimenet
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama Tulajdons´ag f¨ uggv´eny
SORSZ :
Els˝o T tulajdons´ag´ u elem indexe
Pszeudok´od Elj´ ar´ as Kiv´alaszt´as(A, N, T , SORSZ ) i ←1 Ciklus am´ıg ¬T (A[i]) i ←i +1 Ciklus v´ ege SORSZ ← i Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
51 / 76
Kiv´alaszt´as Megjegyz´esek Az eld¨ ont´essel ellent´etben ez visszaadja az els˝ o T tulajdons´ag´ u elem sorsz´am´at A t´etel felt´etelezi, hogy biztosan van legal´abb egy T 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.
2013. szeptember 23.
52 / 76
Kiv´alaszt´as Legjobb bar´at n´evnapja Bemenet: X – keresztneveket ´es a hozz´ajuk tartoz´ o n´evnapokat tartalmaz´ o t¨ omb N – X elemeinek sz´ama BARAT – legjobb bar´atunk keresztneve Kimenet: NAP – legjobb bar´atunk n´evnapja
Elj´ ar´ as Kiv´alaszt´as(N, X , BARAT , NAP) i ←1 Ciklus am´ıg (X [i].nev 6= BARAT ) i ←i +1 Ciklus v´ ege NAP ← X [i].nevnap Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
53 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
54 / 76
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.
2013. szeptember 23.
55 / 76
Line´aris keres´es Bemenet A: N: T:
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama Tulajdons´ag f¨ uggv´eny
Kimenet VAN: SORSZ :
Logikai v´altoz´o Els˝o T tulajdons´ag´ u elem indexe
Pszeudok´od Elj´ ar´ as Keres´es(A, N, T , VAN, SORSZ ) i ←1 Ciklus am´ıg (i ≤ N) ´es ¬T (A[i]) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Ha VAN akkor SORSZ ← i El´ agaz´ as v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
56 / 76
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 T tulajdons´ag´ u elem a sorozatban, ´es ha van, akkor visszaadja a sorsz´am´at is. ´ Ertelemszer˝ uen nem felt´etelezi, hogy biztosan van T tulajdons´ag´ u elem a sorozatban. Ha nincs, akkor a VAN ´ert´eke hamis, ilyenkor a SORSZ 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.
2013. szeptember 23.
57 / 76
Line´aris keres´es Nem nyeres´eges nap Bemenet: K – kiad´asok t¨ ombje B – bev´etelek t¨ombje N – K ´es B elemeinek sz´ama Kimenet: VAN – logikai v´altoz´ o; pontosan akkor igaz, ha van nem nyeres´eges nap SORSZ – a nem nyeres´eges nap (ha van ilyen!) sorsz´ama Elj´ ar´ as Keres´es(K , B, N, VAN, SORSZ ) i ←1 Ciklus am´ıg (i ≤ N) ´es (B[i] − K [i] > 0) i ←i +1 Ciklus v´ ege VAN ← (i ≤ N) Ha VAN akkor SORSZ ← i El´ agaz´ as v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
58 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
59 / 76
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.
2013. szeptember 23.
60 / 76
Megsz´aml´al´as Kimenet
Bemenet A: N: T:
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama Tulajdons´ag f¨ uggv´eny
DB:
T tulajdons´ag´ u elemek sz´ama
Pszeudok´od Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
61 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
Sergy´ an (OE NIK)
6
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
Sergy´ an (OE NIK)
6
DB ← 0
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 0
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 0
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 0
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =1
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 1
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 2
i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 2
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 2
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 2
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 3
i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
P´aros sz´amok megsz´amol´asa Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 3
6
DB ← 4
i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
62 / 76
Megsz´aml´al´as Megjegyz´esek Amennyiben nincs T 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 T tulajdons´ag´ u elem eset´en 1-et hozz´aad a DB ´ert´ek´ehez
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
63 / 76
Fut´asi id˝o elemz´ese Legrosszab eset Fut´asi id˝o szempontj´ab´ol a legrosszabb esetnek azt tekinthetj¨ uk, ha minden elem T tulajdons´ag´ u, mert ilyenkor minden esetben DB-t is n¨ oveln¨ unk kell Elj´ ar´ as Megsz´aml´al´as(A, N, T , DB) DB ← 0 1 ´ert´ekad´as Ciklus i ← 1-t˝ ol N-ig 1 + N ´ert´ekad´as ´es N + 1 ¨osszeh. Ha T (A[i]) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege
N ¨ osszeh. N ´ert´ekad´as
T (N) = 1 + 2(N + 1) + N + N = 4N + 3 = O(N) Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
64 / 76
Fut´asi id˝o elemz´ese Legjobb eset Legjobb esetnek azt tekinthetj¨ uk, amikor egyetlen T tulajdons´ag´ u elem sincs a t¨ombben T (N) = 1 + 2(N + 1) + N + 0 = 3N + 3 = O(N)
´ Atlagos eset T (N) = 1 + 2(N + 1) + N +
Sergy´ an (OE NIK)
Programoz´ as I.
7N N = + 3 = O(N) 2 2
2013. szeptember 23.
65 / 76
Megsz´aml´al´as Olimpiai indul´asi szintet teljes´ıt˝o fut´ok sz´azal´ekos ar´anya Bemenet: ID – Fut´ok id˝ oeredm´enyeit tartalmaz´ o t¨ omb N – ID elemeinek sz´ama SZINT – Olimpiai indul´ashoz sz¨ uks´eges fels˝o id˝okorl´at Kimenet: SZAZ – ID elemei k¨ oz¨ ul a SZINT ´ert´eket meg nem halad´ok sz´azal´ekos ar´anya Elj´ ar´ as Megsz´aml´al´as(N, ID, SZINT , SZAZ ) DB ← 0 Ciklus i ← 1-t˝ ol N-ig Ha (ID[i] ≤ SZINT ) akkor DB ← DB + 1 El´ agaz´ as v´ ege Ciklus v´ ege SZAZ ← Kerek´ıt(100 ∗ DB/N) Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
66 / 76
Tartalom 1
T¨ omb¨ok a C#-ban
2
Met´odusok C#-ban
3
Programoz´asi t´etelek
4
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.
2013. szeptember 23.
67 / 76
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.
2013. szeptember 23.
68 / 76
Maximumkiv´alaszt´as Bemenet A: N:
Feldolgozand´o t¨omb T¨omb elemeinek sz´ama
Kimenet MAX :
Maxim´alis elem indexe
Pszeudok´od Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
69 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege 2
7
4 10 13 6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 1
2
7
4 10 13 6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 1
2
7
4 10 13 6
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 1
2
7
4 10 13 6
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 2
2
7
4 10 13 6
i =2
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 2
2
7
4 10 13 6 i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 2
2
7
4 10 13 6 i =3
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 2
2
7
4 10 13 6 i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 2
2
7
4 10 13 6 i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 4
2
7
4 10 13 6 i =4
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 4
2
7
4 10 13 6 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 4
2
7
4 10 13 6 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 5
2
7
4 10 13 6 i =5
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 5
2
7
4 10 13 6 i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 Ciklus i ← 2-t˝ ol N-ig Ha A[i] > A[MAX ] akkor MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege MAX = 5
2
7
4 10 13 6 i =6
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
70 / 76
Maximumkiv´alaszt´as Megjegyz´esek Rel´aci´ o megford´ıt´as´aval ´ertelemszer˝ uen minimumkiv´alaszt´as lesz a t´etel c´elja 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 azonnal meghat´arozhat´o) Felt´etelezz¨ uk, hogy legal´abb egy elem l´etezik a list´aban T¨obb maxim´alis elem eset´en az els˝ ot adja vissza
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
71 / 76
Fut´asi id˝o elemz´ese Legrosszabb eset Fut´asi id˝o szempontj´ab´ol a legrosszabb eset, ha n¨ ovekv˝o m´odon rendezett a sorozat, mert ´ıgy minden esetben m´ odos´ıtani kell MAX ´ert´ek´et. Elj´ ar´ as Maximumiv´alaszt´as(A, N, MAX ) MAX ← 1 1 ´ert´ekad´as Ciklus i ← 2-t˝ ol N-ig N ´ert´ekad´as ´es N ¨osszeh. Ha A[i] > A[MAX ] akkor N − 1 ¨ osszeh. MAX ← i El´ agaz´ as v´ ege Ciklus v´ ege Elj´ ar´ as v´ ege
N − 1 ´ert´ekad´as
T (N) = 1 + 2N + N − 1 + N − 1 = 4N − 1 = O(N) Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
72 / 76
Fut´asi id˝o elemz´ese Legjobb eset Ha az els˝o elem a legnagyobb, akkor MAX ´ert´ek´et soha nem kell m´ odos´ıtani T (N) = 1 + 2N + N − 1 + 0 = 3N = O(N)
´ Atlagos eset T (N) = 1 + 2N + N − 1 +
Sergy´ an (OE NIK)
Programoz´ as I.
7N N = O(N) = 2 2
2013. szeptember 23.
73 / 76
Maximumkiv´alaszt´as N´evsorban legels˝o tanul´o Bemenet: X – feldolgozand´ o t¨ omb N – X elemeinek sz´ama Kimenet: MIN – X (els˝ o) legkisebb elem´enek indexe NEV – X – legkisebb elem´enek ´ert´eke Elj´ ar´ as Minimumkiv´alaszt´as(X , N, MIN, NEV ) MIN ← 1 Ciklus i ← 2-t˝ ol N-ig Ha X [MIN] > X [i] akkor MIN ← i El´ agaz´ as v´ ege Ciklus v´ ege NEV ← X [MIN] Elj´ ar´ as v´ ege Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
74 / 76
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.
2013. szeptember 23.
75 / 76
Felhaszn´alt irodalom Kor´abbi ´evek OOP diasorai Szl´avi P´eter, Zsak´o L´aszl´ o: M´ odszeres programoz´as: Programoz´asi t´etelek (Mikrol´ogia 19). ELTE TTK, 2002 Andrew Troelsen: A C# 2008 ´es a .NET 3.5. Szak Kiad´o, 2009
Sergy´ an (OE NIK)
Programoz´ as I.
2013. szeptember 23.
76 / 76
