A programoz\u00e1ssal sokszor az a baj \u2013 f\u0151leg ha k\u00f6telez\u0151 tant\u00e1rgy \u00e9s nem szeretj\u00fck \u2013 hogy gondolkodni kell. Igaz, mondhatn\u00e1m ezt a matematik\u00e1ra, fizik\u00e1ra is, de egyik tant\u00e1rgy sem annyira szerte\u00e1gaz\u00f3 a helyes megold\u00e1sok tekintet\u00e9ben, mint a programoz\u00e1s. Itt ugyanazt a probl\u00e9m\u00e1t sokf\u00e9lek\u00e9pp meg lehet oldani, \u00e9s minden megold\u00e1s helyes. M\u00e9gis, a megold\u00e1sok k\u00f6z\u00f6tt az \u00e1rnyalatnyi k\u00fcl\u00f6nbs\u00e9gek azok, amelyek eld\u00f6ntik azt, hogy helyes-e a megold\u00e1s, vagy sem.<\/p>\n
B\u00e1rmilyen bonyolult programot vesz\u00fcnk szem\u00fcgyre \u00e9s bontunk r\u00e9szekre, a v\u00e9g\u00e9n ugyanaz a 4 \u00e9p\u00edt\u0151elem marad:<\/p>\n
A sorrend nem v\u00e9letlen, ebben a sorrendben kell ezeket megtanulni haszn\u00e1lni, mert ezek egym\u00e1sra \u00e9p\u00fcl\u0151 darabok a programoz\u00e1snak nevezett kirak\u00f3 j\u00e1t\u00e9kban. Ha nem az \u00e9p\u00edt\u0151elemeit n\u00e9zz\u00fck a programoknak, akkor is tal\u00e1lhatunk olyan sablonokat, olyan m\u00e1r tanult megold\u00e1sokat, amelyek \u00fajra \u00e9s \u00fajra el\u0151fordulnak a programjainkban. Ezeket a sablonokat, k\u00e9sz megold\u00e1sokat nevezz\u00fck programoz\u00e1si t\u00e9teleknek.<\/p>\n
Ezek val\u00f3j\u00e1ban betanulhat\u00f3 k\u00e9sz algoritmusok, melyek egy adott probl\u00e9m\u00e1ra k\u00e9sz megold\u00e1st adnak. Nem mindig fordulnak el\u0151 tiszta form\u00e1ban, vagyis n\u00e9ha apr\u00f3 v\u00e1ltoztat\u00e1sokra sz\u00fcks\u00e9g van, hogy ezeket az algoritmusokat egy adott feladathoz igaz\u00edtsuk, de ha ezeket ismerj\u00fck \u00e9s biztosan haszn\u00e1ljuk, akkor sokf\u00e9le programoz\u00e1si feladatot meg tudunk oldani.<\/p>\n
Ezek az alap algoritmusok t\u00f6mb\u00f6kh\u00f6z kapcsol\u00f3dnak, vagyis sok egyforma adattal v\u00e9geznek valamit. Megkeresik egy t\u00f6mbb\u0151l a legnagyobb \u00e9rt\u00e9ket, sorba rendezik a sz\u00e1mokat, eld\u00f6ntik, hogy benne van-e egy adott \u00e9rt\u00e9k a t\u00f6mbben, megadj\u00e1k k\u00e9t halmaz metszet\u00e9t, stb. L\u00e1ssunk akkor n\u00e9h\u00e1ny alap algoritmust:<\/p>\n
Ezen algoritmusok mindegyik\u00e9re igaz, hogy ciklusokhoz kapcsol\u00f3dnak, hiszen ha t\u00f6mb\u00f6kkel dolgozunk, akkor mindenk\u00e9ppen ciklusra van sz\u00fcks\u00e9g, hogy az elemeket egyenk\u00e9nt megvizsg\u00e1lhassuk, \u00f6sszehasonl\u00edthassuk, stb. Ezek az algoritmusok kicsit leegyszer\u0171s\u00edtik a programoz\u00e1st, hiszen ezekkel a megtanulhat\u00f3 k\u00e9sz receptekkel sokf\u00e9le feladatot megoldhatunk. A probl\u00e9ma az, hogy a feladatban fel kell ismerni, hogy val\u00f3j\u00e1ban mit is akarunk eredm\u00e9nyk\u00e9nt megkapni, \u00e9s az melyik algoritmusnak felel meg. Ha ez megvan, onnant\u00f3l szinte csak g\u00e9pel\u00e9si feladatt\u00e1 siker\u00fclt egyszer\u0171s\u00edteni a programoz\u00e1si feladatot.<\/p>\n
Az alap algoritmusok valamennyi fajt\u00e1j\u00e1hoz l\u00e9tezik pszeudok\u00f3d, olyan \u00e1ltal\u00e1nos le\u00edr\u00e1s, amely programoz\u00e1si nyelvt\u0151l f\u00fcggetlen. R\u00e1ad\u00e1sul, mivel 3 fajta ciklus l\u00e9tezik, ez\u00e9rt alapb\u00f3l szerte\u00e1gaz\u00f3 megold\u00e1sokat adhatunk ugyanarra a feladatra. Az alap algoritmusokat nagyon sok helyen ugyanazzal a megold\u00e1si form\u00e1val adj\u00e1k meg, \u00e9s biztos vagyok benne, hogy t\u00f6bb tan\u00e1r csak \u00edgy fogadja el megold\u00e1sk\u00e9nt. \u00c9n azt vallom, hogy b\u00e1rmilyen j\u00f3 megold\u00e1s elfogadhat\u00f3, a l\u00e9nyeg, hogy a di\u00e1k alkalmazni tudja azt, amit tanult. L\u00e9teznek lecsupasz\u00edtott, hat\u00e9kony \u00e9s egyszer\u0171 megold\u00e1sok, de sokszor \u00e9n sem azt alkalmazom, mert nem \u00edrunk olyan szint\u0171 programokat, hogy ennyire optimaliz\u00e1lt \u00e9s gyors algoritmusra lenne sz\u00fcks\u00e9g. Aki esetleg az alap algoritmusaimban hib\u00e1t tal\u00e1l, mondv\u00e1n, hogy \u0151 ezt nem \u00edgy tanulta, az nem felt\u00e9tlen\u00fcl hiba, egyszer\u0171en m\u00e1s a megold\u00e1s. Az p\u00e9ld\u00e1kn\u00e1l sok helyen k\u00e9sz t\u00e9nynek veszem azt, hogy rendelkez\u00e9sre \u00e1ll az a t\u00f6mb a megfelel\u0151 adatokkal, amelyekkel dolgozni kell. Ezeknek a t\u00f6mb\u00f6knek a felt\u00f6lt\u00e9s\u00e9vel, ellen\u0151rz\u00e9s\u00e9vel nem foglalkozok. Vegy\u00fck akkor sorra ezeket az algoritmusokat:<\/p>\n
Kezdj\u00fck valami egyszer\u0171vel. Az alapfeladat az, hogy sz\u00e1moljuk meg, hogy egy adott t\u00f6mbben h\u00e1ny darab adott tulajdons\u00e1g\u00fa elem van. Ez jelentheti azt is, hogy nincs ilyen tulajdons\u00e1g\u00fa elem a t\u00f6mbben, akkor a darabsz\u00e1m nyilv\u00e1n 0. Enn\u00e9l a feladatn\u00e1l minden esetben v\u00e9gig kell menni a t\u00f6mb\u00f6n, hiszen minden elemr\u0151l meg kell \u00e1llap\u00edtanom, hogy rendelkezik-e a tulajdons\u00e1ggal, vagy sem. Mivel megsz\u00e1molunk, ez\u00e9rt valahol t\u00e1rolnom kell, hogy \u00e9ppen hol j\u00e1rok a sz\u00e1mol\u00e1sban, h\u00e1ny olyat tal\u00e1ltam, ami megfelelt a felt\u00e9telemnek. Ehhez sz\u00fcks\u00e9g van egy \u00fagynevezett gy\u0171jt\u0151v\u00e1ltoz\u00f3ra. Az adott algoritmus egy darabsz\u00e1mot ad eredm\u00e9ny\u00fcl minden esetben, ami a [0;m\u00e9ret] intervallumban lesz, vagyis lehet, hogy egy elem sem felel meg a felt\u00e9telnek, de az is el\u0151fordulhat, hogy mindegyik. N\u00e9zz\u00fcnk p\u00e1r p\u00e9ld\u00e1t, hogy mikor alkalmazhat\u00f3 ez az algoritmus:<\/p>\n
L\u00e1thatjuk, hogy minden esetben egy darabsz\u00e1mra k\u00edv\u00e1ncsi minden k\u00e9rd\u00e9s. L\u00e1ssuk akkor azt az algoritmust, ami ezekre a k\u00e9rd\u00e9sekre v\u00e1laszt ad. A p\u00e9ld\u00e1ban az els\u0151 k\u00e9rd\u00e9sre keress\u00fck a v\u00e1laszt.<\/p>\n
\r\nint szamlalo = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] > 180 )\r\n {\r\n szamlalo = szamlalo + 1;\r\n }\r\n}\r\n\r\nSystem.out.println("Az osztalyba "+szamlalo+" db 180 cm-nel "\r\n "magasabb diak jar.");\r\n<\/pre>\nN\u00e9zz\u00fck akkor r\u00e9szletesebben, mi t\u00f6rt\u00e9nik.<\/p>\n
\n- Deklar\u00e1lunk egy gy\u0171jt\u0151v\u00e1ltoz\u00f3t, ahol a felt\u00e9telnek megfelel\u0151 elemek darabsz\u00e1m\u00e1t t\u00e1roljuk.<\/li>\n
- A gy\u0171jt\u0151v\u00e1ltoz\u00f3t 0 kezd\u0151\u00e9rt\u00e9kre \u00e1ll\u00edtjuk be. Ez egy\u00e9bk\u00e9nt \u00e1ltal\u00e1nos szab\u00e1ly, hogy minden gy\u0171jt\u0151v\u00e1ltoz\u00f3t legk\u00e9s\u0151bb a haszn\u00e1lata el\u0151tt (a ciklus el\u0151tt) null\u00e1zni kell!<\/li>\n
- Ind\u00edtunk egy ciklust, ami a t\u00f6mb \u00f6sszes elem\u00e9n v\u00e9gigmegy.<\/li>\n
- Megvizsg\u00e1ljuk, hogy az adott elem megfelel-e a felt\u00e9telnek<\/li>\n
- Ha megfelel, a sz\u00e1ml\u00e1l\u00f3t eggyel megn\u00f6velj\u00fck.<\/li>\n
- A ciklus ut\u00e1n ki\u00edrjuk az eredm\u00e9nyt.<\/li>\n<\/ol>\n
A kiemelt sorban a v\u00e1ltoz\u00f3 n\u00f6vel\u00e9s\u00e9t kicser\u00e9lhetj\u00fck a m\u00e1r tanult inkrement\u00e1l\u00f3 oper\u00e1torra. Az\u00e9rt, mert lust\u00e1k vagyunk, \u00e9s nem akarunk sokat g\u00e9pelni \ud83d\ude42<\/p>\n
\r\nszamlalo = szamlalo + 1;\r\nhelyett\r\nszamlalo++;\r\n<\/pre>\nA t\u00f6bbi feladatn\u00e1l gyakorlatilag ugyanezt kell beg\u00e9pelni, igaz\u00e1b\u00f3l az egyetlen dolog ami v\u00e1ltozik az maga a felt\u00e9tel, ami alapj\u00e1n megsz\u00e1molunk.<\/p>\n
<\/a>\u00d6sszegz\u00e9s<\/h2>\nAz \u00f6sszegz\u00e9s t\u00e9tele k\u00eds\u00e9rtetiesen hasonl\u00edt a megsz\u00e1ml\u00e1l\u00e1sra. Egyetlen k\u00fcl\u00f6nbs\u00e9g van csak, a gy\u0171jt\u0151v\u00e1ltoz\u00f3 n\u00f6vel\u00e9se. A feladatok is hasonl\u00f3ak, de az \u00f6sszegz\u00e9s csak sz\u00e1mszer\u0171 adatokra vonatkozik. N\u00e9h\u00e1ny p\u00e9lda ilyen k\u00e9rd\u00e9sekre:<\/p>\n
\n- Mennyi a t\u00f6mbben tal\u00e1lhat\u00f3 p\u00e1ros sz\u00e1mok \u00f6sszege?<\/li>\n
- Mennyi a negat\u00edv sz\u00e1mok \u00f6sszege?<\/li>\n
- Mennyi a p\u00e1ratlan sz\u00e1mok \u00e1tlaga?<\/li>\n<\/ul>\n
L\u00e1ssuk akkor mondjuk az els\u0151 megold\u00e1s\u00e1t:<\/p>\n
\r\nint osszeg = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 == 0 )\r\n {\r\n osszeg = osszeg + tomb[i];\r\n }\r\n}\r\n\r\nSystem.out.println("A tombben levo paros szamok osszege: "+osszeg);\r\n<\/pre>\nL\u00e1thatjuk, hogy az \u00f6sszegz\u00e9s algoritmusa szinte ugyanaz, mint a megsz\u00e1ml\u00e1l\u00e1s\u00e9.<\/p>\n
\n- Deklar\u00e1lunk egy gy\u0171jt\u0151v\u00e1ltoz\u00f3t, ahol a felt\u00e9telnek megfelel\u0151 elemek \u00f6sszeg\u00e9t<\/span> t\u00e1roljuk.<\/li>\n
- A gy\u0171jt\u0151v\u00e1ltoz\u00f3t 0 kezd\u0151\u00e9rt\u00e9kre \u00e1ll\u00edtjuk be.<\/li>\n
- Ind\u00edtunk egy ciklust, ami a t\u00f6mb \u00f6sszes elem\u00e9n v\u00e9gigmegy.<\/li>\n
- Megvizsg\u00e1ljuk, hogy az adott elem megfelel-e a felt\u00e9telnek<\/li>\n
- Ha megfelel, az \u00f6sszeghez hozz\u00e1adjuk<\/span> az aktu\u00e1lis elemet.<\/li>\n
- A ciklus ut\u00e1n ki\u00edrjuk az eredm\u00e9nyt.<\/li>\n<\/ol>\n
A l\u00e9nyegi k\u00fcl\u00f6nbs\u00e9get kiemeltem. L\u00e1that\u00f3, hogy szinte ugyanaz. Ett\u0151l f\u00fcggetlen\u00fcl ne keverj\u00fck a k\u00e9t algoritmust, mert teljesen m\u00e1s a feladatuk!<\/p>\n
A kiemelt sorban a v\u00e1ltoz\u00f3 n\u00f6vel\u00e9s\u00e9t kicser\u00e9lhetj\u00fck m\u00e1r tanult \u00f6sszead\u00e1ssal kombin\u00e1lt \u00e9rt\u00e9kad\u00f3 oper\u00e1torra. Ism\u00e9t csak az\u00e9rt, mert lust\u00e1k vagyunk, \u00e9s nem akarunk sokat g\u00e9pelni.<\/p>\n
\r\nosszeg = osszeg + tomb[i];\r\nhelyett\r\nosszeg += tomb[i];\r\n<\/pre>\nA harmadik feladat kil\u00f3g a t\u00f6bbi k\u00f6z\u00fcl, ez nem csak tiszta \u00f6sszegz\u00e9s. Itt egyszerre kell az el\u0151z\u0151leg ismertetett megsz\u00e1ml\u00e1l\u00e1st \u00e9s \u00f6sszegz\u00e9st elv\u00e9gezni. Sz\u00fcks\u00e9g\u00fcnk van a p\u00e1ratlan sz\u00e1mok \u00f6sszeg\u00e9re, valamint a darabsz\u00e1m\u00e1ra is az \u00e1tlagol\u00e1shoz:<\/p>\n
\r\nint osszeg = 0;\r\nint db = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 != 0 )\r\n {\r\n osszeg = osszeg + tomb[i];\r\n db++;\r\n }\r\n}\r\ndouble atlag = (double)osszeg\/db;\r\nSystem.out.println("A tomb paratlan szamainak atlaga: "+atlag );\r\n<\/pre>\nL\u00e1thatjuk, hogy a ciklussal ugyan\u00fagy v\u00e9gigmegy\u00fcnk az eg\u00e9sz t\u00f6mb\u00f6n. Ha tal\u00e1lunk egy megfelel\u0151 sz\u00e1mot, akkor hozz\u00e1adjuk az \u00f6sszeghez \u00e9s n\u00f6velj\u00fck a darabsz\u00e1mot is. Az \u00e1tlag m\u00e1r csak egy oszt\u00e1s. De nem egyszer\u0171 oszt\u00e1s. Az osszeg \u00e9s db v\u00e1ltoz\u00f3k eg\u00e9sz t\u00edpusok. Mi lenne az eredm\u00e9nye annak, ha mondjuk az \u00f6sszeg 11 a darabsz\u00e1m pedig 5? 11\/5 = ?<\/p>\n
Ne felejtsd el! Ha k\u00e9t eg\u00e9sz sz\u00e1mot osztunk egym\u00e1ssal, az eg\u00e9sz oszt\u00e1s<\/strong>! Az eredm\u00e9ny nem a sokszor v\u00e1rt 2,2 lenne, hanem 2,0. Az oszt\u00e1s akkor nem eg\u00e9sz oszt\u00e1s, ha legal\u00e1bb az egyik m\u0171veletben r\u00e9szt vev\u0151 sz\u00e1m nem eg\u00e9sz. El\u0151z\u0151leg m\u00e1r mutattam egy tr\u00fckk\u00f6t, \u00edrhatn\u00e1nk \u00edgy is:<\/p>\n\r\nosszeg\/(db+0.0)\r\n<\/pre>\nHelyette azonban legy\u00fcnk eleg\u00e1nsabbak, haszn\u00e1ljunk t\u00edpusk\u00e9nyszer\u00edt\u00e9st, amit a v\u00e9letlen sz\u00e1mok t\u00e9mak\u00f6rben m\u00e1r bemutattam:<\/p>\n
\r\n(double)osszeg\/db\r\n<\/pre>\nA t\u00edpusk\u00e9nyszer\u00edt\u00e9s sor\u00e1n az \u00f6sszeg v\u00e1ltoz\u00f3b\u00f3l kiolvasott \u00e9rt\u00e9ket lebeg\u0151pontos sz\u00e1mm\u00e1 alak\u00edtjuk, majd osztjuk egy eg\u00e9sszel. Ennek eredm\u00e9nye m\u00e1r megfelel\u0151: 2,2.<\/p>\n
Fontos, hogy ez a t\u00edpusk\u00e9nyszer\u00edt\u00e9s nem az eredeti \u00f6sszegv\u00e1ltoz\u00f3ban t\u00e1rolt \u00e9rt\u00e9ket v\u00e1ltoztatja meg, nincs \u00e9rt\u00e9kad\u00e1s! Nem is v\u00e1ltoztathatja meg az \u00f6sszegv\u00e1ltoz\u00f3 tartalm\u00e1t, mivel annak t\u00edpusa eg\u00e9sz. Csak a v\u00e1ltoz\u00f3b\u00f3l felhaszn\u00e1lt \u00e9rt\u00e9ket alak\u00edtja \u00e1t a megadott t\u00edpusra.<\/p>\n
<\/a>Eld\u00f6nt\u00e9s<\/h2>\nEnn\u00e9l a feladatt\u00edpusn\u00e1l azt vizsg\u00e1ljuk, hogy egy t\u00f6mbben tal\u00e1lhat\u00f3-e egy bizonyos tulajdons\u00e1g\u00fa elem. Nem \u00e9rdekel, hogy h\u00e1ny ilyen elem van, csak az a fontos, hogy van-e benne ilyen. Itt logikai eredm\u00e9nyt kapunk, vagyis a v\u00e1lasz igaz vagy hamis lehet. L\u00e1ssunk p\u00e1r p\u00e9ld\u00e1t olyan k\u00e9rd\u00e9sekre, amelyekre ezzel az algoritmussal kaphatunk v\u00e1laszt:<\/p>\n
\n- Van-e az oszt\u00e1lyban l\u00e1ny?<\/li>\n
- Van-e az oszt\u00e1lyban 190 cm-n\u00e9l magasabb di\u00e1k?<\/li>\n
- Volt-e melegebb 38 fokn\u00e1l tavaly ny\u00e1ron?<\/li>\n
- Van-e 30 \u00e9vn\u00e9l fiatalabb tan\u00e1r az iskol\u00e1ban?<\/li>\n<\/ul>\n
Ezekhez a feladatokhoz term\u00e9szetesen sz\u00fcks\u00e9g van t\u00f6mb\u00f6kre, melyek azokat az adatokat t\u00e1rolj\u00e1k, amelyek k\u00f6z\u00f6tt keress\u00fck azt a bizonyos tulajdons\u00e1g\u00fa elemet, azok k\u00f6z\u00fcl is a legels\u0151t. Eml\u00e9kezz, nem \u00e9rdekel h\u00e1ny ilyen elem van, csak az sz\u00e1m\u00edt, hogy van-e ilyen, \u00e9s ez nyilv\u00e1n a legels\u0151 megtal\u00e1lt elem lesz. Az els\u0151 p\u00e9ld\u00e1hoz sz\u00fcks\u00e9g van egy t\u00f6mbre, amely a tanul\u00f3k nem\u00e9t t\u00e1rolja, ak\u00e1r logikai t\u00edpusk\u00e9nt (l\u00e1ny \u2013 true, fi\u00fa \u2013 false). A m\u00e1sodik esetben kell egy t\u00f6mb, ami az oszt\u00e1lyba j\u00e1r\u00f3 di\u00e1kok magass\u00e1gait tartalmazza, a harmadikban egy t\u00f6mb, ami a ny\u00e1ri napok maximum h\u0151m\u00e9rs\u00e9klet\u00e9t tartalmazza, a negyedikn\u00e9l egy t\u00f6mb, amiben benne van az iskol\u00e1ban tan\u00edt\u00f3 tan\u00e1rok \u00e9letkora. Maradjunk a m\u00e1sodik p\u00e9ld\u00e1n\u00e1l, \u00e9s vegy\u00fck \u00fagy, hogy rendelkez\u00e9sre \u00e1ll egy \u201etomb\u201d nev\u0171 t\u00f6mb, ami az oszt\u00e1lyba j\u00e1r\u00f3 di\u00e1kok magass\u00e1gait r\u00f6gz\u00edti.<\/p>\n
\r\nint i = 0;\r\n\r\nwhile( i < tomb.length && tomb[i] <= 190 )\r\n{\r\n i++;\r\n}\r\n\r\nif( i < tomb.length )\r\n{\r\n System.out.println("Van az osztalyban 190 cm-nel magasabb diak.");\r\n}\r\n<\/pre>\nNa de mit is csin\u00e1l ez pontosan?<\/p>\n
\n- El\u0151sz\u00f6r deklar\u00e1lunk egy ciklusv\u00e1ltoz\u00f3t, amit arra fogunk haszn\u00e1lni, hogy indexelhess\u00fck (hivatkozhassunk) az egyes t\u00f6mbelemekre, jelen esetben a di\u00e1kok magass\u00e1gi adataira. Ez a sorsz\u00e1m term\u00e9szetesen 0-t\u00f3l indul, mert a Java nyelvben a t\u00f6mb\u00f6k indexei 0 sz\u00e1mmal kezd\u0151dnek.<\/li>\n
- Azt\u00e1n ind\u00edtunk egy ciklust, melynek az a feladata, hogy v\u00e9gigmehess\u00fcnk egyenk\u00e9nt a t\u00f6mb elemein. A ciklus feje viszont egy \u00f6sszetett felt\u00e9telt tartalmaz. Ennek els\u0151 fele azt vizsg\u00e1lja, hogy v\u00e9gig\u00e9rt\u00fcnk-e m\u00e1r a t\u00f6mb\u00f6n – vagyis, hogy az index kisebb-e, mint a t\u00f6mb m\u00e9rete. Ha az i egyenl\u0151 lenne a t\u00f6mbm\u00e9rettel, az m\u00e1r azt jelenten\u00e9, hogy t\u00faljutottunk az utols\u00f3 elemen, teh\u00e1t a ciklus meg\u00e1ll. Mivel a t\u00f6mb\u00f6k indexe 0-val kezd\u0151dik, ebb\u0151l k\u00f6vetkezik, hogy az utols\u00f3 elem indexe t\u00f6mbm\u00e9ret-1. A felt\u00e9tel m\u00e1sik r\u00e9sze a tulajdons\u00e1g vizsg\u00e1lat, amelyre csak akkor ker\u00fcl sor, ha m\u00e9g nem \u00e9rt\u00fcnk a t\u00f6mb v\u00e9g\u00e9re. Itt azt vizsg\u00e1ljuk, hogy a tomb[i] – vagyis az aktu\u00e1lis di\u00e1k magass\u00e1ga – NEM RENDELKEZIK a keresett tulajdons\u00e1ggal. Ez fura, mert nem pont ennek a ford\u00edtottj\u00e1t keress\u00fck? De igen, ez az algoritmus l\u00e9nyege. Addig kell keresni, am\u00edg NEM tal\u00e1ltuk meg, amit kerest\u00fcnk, hiszen ha megvan, akkor meg\u00e1llhatunk. Ha ez a k\u00e9t felt\u00e9tel egyszerre igaz (nem \u00e9rt\u00fcnk m\u00e9g a t\u00f6mb v\u00e9g\u00e9re \u00c9S nem rendelkezik az aktu\u00e1lis di\u00e1k a keresett tulajdons\u00e1ggal), akkor l\u00e9p\u00fcnk be a ciklusba, ami semmi m\u00e1st nem csin\u00e1l, csak l\u00e9pteti a sz\u00e1ml\u00e1l\u00f3t, vagyis j\u00f6het a k\u00f6vetkez\u0151 vizsg\u00e1land\u00f3 di\u00e1k. Az algoritmus nagyon fontos r\u00e9sze az, hogy a ciklus k\u00e9t felt\u00e9tel\u00e9nek sorrendje k\u00f6t\u00f6tt! El\u0151sz\u00f6r kell azt vizsg\u00e1lni, hogy nem \u00e9rt\u00fcnk-e a v\u00e9g\u00e9re, \u00e9s ha nem, csak akkor szabad megvizsg\u00e1lni, hogy az aktu\u00e1lis elem nem rendelkezik-e a keresett tulajdons\u00e1ggal. Hiszen ha m\u00e1r v\u00e9gign\u00e9zt\u00fck a t\u00f6mb\u00f6t, akkor m\u00e1r nincs mit vizsg\u00e1lni.<\/li>\n
- A ciklus befejez\u0151d\u00e9se ut\u00e1n m\u00e1r csak \u00e9rtelmezn\u00fcnk kell a kapott eredm\u00e9nyt. Az i v\u00e1ltoz\u00f3 \u00e9rt\u00e9ke az, ami a megold\u00e1st tartalmazza. Ha tal\u00e1ltunk olyan di\u00e1kot, aki rendelkezett a keresett tulajdons\u00e1ggal, akkor a ciklus id\u0151 el\u0151tt meg\u00e1llt, vagyis az i \u00e9rt\u00e9ke kisebb, mint a t\u00f6mb m\u00e9rete. Ha egyetlen di\u00e1k sem volt 190 cm-n\u00e9l magasabb, akkor a ciklus az\u00e9rt \u00e1llt meg, mert az i v\u00e1ltoz\u00f3 m\u00e1r nem kisebb a t\u00f6mb m\u00e9ret\u00e9n\u00e9l (vagyis egyenl\u0151), teh\u00e1t nem tal\u00e1ltunk olyat, aki a felt\u00e9telnek megfelelt volna<\/li>\n<\/ol>\n
Term\u00e9szetesen a t\u00f6bbi feladatra is hasonl\u00f3 a megold\u00e1s, l\u00e1ssuk mondjuk a negyedik feladatot:<\/p>\n
\r\nint i = 0;\r\n\r\nwhile( i < tomb.length && tomb[i] >= 30 )\r\n{\r\n i++;\r\n}\r\n\r\nif( i < tomb.length )\r\n{\r\n System.out.println("Van az iskolaban 30 evnel fiatalabb tanar.");\r\n}\r\n<\/pre>\nNagyon fontos eleme teh\u00e1t az eld\u00f6nt\u00e9snek, hogy m\u00e1sodik r\u00e9szfelt\u00e9telnek azt adjuk meg, hogy az aktu\u00e1lis elem a keresett tulajdons\u00e1ggal nem rendelkezik! Mivel a felt\u00e9telek t\u00f6bbs\u00e9ge rel\u00e1ci\u00f3t tartalmaz, itt a rel\u00e1ci\u00f3k ellentettj\u00e9t kell haszn\u00e1lni!<\/p>\n
\r\n\/\/ 30 \u00e9vn\u00e9l fiatalabbat keres\u00fcnk\r\nwhile( ... && tomb[i] < 30 )\r\n<\/pre>\nhelyett<\/p>\n
\r\n\/\/ 30 \u00e9vn\u00e9l nem fiatalabb kell a felt\u00e9telbe\r\nwhile( ... && tomb[i] >= 30 )\r\n<\/pre>\n\u00cdrhatn\u00e1m \u00fagy is, hogy val\u00f3ban tagadom az eredeti \u00e1ll\u00edt\u00e1st:<\/p>\n
\r\n\/\/ 30 \u00e9vn\u00e9l nem fiatalabb\r\nwhile( ... && !(tomb[i] < 30) )\r\n<\/pre>\nAz eredeti \u00e1ll\u00edt\u00e1s val\u00f3di tagad\u00e1s\u00e1t tomb[i] < 30 -> !( tomb[i] < 30) \u00e9n ink\u00e1bb a rel\u00e1ci\u00f3 ellentettj\u00e9vel helyettes\u00edten\u00e9m, mivel ott egy rel\u00e1ci\u00f3 marad csak, \u00edgy csak egy m\u0171veletet kell v\u00e9grehajtani. Val\u00f3di tagad\u00e1s eset\u00e9n ott marad az eredeti rel\u00e1ci\u00f3, majd a rel\u00e1ci\u00f3 logikai \u00e9rt\u00e9k\u00e9nek tagad\u00e1sa is kell, ami k\u00e9t m\u0171velet, de ezekb\u0151l az egyik megsp\u00f3rolhat\u00f3.<\/p>\n
Itt visszautaln\u00e9k a rel\u00e1ci\u00f3s oper\u00e1torokn\u00e1l arra a t\u00e1bl\u00e1zatra<\/a>, ahol ismertettem a rel\u00e1ci\u00f3k tagad\u00e1sait. Ne feledd: a kisebb tagad\u00e1sa nem a nagyobb!<\/span><\/p>\nMi az, amit m\u00e9g \u00e9szrevehett\u00e9l ebben az algoritmusban? Ezzel vissza is kanyarodtunk egy nagyon fontos r\u00e9szhez, a logikai kifejez\u00e9sekn\u00e9l. L\u00e1thatod, hogy a while ciklus fej\u00e9ben egy \u00f6sszetett kifejez\u00e9s szerepel. Ennek az els\u0151 fele az, hogy el\u00e9rt\u00fcnk-e m\u00e1r a t\u00f6mb v\u00e9g\u00e9ig, a m\u00e1sodik pedig az, hogy az aktu\u00e1lis elem nem rendelkezik a keresett tulajdons\u00e1ggal. L\u00e1that\u00f3, hogy a m\u00e1sodik felt\u00e9tel k\u00e9sz t\u00e9nyk\u00e9nt veszi azt, hogy ott csak val\u00f3di elemet vizsg\u00e1lhatok. Egy t\u00f6mbnek, ha eml\u00e9kszel, fix tulajdons\u00e1ga a m\u00e9rete. Vagyis csak akkora indexet lehet haszn\u00e1lni, amilyen elem m\u00e9g szerepel a t\u00f6mbben. Egy 10 elem\u0171 t\u00f6mbben nem lehet pl a tomb[12] elemre hivatkozni, mert ilyen elem nem l\u00e9tezik.<\/p>\n
Ez fut\u00e1si hib\u00e1t eredm\u00e9nyez. Na de itt hol ellen\u0151rz\u00f6m azt, hogy nehogy t\u00fal nagy indexet haszn\u00e1ljak? Az els\u0151 felt\u00e9telben. Ez egy logikai r\u00f6vidz\u00e1r<\/a>. Ha az els\u0151 r\u00e9szfelt\u00e9tel, hogy az i sz\u00e1ml\u00e1l\u00f3 kisebb, mint a t\u00f6mbm\u00e9ret (vagyis az i lehet a t\u00f6mb egy indexe) teljes\u00fcl, csak akkor vizsg\u00e1lja meg a m\u00e1sodik r\u00e9szfelt\u00e9telt, az adott elem keresett tulajdons\u00e1g\u00e1nak hi\u00e1ny\u00e1t. Ha az i el\u00e9rte a t\u00f6mbm\u00e9retet (vagyis nem kisebb), akkor a logikai r\u00f6vidz\u00e1r miatt a m\u00e1sodik felt\u00e9telt logikai \u00e9s<\/strong> eset\u00e9n m\u00e1r meg sem vizsg\u00e1lja. Nem fog olyan elemet vizsg\u00e1lni, ami nem l\u00e9tezik! Nagyon fontos eleme az algoritmusnak az, hogy a k\u00e9t r\u00e9szfelt\u00e9telnek pontosan ilyen sorrendben kell szerepelnie, mert \u00edgy oldja meg a r\u00f6vidz\u00e1r azt az ellen\u0151rz\u00e9st is, hogy csak val\u00f3di emelet vizsg\u00e1ljunk meg, \u00e9s ne kapjunk fut\u00e1si hib\u00e1t.<\/p>\n<\/a>Kiv\u00e1laszt\u00e1s<\/h2>\nEzzel az algoritmussal azt adhatjuk meg, hogy egy adott elem pontosan hol szerepel a t\u00f6mbben. Ez term\u00e9szetesen az adott elem index\u00e9t jelenti, amellyel a t\u00f6mbben hivatkozunk r\u00e1. Ez az algoritmus felt\u00e9telezi azt, hogy az elem t\u00e9nyleg benne van a t\u00f6mbben, ez ugyanis nem keverend\u0151 \u00f6ssze a keres\u00e9s algoritmus\u00e1val, amit k\u00f6vetkez\u0151k\u00e9nt fogok ismertetni. L\u00e1ssunk erre egy p\u00e1r k\u00e9rd\u00e9st.<\/p>\n
\n- V\u00e1lasszuk ki a t\u00f6mbb\u0151l az 50-es sz\u00e1mot (nem index, hanem \u00e9rt\u00e9k!).<\/li>\n
- H\u00e1nyadik a sorban az a di\u00e1k, akinek a magass\u00e1ga 190 cm-n\u00e9l nagyobb.<\/li>\n<\/ul>\n
L\u00e1ssuk az els\u0151 p\u00e9lda megold\u00e1s\u00e1t:<\/p>\n
\r\nint i = 0;\r\n\r\nwhile( tomb[i] != 50 )\r\n{\r\n i++;\r\n}\r\n\r\nSystem.out.println("Az 50-es sz\u00e1m indexe: "+i);\r\n<\/pre>\nHa megn\u00e9zz\u00fck, ez egy lecsupasz\u00edtott eld\u00f6nt\u00e9s algoritmusnak t\u0171nik, amikor ciklusban m\u0171k\u00f6d\u00e9si felt\u00e9telk\u00e9nt furcsa m\u00f3don azt adjuk meg, hogy a ciklus addig menjen, am\u00edg az aktu\u00e1lis elem NEM rendelkezik a tulajdons\u00e1ggal. Vagyis addig megy\u00fcnk, am\u00edg meg nem tal\u00e1ljuk. Hi\u00e1nyzik viszont a eld\u00f6nt\u00e9ses algoritmus \u00f6sszetett felt\u00e9tel\u00e9nek els\u0151 r\u00e9sze, ami azt vizsg\u00e1lja, hogy t\u00falszaladtunk-e a t\u00f6mb v\u00e9g\u00e9n. Itt erre nincs is sz\u00fcks\u00e9g, mivel abb\u00f3l indultunk ki, hogy a kiv\u00e1lasztand\u00f3 elem biztosan benne van a t\u00f6mbben.<\/p>\n
Kiv\u00e1laszt\u00e1sn\u00e1l lehets\u00e9ges, hogy t\u00f6bb elem is megfelel a felt\u00e9telnek, ez az algoritmus a legels\u0151 olyan elemet v\u00e1lasztja ki, akire a felt\u00e9tel\u00fcnk igaz lesz. Viszonylag k\u00f6nnyen megoldhat\u00f3 az is, hogy a legutols\u00f3 olyat v\u00e1lasszuk ki, ez csak a ciklus halad\u00e1si ir\u00e1ny\u00e1t\u00f3l \u00e9s az i kezd\u0151\u00e9rt\u00e9k\u00e9t\u0151l f\u00fcgg.<\/p>\n
<\/a>Keres\u00e9s<\/h2>\nA keres\u00e9s algoritmusa gyakorlatilag szinte ugyanaz, mint az eld\u00f6nt\u00e9s algoritmusa, mind\u00f6ssze az i v\u00e1ltoz\u00f3 ciklus ut\u00e1ni \u00e9rtelmez\u00e9s\u00e9n\u00e9l van k\u00fcl\u00f6nbs\u00e9g. Az\u00e9rt szerepeljen itt \u00fajra az algoritmus egy konkr\u00e9t p\u00e9ld\u00e1val. A feladatban azt keress\u00fck, hogy van-e 190 cm-n\u00e9l magasabb di\u00e1k \u00e9s hogy \u0151 h\u00e1nyadik a t\u00f6mbben:<\/p>\n
\r\nint i = 0;\r\n\r\nwhile( i < tomb.length && tomb[i] <= 190 )\r\n{\r\n i++;\r\n}\r\n\r\nif( i < tomb.length )\r\n{\r\n System.out.println("A 190 cm-n\u00e9l magasabb di\u00e1k helye: "+i);\r\n}\r\nelse\r\n{\r\n System.out.println("Nincs ilyen di\u00e1k.");\r\n}\r\n<\/pre>\nL\u00e1that\u00f3 az, hogy ez biztons\u00e1gosabb algoritmus az el\u0151z\u0151n\u00e9l. Ez akkor is haszn\u00e1lhat\u00f3, ha nem tudjuk, hogy egy\u00e1ltal\u00e1n l\u00e9tezik-e ilyen di\u00e1k, ez\u00e9rt eggyel t\u00f6bb a felt\u00e9tel is, mert azt is figyelni kell, hogy a t\u00f6mb v\u00e9g\u00e9n ne szaladjunk t\u00fal. A ciklus ut\u00e1n pedig az i \u00e9rt\u00e9k\u00e9b\u0151l hat\u00e1rozhatjuk meg a keresett elem hely\u00e9t, ha ugyanis az i kisebb a t\u00f6mb m\u00e9ret\u00e9n\u00e9l (vagyis nem szaladtunk t\u00fal rajta, teh\u00e1t benne van), akkor az i m\u00e1r a keresett elem hely\u00e9t jelenti. Ha nem \u00edgy van, akkor nincs benne. Itt is logikai r\u00f6vidz\u00e1rat haszn\u00e1lunk, teh\u00e1t a k\u00e9t felt\u00e9tel sorrendje nagyon fontos. Az els\u0151 felt\u00e9tel biztos\u00edtja azt, hogy a m\u00e1sodik nem lehet hib\u00e1s. Keres\u00e9si algoritmusb\u00f3l t\u00f6bbf\u00e9le l\u00e9tezik, ez csak a legegyszer\u0171bb line\u00e1ris keres\u00e9s algoritmusa.<\/p>\n
<\/a>Minimum\/maximum keres\u00e9s<\/h2>\nNagyon gyakori feladat az, amikor egy t\u00f6mbb\u0151l meg kell hat\u00e1rozni a legkisebb\/legnagyobb elemet. Ez nem csak egyszer\u0171 t\u00edpusokn\u00e1l haszn\u00e1lhat\u00f3, ak\u00e1r objektumok (t\u00f6bb tulajdons\u00e1ggal rendelkez\u0151 adatt\u00e1rol\u00f3k) k\u00f6z\u00fcl is kiv\u00e1laszthatjuk a legkisebb\/legnagyobb tulajdons\u00e1g\u00fat. Technikailag az, hogy a minimum vagy maximum \u00e9rt\u00e9ket keress\u00fck csak egy rel\u00e1ci\u00f3 megford\u00edt\u00e1s\u00e1t jelenti. N\u00e9zz\u00fck akkor hogy n\u00e9z ki ez az algoritmus. Keress\u00fck meg a tomb nev\u0171 t\u00f6mbben a legnagyobb \u00e9rt\u00e9ket!<\/p>\n
\r\nint max = 0;\r\n\r\nfor( int i = 1; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] > tomb[max] ) max = i;\r\n}\r\n\r\nSystem.out.println("A tombben levo legnagyobb szam: "+tomb[max]);\r\n<\/pre>\nN\u00e9zz\u00fck akkor r\u00e9szenk\u00e9nt a programot. El\u0151sz\u00f6r is deklar\u00e1lunk egy max nev\u0171 v\u00e1ltoz\u00f3t, amelynek azonnal adunk is egy 0 kezd\u0151\u00e9rt\u00e9ket. Fontos, hogy ez nem egy v\u00e1ltoz\u00f3 null\u00e1z\u00e1s, mint a megsz\u00e1ml\u00e1l\u00e1s vagy \u00f6sszegz\u00e9s algoritmus\u00e1n\u00e1l tett\u00fck. Ennek a 0 \u00e9rt\u00e9knek jelent\u00e9se van. Azt jelenti, hogy a legnagyobb elem a legels\u0151, vagyis a 0 index\u0171! A max v\u00e1ltoz\u00f3ban teh\u00e1t nem a legnagyobb elem \u00e9rt\u00e9k\u00e9t, hanem a hely\u00e9t (index\u00e9t) t\u00e1roljuk. Mindj\u00e1rt vil\u00e1gos lesz, mi\u00e9rt. Azt mondjuk teh\u00e1t, hogy a legnagyobb elem a 0. helyen van, vagyis ez az els\u0151 elem. Ez teljesen egy\u00e9rtelm\u0171, hiszen am\u00edg meg nem vizsg\u00e1lom a t\u00f6mb\u00f6t, az els\u0151 elem tekinthet\u0151 a legnagyobbnak, mivel a t\u00f6bbit m\u00e9g nem ismerem. A ciklust, amivel v\u00e9gigmegyek az eg\u00e9sz t\u00f6mb\u00f6n term\u00e9szetesen a 2. elemt\u0151l indul (indexe 1) \u00e9s a t\u00f6mbm\u00e9ret-1 index\u0171 az utols\u00f3, amit vizsg\u00e1lnom kell. Ha az \u00e9ppen vizsg\u00e1lt elem (tomb[i]) nagyobb, mint az eddigi legnagyobb tomb[max], akkor az \u00faj maximum helye megv\u00e1ltozik az aktu\u00e1lisra -> max = i.<\/p>\n
Fura lehet, hogy mi\u00e9rt a legnagyobb elem hely\u00e9t t\u00e1roljuk \u00e9s nem az \u00e9rt\u00e9k\u00e9t. Mi van akkor, ha ez a k\u00e9rd\u00e9s: H\u00e1nyadik elem a legnagyobb a t\u00f6mbben? Ha a maximumban a legnagyobb elem \u00e9rt\u00e9k\u00e9t t\u00e1roln\u00e1nk, azzal a hely\u00e9t nem tudjuk megmondani, csak az \u00e9rt\u00e9k\u00e9t. A hely\u00e9b\u0151l viszont meghat\u00e1rozhatjuk mindkett\u0151t.<\/p>\n
Ha a legkisebb elemet keress\u00fck, akkor a kiemelt sorban fordul meg a rel\u00e1ci\u00f3s jel, \u00e9s m\u00e1ris a legkisebb elemet kapjuk meg a v\u00e9g\u00e9n. Term\u00e9szetesen minimum keres\u00e9sn\u00e9l c\u00e9lszer\u0171 a max v\u00e1ltoz\u00f3 nev\u00e9t min-re v\u00e1ltoztatni, hogy utaljon arra, mit is keresek.<\/p>\n
Ne felejtsd el teh\u00e1t, minimum \u00e9s maximum keres\u00e9sn\u00e9l a helyet t\u00e1rol\u00f3 v\u00e1ltoz\u00f3 kezd\u0151\u00e9rt\u00e9ke 0, mivel az els\u0151 elem lesz el\u0151sz\u00f6r a legkisebb vagy legnagyobb, ha elkezdem a keres\u00e9st.<\/p>\n
M\u00e1s oka is van annak, hogy a helyet \u00e9s nem az \u00e9rt\u00e9ket t\u00e1roljuk. T\u00e9telezz\u00fck fel, hogy csak negat\u00edv sz\u00e1mokat tartalmaz a t\u00f6mb\u00fcnk \u00e9s a legnagyobbat keress\u00fck k\u00f6z\u00fcl\u00fck. L\u00e9trehozunk egy max v\u00e1ltoz\u00f3t, azt null\u00e1zzuk, de ez most a legnagyobb elem \u00e9rt\u00e9k\u00e9t jelenten\u00e9. Tal\u00e1lhatunk negat\u00edv sz\u00e1mok k\u00f6z\u00f6tt olyat, ami nagyobb, mint 0? K\u00f6nnyen bel\u00e1that\u00f3, hogy csak pozit\u00edv sz\u00e1mokat tartalmaz a t\u00f6mb \u00e9s a legkisebbet keress\u00fck, akkor sem \u00e1llja meg a hely\u00e9t a null\u00e1z\u00e1s. A nulla nem pozit\u00edv, teh\u00e1t nem tal\u00e1lsz ett\u0151l kisebb pozit\u00edv sz\u00e1mot, vagyis a t\u00f6mb egyik eleme sem ker\u00fclhet a hely\u00e9re.<\/p>\n
<\/a>Rendez\u00e9s<\/h2>\nNagyon gyakori a programjainkban az a t\u00edpusfeladat, hogy sorba kell rendezni egy t\u00f6mb elemeit. A Java nyelvben az egyszer\u0171 t\u00edpusokra, \u00e9s a Stringekre is l\u00e9tezik be\u00e9p\u00edtett rendez\u00e9s, m\u00e9gis ritk\u00e1n haszn\u00e1ljuk \u0151ket, mert javar\u00e9szt objektumokkal fogunk dolgozni, azokra pedig ezek nem m\u0171k\u00f6dnek. Rendez\u00e9si algoritmusb\u00f3l nagyon sokf\u00e9le l\u00e9tezik, vannak egyszer\u0171bb, de lassabb t\u00edpusok, \u00e9s vannak nagyon hat\u00e9konyak. A val\u00f3di helyzet az, hogy a rendezend\u0151 adatokt\u00f3l mennyis\u00e9g\u00e9t\u0151l is f\u00fcgg az, hogy melyik rendez\u00e9si algoritmus a hat\u00e9kony, de k\u00f6z\u00e9piskolai szinten mindegy hogyan rendez\u00fcnk, csak oldjuk meg a feladatot. K\u00e9t rendez\u00e9si algoritmust fogok megmutatni, amelyeket haszn\u00e1lni\/tan\u00edtani szoktam, ha ezeket tudod, akkor b\u00e1rmilyen t\u00edpus\u00fa t\u00f6mb\u00f6t rendezni tudsz.<\/p>\n
A rendez\u00e9sek legt\u00f6bbje \u00f6sszehasonl\u00edt\u00e1sokon \u00e9s cser\u00e9ken alapul. \u00d6sszehasonl\u00edtunk k\u00e9t elemet, \u00e9s ha azok sorrendje nem megfelel\u0151, akkor megcser\u00e9lj\u00fck \u0151ket. Az algoritmusok sokszor abban k\u00fcl\u00f6nb\u00f6znek, hogy melyik kett\u0151t hasonl\u00edtjuk \u00f6ssze \u00e9s ut\u00e1na melyik kett\u0151t, stb. L\u00e9tezik olyan speci\u00e1lis rendez\u00e9s is, amelyik nem haszn\u00e1l \u00f6sszehasonl\u00edt\u00e1sokat \u00e9s cser\u00e9ket, de ezek csak bizonyos esetekben haszn\u00e1lhat\u00f3ak, akkor viszont hihetetlen gyorsak.<\/p>\n
A rendez\u00e9s eset\u00e9n m\u00e1r \u00f6sszetettebb m\u00f3don kell bej\u00e1rni a t\u00f6mb\u00f6t, amelynek elemeit rendezni szeretn\u00e9nk. Itt is igaz az, hogy nem csak egyszer\u0171 t\u00edpus\u00fa \u00e9rt\u00e9keket tartalmaz\u00f3 t\u00f6mb\u00f6ket lehet rendezni, az elemek lehetnek \u00f6sszetett objektumok is, melyek t\u00f6bbf\u00e9le t\u00edpus\u00fa \u00e9rt\u00e9ket tartalmazhatnak.<\/p>\n
A t\u00f6mb\u00f6k kezel\u00e9sekor, \u00e9s az alap algoritmusok haszn\u00e1latakor minden esetben ciklusokat haszn\u00e1lunk arra, hogy bej\u00e1rjuk az adott t\u00f6mb\u00f6t, \u00e9s annak \u00e9rt\u00e9keihez egym\u00e1s ut\u00e1n hozz\u00e1f\u00e9rj\u00fcnk. Abban vannak csak k\u00fcl\u00f6nbs\u00e9gek, hogy t\u00e9nylegesen bej\u00e1rjuk-e az eg\u00e9szet, vagy sem, esetleg a bej\u00e1r\u00e1s ir\u00e1nya v\u00e1ltozik. Itt azonban m\u00e1sr\u00f3l lesz sz\u00f3. Itt tal\u00e1lkozunk el\u0151sz\u00f6r az egym\u00e1sba \u00e1gyazott ciklusokkal.<\/p>\n
A rendez\u00e9sek, melyeket jellemz\u0151en haszn\u00e1lunk minden esetben azt az elvet k\u00f6vetik, hogy a t\u00f6mb bizonyos elemeit hasonl\u00edtj\u00e1k \u00f6ssze, hogy azok egym\u00e1shoz k\u00e9pest a k\u00edv\u00e1nt sorrendben helyezkednek-e el. Ha ez nem \u00edgy van, akkor ezt a k\u00e9t elemet meg kell cser\u00e9lni. Itt azonban nem csak az egym\u00e1s melletti szomsz\u00e9dokat vizsg\u00e1ljuk,<\/p>\n
Egyszer\u0171 cser\u00e9s rendez\u00e9s<\/h4>\n
Ezt a rendez\u00e9st t\u00f6bb n\u00e9ven is megtal\u00e1lhatjuk az alap algoritmusok k\u00f6z\u00f6tt, \u00e9n ezt a nevet haszn\u00e1lom. Az elv, ami alapj\u00e1n dolgozik az az, hogy minden elemet \u00f6sszehasonl\u00edt az \u00f6sszes m\u00f6g\u00f6tte l\u00e9v\u0151vel, \u00e9s ha azok sorrendje nem megfelel\u0151, akkor megcser\u00e9li \u0151ket. K\u00e9t egym\u00e1sba \u00e1gyazott ciklust ig\u00e9nyel, ezeket tradicion\u00e1lisan i<\/strong> \u00e9s j<\/strong> ciklusv\u00e1ltoz\u00f3kkal haszn\u00e1ljuk. L\u00e1ssuk akkor mag\u00e1t az algoritmust, ahol felt\u00e9telezz\u00fck, hogy van egy tomb<\/strong> nev\u0171 t\u00f6mb\u00fcnk, amely v\u00e9letlen sz\u00e1mokkal van felt\u00f6ltve \u00e9s a meret<\/strong> nev\u0171 v\u00e1ltoz\u00f3ban a t\u00f6mb m\u00e9ret\u00e9t tal\u00e1ljuk meg:<\/p>\n\r\nint csere;\r\nfor( int i = 0; i < tomb.length-1; i++ )\r\n{\r\n for( int j = i+1; j < tomb.length; j++ )\r\n {\r\n if( tomb[i] > tomb[j] )\r\n {\r\n csere = tomb[i];\r\n tomb[i] = tomb[j];\r\n tomb[j] = csere;\r\n }\r\n }\r\n}\r\n<\/pre>\nA ciklus \u00fagy dolgozik, hogy a j v\u00e1ltoz\u00f3 mindig az i ut\u00e1ni helyet jel\u00f6l, mivel a j kezd\u0151\u00e9rt\u00e9ke minden esetben i+1-r\u0151l indul. \u00c9ppen ez\u00e9rt az i soha nem mehet el a t\u00f6mb v\u00e9g\u00e9ig, mert akkor az utols\u00f3 elem ut\u00e1ni \u00f6sszehasonl\u00edt\u00e1st is elv\u00e9gezne, ami mindenk\u00e9pp hib\u00e1s.<\/p>\n
Teh\u00e1t m\u00e9g egyszer a l\u00e9nyeg: az i van el\u00f6l, a j van h\u00e1tul!<\/strong><\/p>\nL\u00e1ssuk a kiemelt r\u00e9szek magyar\u00e1zat\u00e1t:<\/p>\n
\n- 1 – Kell egy csere v\u00e1ltoz\u00f3 az esetleges cser\u00e9khez seg\u00e9dv\u00e1ltoz\u00f3nak. A v\u00e1ltoz\u00f3 t\u00edpus\u00e1nak meg kell egyezni a t\u00f6mb elemeinek t\u00edpus\u00e1val, hiszen azon k\u00f6z\u00fcl fogjuk az egyiket elt\u00e1rolni benne.<\/li>\n
- 2 – Az i v\u00e1ltoz\u00f3 soha nem mehet el a t\u00f6mb v\u00e9g\u00e9ig, vagyis i < tomb.length-1;<\/li>\n
- 4 – A j mindig az i ut\u00e1n \u00e1ll, ez\u00e9rt int j = i+1;<\/li>\n
- 6 – Mindig \u00f6sszehasonl\u00edtjuk az el\u00f6l \u00e9s h\u00e1tul l\u00e9v\u0151 elemeket, \u00e9s ha ezek sorrendje nem megfelel\u0151…<\/li>\n
- 8-10 – Akkor j\u00f6n az elemek cser\u00e9je.<\/li>\n<\/ul>\n
A rendez\u00e9s ir\u00e1nya csak \u00e9s kiz\u00e1r\u00f3lag a 6. sorban megadott rel\u00e1ci\u00f3s jelt\u0151l f\u00fcgg. Ha az el\u00f6l l\u00e9v\u0151 nagyobb \u00e9s akkor cser\u00e9l\u00fcnk, akkor a nagyok ker\u00fclnek h\u00e1tra, vagyis n\u00f6vekv\u0151 rendez\u00e9st alkalmazunk. Ha az el\u0151l l\u00e9v\u0151 kisebb \u00e9s akkor cser\u00e9l\u00fcnk, akkor a kicsik ker\u00fclnek h\u00e1tra, \u00e9s cs\u00f6kken\u0151 rendez\u00e9st \u00edrunk. A fenti p\u00e9lda teh\u00e1t n\u00f6vekv\u0151 rendez\u00e9st val\u00f3s\u00edt meg, mivel az els\u0151 esetnek megfelel\u0151 a rel\u00e1ci\u00f3s jel.<\/p>\n
A cs\u00f6kken\u0151 rendez\u00e9s ehhez k\u00e9pest teh\u00e1t minim\u00e1lis v\u00e1ltoztat\u00e1ssal j\u00e1r:<\/p>\n
\r\nint csere;\r\nfor( int i = 0; i < tomb.length-1; i++ )\r\n{\r\n for( int j = i+1; j < tomb.length; j++ )\r\n {\r\n if( tomb[i] < tomb[j] )\r\n {\r\n csere = tomb[i];\r\n tomb[i] = tomb[j];\r\n tomb[j] = csere;\r\n }\r\n }\r\n}\r\n<\/pre>\nMinimum\/maximum kiv\u00e1laszt\u00e1sos rendez\u00e9s<\/h4>\n
Ez a rendez\u00e9s az el\u0151z\u0151 tov\u00e1bbfejlesztett v\u00e1ltozata. Az el\u0151z\u0151 algoritmus \u00fagy dolgozik, hogy minden esetben megcser\u00e9li a k\u00e9t elemet, ha az aktu\u00e1lis k\u00e9t elem helyzete nem megfelel\u0151. Ez azt eredm\u00e9nyezi, hogy t\u00f6bb csere is lesz, mire a legkisebb a t\u00f6mb elej\u00e9re ker\u00fcl n\u00f6vekv\u0151 rendez\u00e9s eset\u00e9n. De ha m\u00e1r egyszer n\u00f6vekv\u0151 rendez\u00e9st akarunk megval\u00f3s\u00edtani, akkor nem lenne jobb, hogy ha el\u0151sz\u00f6r megkeresn\u00e9nk a legkisebb elemet, majd azt helyezn\u00e9nk a lista elej\u00e9re, majd ut\u00e1na megkeresn\u00e9k a m\u00e1sodik legkisebbet, azt berakn\u00e1nk az els\u0151 ut\u00e1n, \u00e9s \u00edgy tov\u00e1bb? J\u00f3val kevesebb cser\u00e9vel j\u00e1rna, mint az el\u0151z\u0151. Term\u00e9szetesen megoldhat\u00f3, az el\u0151z\u0151 rendez\u00e9si algoritmusa t\u00f6k\u00e9letesen kombin\u00e1lhat\u00f3 a m\u00e1r tanult minimum\/maximumkeres\u00e9si algoritmusokkal. L\u00e1ssuk akkor hogyan:<\/p>\n
\r\nint csere;\r\nint min;\r\nfor( int i = 0; i < tomb.length-1; i++ )\r\n{\r\n min = i;\r\n for( int j = i+1; j < tomb.length; j++ )\r\n {\r\n if( tomb[j] < tomb[min] )\r\n {\r\n min = j;\r\n }\r\n }\r\n if( min != i )\r\n {\r\n csere = tomb[i];\r\n tomb[i] = tomb[min];\r\n tomb[min] = csere;\r\n }\r\n}\r\n<\/pre>\nL\u00e1ssuk akkor a magyar\u00e1zatot:<\/p>\n
\n- 1 – Kell egy csere v\u00e1ltoz\u00f3 az esetleges cser\u00e9khez seg\u00e9dv\u00e1ltoz\u00f3nak. A v\u00e1ltoz\u00f3 t\u00edpus\u00e1nak meg kell egyezni a t\u00f6mb elemeinek t\u00edpus\u00e1val, hiszen azon k\u00f6z\u00fcl fogjuk az egyiket elt\u00e1rolni benne.<\/li>\n
- 2 – Kell egy v\u00e1ltoz\u00f3, ahol a legkisebb elem hely\u00e9t t\u00e1roljuk (mint a minimumkiv\u00e1laszt\u00e1sn\u00e1l), de ennek itt m\u00e9g nem adunk kezd\u0151\u00e9rt\u00e9ket.<\/li>\n
- 5 – Miel\u0151tt elkezdj\u00fck a bels\u0151 ciklust, ami az el\u00f6l l\u00e9v\u0151 elem m\u00f6g\u00f6ttiek index\u00e9n megy v\u00e9gig, az el\u00f6l l\u00e9v\u0151 elemet felt\u00e9telezz\u00fck a legkisebbnek. Itt a bels\u0151 ciklus fut\u00e1s\u00e1t gyakorlatilag egy minimum kiv\u00e1laszt\u00e1snak \u00edrtuk meg. A tomb[i] az els\u0151 elem, ez\u00e9rt ennek a hely\u00e9t felt\u00e9telezz\u00fck a legkisebb elem hely\u00e9nek,<\/li>\n
- 8 – majd, ha az eddigi minimumt\u00f3l valamelyik m\u00f6g\u00f6tte l\u00e9v\u0151 (tomb[j]) t\u0151le kisebb,<\/li>\n
- 10 – akkor a h\u00e1tul l\u00e9v\u0151 elem hely\u00e9t (j) jegyezz\u00fck meg, mint aktu\u00e1lis legkisebbet.<\/li>\n
- 13 – Ha a bels\u0151 ciklussal v\u00e9gezt\u00fcnk, akkor a min v\u00e1ltoz\u00f3ban benne van a h\u00e1tul l\u00e9v\u0151 elemek k\u00f6z\u00fcl a legkisebbnek a helye. Ha ez a hely nem egyenl\u0151 az el\u00f6l l\u00e9v\u0151vel (vagyis nem \u00f6nmaga a legkisebb), akkor tal\u00e1ltunk az el\u00f6l l\u00e9v\u0151 (i) elem m\u00f6g\u00f6tt t\u0151le kisebbet, melynek helyet a min v\u00e1ltoz\u00f3ban t\u00e1roljuk.<\/li>\n
- 15-17 – Ebben az esetben a k\u00e9t elemet (i \u00e9s min helyen l\u00e9v\u0151ket) megcser\u00e9lj\u00fck.<\/li>\n<\/ul>\n
Ezt az algoritmust ink\u00e1bb csak \u00e9rdekess\u00e9gk\u00e9pp mutattam meg, \u00e9retts\u00e9gire t\u00f6k\u00e9letesen el\u00e9g, ha az egyszer\u0171 cser\u00e9s rendez\u00e9st megtanulod, mert csak az a k\u00f6vetelm\u00e9ny, hogy rendezni tudj, teljesen mindegy, melyik algoritmussal. Nyilv\u00e1n a legegyszer\u0171bbet c\u00e9lszer\u0171 megtanulni, a hat\u00e9konys\u00e1g nem k\u00f6vetelm\u00e9ny.<\/p>\n
<\/a>Kiv\u00e1logat\u00e1s<\/h2>\nSzint\u00e9n az alap algoritmusok k\u00f6z\u00e9 tartozik az a feladatt\u00edpus, amikor bizonyos tulajdons\u00e1gnak, vagy tulajdons\u00e1goknak megfelel\u0151 elemeket kell egy t\u00f6mbb\u0151l egy m\u00e1sik t\u00f6mbbe kiv\u00e1logatni. Tegy\u00fck fel, van egy eg\u00e9szeket tartalmaz\u00f3 t\u00f6mb\u00fcnk, melyet a [-9;9] intervallumb\u00f3l t\u00f6lt\u00f6tt\u00fcnk fel. Hogyan oldhatjuk meg, hogy ebb\u0151l a t\u00f6mbb\u0151l egy m\u00e1sik t\u00f6mbbe kigy\u0171jtj\u00fck a negat\u00edv sz\u00e1mokat? Minden esetben l\u00e9tre kell hozni egy m\u00e1sik t\u00f6mb\u00f6t, amibe a megfelel\u0151 elemeket m\u00e1soljuk. De mekkora legyen ez a t\u00f6mb? Ez az ami alapvet\u0151en meghat\u00e1rozza, hogy milyen megold\u00e1si m\u00f3dot alkalmazunk. K\u00e9tf\u00e9le esetet k\u00fcl\u00f6nb\u00f6ztet\u00fcnk meg:<\/p>\n
\n- L\u00e9trehozunk egy eredeti t\u00f6mbnek megfelel\u0151 m\u00e9ret\u0171 t\u00f6mb\u00f6t, azt felt\u00e9telezve, hogy ak\u00e1r az \u00f6sszes elem lehet negat\u00edv, \u00edgy mindet \u00e1t kell m\u00e1solni. Ha azonban nem minden elem negat\u00edv, akkor az \u00faj t\u00f6mbben maradnak \u00fcres helyek, ahova nem rakunk \u00e1t semmit. \u00cdgy nyilv\u00e1n kell tartanunk, hogy h\u00e1ny elemet m\u00e1soltunk \u00e1t az \u00faj t\u00f6mbbe, \u00e9s mennyi maradt “\u00fcresen” a v\u00e9g\u00e9n.<\/li>\n
- Megoldhatjuk \u00fagy is, hogy el\u0151sz\u00f6r megsz\u00e1moljuk, hogy h\u00e1ny elem felel meg a felt\u00e9telnek, ami alapj\u00e1n a kiv\u00e1logat\u00e1st el akarjuk v\u00e9gezni, \u00e9s az \u00faj t\u00f6mb\u00f6t pontosan akkor\u00e1nak \u00e1ll\u00edtjuk be. \u00cdgy a megold\u00e1s v\u00e9g\u00e9n az \u00faj t\u00f6mbben csak azok az elemek lesznek benne, amelyeket mi helyezt\u00fcnk el benne.<\/li>\n<\/ol>\n
A k\u00e9t megold\u00e1sb\u00f3l a m\u00e1sodik nyilv\u00e1n picivel t\u00f6bb munk\u00e1val j\u00e1r, mert kapcsol\u00f3dik hozz\u00e1 egy megsz\u00e1ml\u00e1l\u00e1s is, viszont ut\u00e1na m\u00e1r nem kell att\u00f3l tartanunk, hogy az eredm\u00e9ny t\u00f6mbben olyan elem is el\u0151fordul, ami nem felel meg a kiv\u00e1logat\u00e1s felt\u00e9tel\u00e9nek.<\/p>\n
L\u00e1ssuk akkor a k\u00e9t k\u00fcl\u00f6nb\u00f6z\u0151 megold\u00e1st. Mindk\u00e9t esetben felt\u00e9telezz\u00fck, hogy van egy tomb<\/strong> nev\u0171 t\u00f6mb\u00fcnk, amely v\u00e9letlen sz\u00e1mokkal van felt\u00f6ltve. Az \u00faj t\u00f6mbbe a p\u00e1ratlan sz\u00e1mokat szeretn\u00e9nk kiv\u00e1logatni:<\/p>\n\r\nint[] paratlan = new int[tomb.length];\r\n\r\nint db = 0;\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 != 0 )\r\n {\r\n paratlan[db] = tomb[i];\r\n db++;\r\n }\r\n}\r\n<\/pre>\nL\u00e1ssuk akkor a kiemelt sorok magyar\u00e1zat\u00e1t:<\/p>\n
\n- 1 – L\u00e9trehozok egy ugyanakkora t\u00f6mb\u00f6t, mint az eredeti, lehet\u0151s\u00e9get adva arra, hogy ak\u00e1r minden elemet kiv\u00e1logathassak.<\/li>\n
- 3 – L\u00e9trehozok egy db nev\u0171 v\u00e1ltoz\u00f3t, ami jelen esetben az els\u0151 \u00fcres helyet fogja t\u00e1rolni, ahova a k\u00f6vetkez\u0151 kiv\u00e1logatott elemet elhelyezhetem, a kiv\u00e1logat\u00e1s v\u00e9gezt\u00e9vel pedig t\u00e1rolni fogja, hogy az \u00faj t\u00f6mbbe h\u00e1ny elem ker\u00fclt bele.<\/li>\n
- 4 – V\u00e9gigmegyek az eredeti t\u00f6mb\u00f6n,<\/li>\n
- 6 – \u00e9s ha az eredeti t\u00f6mbben p\u00e1ratlan sz\u00e1mot tal\u00e1lunk,<\/li>\n
- 8 – akkor az \u00faj t\u00f6mbben a els\u0151 \u00fcres helyre (db) elhelyezem az elemet,<\/li>\n
- 9 – majd megn\u00f6velem a db-ot, hogy az esetleges k\u00f6vetkez\u0151 \u00e1tm\u00e1solt elem ne \u00edrja fel\u00fcl az el\u0151z\u0151t.<\/li>\n<\/ul>\n
L\u00e1that\u00f3, hogy nem olyan bonyolult algoritmusr\u00f3l van sz\u00f3, a kulcs az, hogy mindig t\u00e1rolom egy v\u00e1ltoz\u00f3ban, hogy hol van az \u00faj t\u00f6mbben az els\u0151 \u00fcres hely, mert csak oda rakhatok bele a kiv\u00e1logat\u00e1s sor\u00e1n elemeket. A gond csak annyi, hogy ha van egy 1000 m\u00e9ret\u0171 t\u00f6mb\u00f6m, amibe 3 elemet kellene csak kiv\u00e1logatni, akkor is a mem\u00f3ri\u00e1ban foglalja az 1000 elemnyi helyet a 3 kedv\u00e9\u00e9rt.<\/p>\n
L\u00e1ssuk akkor a m\u00e1sik megold\u00e1st:<\/p>\n
\r\nint db = 0;\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 != 0 )\r\n {\r\n db++;\r\n }\r\n}\r\n\r\nint[] paratlan = new int[db];\r\n\r\ndb = 0;\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 != 0 )\r\n {\r\n paratlan[db] = tomb[i];\r\n db++;\r\n }\r\n}\r\n<\/pre>\nHa j\u00f3l megn\u00e9zed nem sokkal bonyolultabb, picit t\u00f6bbet kell g\u00e9pelni, \u00e9s ki kellett eg\u00e9sz\u00edteni a megsz\u00e1ml\u00e1l\u00e1s alap algoritmus\u00e1val:<\/p>\n
\n- 1-8 – Megsz\u00e1moljuk, h\u00e1ny elemet kell majd kiv\u00e1logatni az \u00faj t\u00f6mbbe.<\/li>\n
- 10 – L\u00e9trehozunk egy ugyanakkora t\u00f6mb\u00f6t.<\/li>\n
- 12-20 – Ez pedig pontosan az els\u0151 megold\u00e1s.<\/li>\n<\/ul>\n
Az eg\u00e9sz algoritmus kulcs momentuma a db v\u00e1ltoz\u00f3 haszn\u00e1lata!<\/strong> Ennek t\u00f6bb szerepe is van. El\u0151sz\u00f6r a kiv\u00e1logatand\u00f3 elemek darabsz\u00e1m\u00e1t gy\u0171jtj\u00fck bele, ut\u00e1na a k\u00f6vetkez\u0151 \u00fcres helyet jel\u00f6li az \u00faj t\u00f6mbben, v\u00e9g\u00fcl a kiv\u00e1logat\u00e1s v\u00e9gezt\u00e9vel az \u00faj t\u00f6mb m\u00e9ret\u00e9t jelenti, b\u00e1r ezt a t\u00f6mbb\u0151l \u00fagyis ki lehet nyerni a .length v\u00e1ltoz\u00f3b\u00f3l.<\/p>\n<\/a>Sz\u00e9tv\u00e1logat\u00e1s<\/h2>\nA sz\u00e9tv\u00e1logat\u00e1s algoritmusa a kiv\u00e1logat\u00e1s kib\u0151v\u00edt\u00e9se. Az alapfeladat az, hogy az eredeti t\u00f6mb minden elem\u00e9t k\u00e9t k\u00fcl\u00f6n t\u00f6mbbe kell elhelyezni. Felt\u00e9telezz\u00fck, hogy minden elem beker\u00fcl valamelyik \u00faj t\u00f6mbbe, vagyis nem hagyunk ki semmit sem. A kiv\u00e1logat\u00e1sn\u00e1l ennek a feladatnak a fel\u00e9t gyakorlatilag megoldottuk. Amit egy kiv\u00e1logat\u00e1sn\u00e1l kiv\u00e1logatunk, az itt az egyik t\u00f6mb elemeinek felelne meg. Az \u00f6sszes t\u00f6bbi elemet a m\u00e1sik t\u00f6mbbe pakoljuk. \u00cdgy m\u00e1r nem is t\u0171nik olyan neh\u00e9znek, igaz?<\/p>\n
A sz\u00e9tv\u00e1logat\u00e1s felt\u00e9tele minden esetben gyakorlatilag egyetlen felt\u00e9tel.<\/p>\n
\n- V\u00e1logassuk sz\u00e9t a t\u00f6mb elemeit 5-t\u0151l nagyobb \u00e9s nem nagyobb elemekre. (eml\u00e9kezz a rel\u00e1ci\u00f3s jelekre<\/a>!)<\/li>\n
- V\u00e1logassuk sz\u00e9t a t\u00f6mb elemeit 5-tel oszthat\u00f3 \u00e9s nem oszthat\u00f3 elemekre.<\/li>\n
- V\u00e1logassuk sz\u00e9t az elemeket egyjegy\u0171 \u00e9s nem egyjegy\u0171 sz\u00e1mokra<\/li>\n
- V\u00e1logassuk sz\u00e9t a t\u00f6mb elemeit p\u00e1ros \u00e9s p\u00e1ratlan elemekre.<\/li>\n<\/ul>\n
Ha megfigyelted, a feladatok j\u00f3 r\u00e9sze \u00fagy fogalmazza meg a felt\u00e9telt, hogy sz\u00e9tv\u00e1logatjuk valamilyen \u00e9s NEM valamilyen elemekre. Egy felt\u00e9tel \u00e9s annak az ellentettje minden elemet le kell hogy fedjen. Ez\u00e9rt sz\u00e9tv\u00e1logat\u00e1s, nem maradhat ki egyetlen elem sem. \u00c9s az utols\u00f3 esetben? Amelyik sz\u00e1m nem p\u00e1ros, az p\u00e1ratlan, teh\u00e1t ez is lefed minden sz\u00e1mot.<\/p>\n
A sz\u00e9tv\u00e1logat\u00e1sn\u00e1l is ugyanaz a dilemma lesz el\u0151sz\u00f6r, mint amit a kiv\u00e1logat\u00e1sn\u00e1l \u00edrtam:<\/p>\n
\n- Nem foglalkozok az \u00faj t\u00f6mb\u00f6k m\u00e9reteivel, a legrosszabb esetb\u0151l indulok ki, hogy minden elemet be kell tennem az egyik t\u00f6mbbe, a m\u00e1sik pedig \u00fcres marad. Ebben az esetben mindk\u00e9t \u00faj t\u00f6mb m\u00e9ret\u00e9nek az eredeti t\u00f6mb m\u00e9ret\u00e9t \u00e1ll\u00edtom be, \u00edgy a k\u00e9t \u00faj t\u00f6mb k\u00e9tszer annyi helyet foglal majd, amennyire val\u00f3ban sz\u00fcks\u00e9g lenne.<\/li>\n
- El\u0151re megsz\u00e1molom, h\u00e1ny elem felel meg a sz\u00e9tv\u00e1logat\u00e1s felt\u00e9tel\u00e9nek, ezut\u00e1n be\u00e1ll\u00edtom a k\u00edv\u00e1nt t\u00f6mbm\u00e9reteket, majd ut\u00e1na v\u00e1logatom sz\u00e9t az elemeket. Ez a legtakar\u00e9kosabb megold\u00e1s, mert mindk\u00e9t t\u00f6mb m\u00e9rete pontosan akkora lesz, amekkor\u00e1ra sz\u00fcks\u00e9gem lesz. Ha eml\u00e9kszel, a kiv\u00e1logat\u00e1sn\u00e1l itt egy megsz\u00e1ml\u00e1l\u00e1ssal b\u0151v\u00edtettem ki az alap megold\u00e1st.<\/li>\n<\/ol>\n
L\u00e1ssuk akkor az els\u0151 esetet. T\u00e9telezz\u00fck fel, hogy van egy adott m\u00e9ret\u0171 t\u00f6mb\u00f6m, felt\u00f6ltve elemekkel. V\u00e1logassuk sz\u00e9t az elemeket p\u00e1ros \u00e9s p\u00e1ratlan elemeket tartalmaz\u00f3 t\u00f6mb\u00f6kbe. Vedd \u00e9szre, hogy ez val\u00f3j\u00e1ban egyetlen felt\u00e9tel. Ami nem p\u00e1ros, az p\u00e1ratlan<\/p>\n
\r\nint[] paros = new int[tomb.length];\r\nint[] paratlan = new int[tomb.length];\r\n\r\nint dbparos = 0;\r\nint dbparatlan = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 == 0 )\r\n {\r\n paros[dbparos] = tomb[i]; \r\n dbparos++;\r\n }\r\n else\r\n {\r\n paratlan[dbparatlan] = tomb[i];\r\n dbparatlan++;\r\n }\r\n}\r\n<\/pre>\nHa a kiv\u00e1logat\u00e1s algoritmus\u00e1t meg\u00e9rtetted, akkor ezzel se lesz probl\u00e9ma. Nem v\u00e9letlen\u00fcl csak k\u00e9t r\u00e9szt emeltem ki. A kiv\u00e1logat\u00e1sn\u00e1l kellett egy sz\u00e1ml\u00e1l\u00f3, amelyben nyilv\u00e1ntartottam, hogy h\u00e1ny elemet v\u00e1logattam ki, ami egy\u00fattal azt is jelezte, hogy hol van az \u00faj t\u00f6mbben a k\u00f6vetkez\u0151 \u00fcres hely. Itt is hasonl\u00f3 a helyzet, csak itt k\u00e9t t\u00f6mb eset\u00e9n k\u00e9t k\u00fcl\u00f6n v\u00e1ltoz\u00f3ban kell t\u00e1rolni, hogy h\u00e1ny elem van az egyikben-m\u00e1sikban, \u00e9s ez\u00e1ltal melyik t\u00f6mbben hol van a k\u00f6vetkez\u0151 \u00fcres hely, ahova az elemeket pakolhatom. A bels\u0151 felt\u00e9tel sem sokat v\u00e1ltozott, ha a felt\u00e9telnek megfelel az elem, akkor berakom az egyik t\u00f6mbbe, ha nem, akkor mindenk\u00e9ppen (else) a m\u00e1sik t\u00f6mbbe kell tennem. Eml\u00e9kszel: minden elem beker\u00fcl valamelyik t\u00f6mbbe, ha nem az els\u0151be, akkor a m\u00e1sodikba, nem hagyhatok ki semmit sem.<\/p>\n
Ne felejtsd el, a k\u00e9t \u00faj t\u00f6mb m\u00e9rete nagyobb, mint amennyi t\u00e9nyleges elemet tartalmaznak.<\/strong> Az algoritmus ut\u00e1n a k\u00e9t darabsz\u00e1mot t\u00e1rol\u00f3 v\u00e1ltoz\u00f3 az, amib\u0151l megtudhatod, hogy mekkora val\u00f3j\u00e1ban a t\u00f6mb, amit kezelned kell. Nem a paros.length lesz az a hat\u00e1r, ameddig be kell j\u00e1rnod egy ciklussal, hanem a dbparos v\u00e1ltoz\u00f3.<\/p>\nL\u00e1ssuk akkor a m\u00e1sodik megold\u00e1st. Eml\u00e9keztet\u0151\u00fcl: megsz\u00e1molom h\u00e1ny elemet kell majd beraknom az egyik t\u00f6mbbe, akkor meglesznek a megfelel\u0151 t\u00f6mbm\u00e9retek.<\/p>\n
\r\nint parosdb = 0; \r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 == 0 )\r\n {\r\n parosdb++;\r\n }\r\n}\r\n\r\nint[] paros = new int[parosdb];\r\nint[] paratlan = new int[tomb.length-parosdb];\r\n\r\nparosdb = 0;\r\nparatlandb = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] % 2 == 0 )\r\n {\r\n paros[parosdb] = tomb[i];\r\n parosdb++;\r\n }\r\n else\r\n {\r\n paratlan[paratlandb] = tomb[i];\r\n paratlandb++;\r\n }\r\n}\r\n<\/pre>\nL\u00e1ssuk akkor a kiemelt r\u00e9szeket:<\/p>\n
\n- 1-9 – Megsz\u00e1molom, h\u00e1ny elem felel meg a sz\u00e9tv\u00e1logat\u00e1s felt\u00e9tel\u00e9nek.<\/li>\n
- 11-12 – L\u00e9trehozom a k\u00e9t megfelel\u0151 m\u00e9ret\u0171 t\u00f6mb\u00f6t. A p\u00e1ratlan t\u00f6mb m\u00e9ret\u00e9t \u00fagy kapom meg, hogy a t\u00f6mb elemeinek darabsz\u00e1m\u00e1b\u00f3l kivonom a p\u00e1rosok darabsz\u00e1m\u00e1t, \u00edgy megvan a p\u00e1ratlanok sz\u00e1ma.<\/li>\n
- 14-31 – Lenull\u00e1zom a k\u00e9t sz\u00e1ml\u00e1l\u00f3t, \u00e9s elv\u00e9gzem a sz\u00e9tv\u00e1logat\u00e1st az els\u0151 megold\u00e1snak megfelel\u0151en, csak itt m\u00e1r biztos lehetek benne, hogy mindk\u00e9t \u00faj t\u00f6mb\u00f6t teljesen felt\u00f6lt\u00f6m.<\/li>\n<\/ul>\n
Az el\u0151z\u0151h\u00f6z k\u00e9pest ez nyilv\u00e1n bonyolultabb megold\u00e1s. Cser\u00e9be takar\u00e9kosabb, m\u00e1sr\u00e9szt nem kell k\u00fcl\u00f6n t\u00e1rolni, hogy a t\u00f6mb\u00f6k val\u00f3j\u00e1ban meddig vannak felt\u00f6ltve, mivel a m\u00e9ret\u00fck pontosan megfelel a sz\u00e9tv\u00e1logatott elemek darabsz\u00e1m\u00e1nak.<\/p>\n
\u00c9s ha nem mindent v\u00e1logatok sz\u00e9t?<\/h4>\n
Ez az algoritmus csak abban az esetben haszn\u00e1lhat\u00f3, ha minden elemet sz\u00e9t kell v\u00e1logatni. Ez mondjuk a sz\u00e9tv\u00e1logat\u00e1s elv\u00e9b\u0151l is k\u00f6vetkezik, mivel nem hagyhatunk ki elemeket, k\u00fcl\u00f6nben nem sz\u00e9tv\u00e1logat\u00e1snak nevezn\u00e9nk. M\u00e9gis a p\u00e9lda kedv\u00e9\u00e9rt t\u00e9telezz\u00fck fel, hogy egy t\u00f6mbb\u0151l szeretn\u00e9nk a pozit\u00edv \u00e9s negat\u00edv sz\u00e1mokat k\u00e9t m\u00e1sik t\u00f6mbbe \u00e1tpakolni. Ebben az esetben m\u00e1r figyeln\u00fcnk kell arra, hogy mi a helyzet a null\u00e1kkal. Term\u00e9szetesen ezt is meg kell oldani, csak itt az elemek megsz\u00e1mol\u00e1s\u00e1n\u00e1l figyelembe kell venni, hogy kihagyunk elemeket, valamint a t\u00e9nyleges v\u00e1logat\u00e1sn\u00e1l is \u00fcgyelni kell r\u00e1juk. Sz\u00e1nd\u00e9kosan ker\u00fcltem a sz\u00e9tv\u00e1logat\u00e1s sz\u00f3t, mert ez val\u00f3j\u00e1ban a kihagyott elemek miatt nem az lesz. L\u00e1ssunk akkor erre egy p\u00e9ld\u00e1t.<\/p>\n
V\u00e1logassuk ki egy t\u00f6mb elemei k\u00f6z\u00fcl a pozit\u00edv \u00e9s negat\u00edv sz\u00e1mokat. (\u00c9szrevetted? Kiv\u00e1logat\u00e1s)<\/p>\n
\r\nint pozitivdb = 0;\r\nint negativdb = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] > 0 )\r\n {\r\n pozitivdb++;\r\n }\r\n else if( tomb[i] < 0 )\r\n {\r\n negativdb++;\r\n }\r\n}\r\nint[] pozitiv = new int[pozitivdb];\r\nint[] negativ = new int[negativdb];\r\n\r\npozitivdb = 0;\r\nnegativdb = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] > 0 )\r\n {\r\n pozitiv[pozitivdb] = tomb[i];\r\n pozitivdb++;\r\n }\r\n else if( tomb[i] < 0 )\r\n {\r\n negativ[negativdb] = tomb[i];\r\n negativdb++;\r\n }\r\n}\r\n<\/pre>\n\n- 1-13 – Egy ciklusban megsz\u00e1molom a pozit\u00edv \u00e9s negat\u00edv sz\u00e1mokat.<\/li>\n
- 15-16 – L\u00e9trehozom nekik a megfelel\u0151 m\u00e9ret\u0171 t\u00f6mb\u00f6ket.<\/li>\n
- \u00c9s kiv\u00e1logatom<\/strong> \u0151ket egyetlen ciklusban.<\/li>\n<\/ul>\n
Ez gyakorlatilag k\u00e9t kiv\u00e1logat\u00e1s egy ciklusba pakolva, a k\u00e9t felt\u00e9telnek (pozit\u00edv vagy negat\u00edv) l\u00e9nyeg\u00e9ben semmi k\u00f6ze egym\u00e1shoz, a sz\u00e1ml\u00e1l\u00f3ik is teljesen f\u00fcggetlenek, mert nem tudom, hogy a k\u00e9t felt\u00e9tel lefedi-e az \u00f6sszes eredeti elemet vagy sem. Ha a k\u00e9t felt\u00e9tel minden elemet besorol valahova, akkor sz\u00e9tv\u00e1logat\u00e1s, egy\u00e9bk\u00e9nt k\u00e9t egym\u00e1st\u00f3l f\u00fcggetlen kiv\u00e1logat\u00e1sr\u00f3l besz\u00e9l\u00fcnk.<\/p>\n
<\/a>Metszet<\/h2>\nA metszet algoritmus egy kis magyar\u00e1zatot ig\u00e9nyel. Az alap algoritmusok metszetk\u00e9pz\u00e9se nem egyezik meg a halmazelm\u00e9letben tanult metszettel. A halmazt elemek sokas\u00e1g\u00e1nak tekintj\u00fck, ahol az elemeknek nincs sorrendje, \u00e9s minden elem csak egyszer szerepelhet a halmazban. Ez a t\u00f6mb\u00f6kn\u00e9l nyilv\u00e1nval\u00f3an nem \u00e1ll fenn. A halmazokn\u00e1l metszetk\u00e9nt azon elemek halmaz\u00e1t vessz\u00fck, amelyek mindk\u00e9t halmazban megtal\u00e1lhat\u00f3ak.<\/p>\n
T\u00f6mb\u00f6k eset\u00e9n ez azt jelenti, hogy az egyik t\u00f6mbb\u0151l vessz\u00fck azokat az elemeket, amelyek benne vannak a m\u00e1sikban. Ezzel az algoritmussal csak az a bajom, hogy nem mindegy, hogy melyik t\u00f6mb oldal\u00e1r\u00f3l kezdj\u00fck ez a dolgot. L\u00e1ssuk a k\u00f6vetkez\u0151 p\u00e9ld\u00e1t, hogy mir\u0151l is van sz\u00f3.<\/p>\n
\r\n{2,2,3,4}\r\n{3,5,2,6,6}\r\n<\/pre>\nHa az els\u0151 t\u00f6mb elemeib\u0151l hagyjuk meg azokat, amelyek benne vannak a m\u00e1sodikban, akkor ezt az eredm\u00e9nyt kapjuk:<\/p>\n
\r\n{2,2,3}\r\n<\/pre>\nHa a m\u00e1sodik t\u00f6mb elemeib\u0151l hagyjuk meg azokat, amelyek benne vannak az els\u0151ben, akkor ezt az eredm\u00e9nyt kapjuk:<\/p>\n
\r\n{3,2}\r\n<\/pre>\nNyilv\u00e1n l\u00e1tszik mi a gond. Ez pedig abb\u00f3l fakad, hogy egy elem t\u00f6bbsz\u00f6r is lehet egy t\u00f6mb eleme. A sorsz\u00e1moz\u00e1s miatt ezek egy\u00e9rtelm\u0171en megk\u00fcl\u00f6nb\u00f6ztethet\u0151ek. A halmazban viszont az elemek nem sorsz\u00e1mozottak, ez\u00e9rt k\u00e9t azonos \u00e9rt\u00e9k\u0171 elemet nem k\u00fcl\u00f6nb\u00f6ztethetn\u00e9nk meg. Az algoritmus nem foglalkozik ezzel a probl\u00e9m\u00e1val, \u00e9s nek\u00fcnk sem kell. M\u00e1s k\u00e9rd\u00e9s, hogy meg tudn\u00e1nk oldani azt is, hogy minden elem egyszer szerepeljen csak a metszetben, k\u00e9s\u0151bb ezt is megmutatom.<\/p>\n
Mint m\u00e1r fent eml\u00edtettem, az algoritmus annyib\u00f3l \u00e1ll, hogy az vessz\u00fck az egyik t\u00f6mb elemei k\u00f6z\u00fcl azokat, amelyek benne vannak a m\u00e1sikban. N\u00e9zz\u00fck meg jobban, mi is ez? Kiv\u00e1logatjuk az egyik t\u00f6mb elemei k\u00f6z\u00fcl azokat, amelyek megfelelnek annak a felt\u00e9telnek, hogy benne vannak a m\u00e1sik t\u00f6mbben. Kiv\u00e1logat\u00e1s, amiben van egy eld\u00f6nt\u00e9s. A metszetk\u00e9pz\u00e9s teh\u00e1t k\u00e9t tanult algoritmus kombin\u00e1ci\u00f3ja.<\/p>\n
\r\nint[] t1 = new int[] {2,2,3,4};\r\nint[] t2 = new int[] {3,5,2,6,6};\r\nint[] metszet = new int[t1.length];\r\n\r\nint j;\r\nint db = 0;\r\nfor( int i = 0; i < t1.length; i++ )\r\n{\r\n j = 0;\r\n while( j < t2.length && t2[j] != t1[i] )\r\n {\r\n j++;\r\n }\r\n if( j < t2.length )\r\n {\r\n metszet[db] = t2[j];\r\n db++;\r\n }\r\n}\r\n<\/pre>\nL\u00e1ssuk a kiemelt r\u00e9szek magyar\u00e1zat\u00e1t:<\/p>\n
\n- 3 – A metszet t\u00f6mb m\u00e9rete akkora, mint az els\u0151 t\u00f6mb m\u00e9rete, hiszen lehet, hogy annak minden eleme megtal\u00e1lhat\u00f3 a m\u00e1sikban. Term\u00e9szetesen a kiv\u00e1logat\u00e1shoz hasonl\u00f3an itt is \u00fcgyelni kell arra, hogy nem felt\u00e9tlen ker\u00fcl minden elem a metszet t\u00f6mbbe, ez\u00e9rt majd a db v\u00e1ltoz\u00f3 fogja t\u00e1rolni a metszet t\u00f6mb val\u00f3di elemeinek sz\u00e1m\u00e1t.<\/li>\n
- 7 – Ebben a sorban elkezd\u00fcnk egy kiv\u00e1logat\u00e1st, vagyis elindulunk az els\u0151 t\u00f6mb\u00f6n azt keresve, hogy ezek k\u00f6z\u00fcl melyiket kell majd \u00e1trakni a metszetbe.<\/li>\n
- 9-14 – Ez gyakorlatilag az eld\u00f6nt\u00e9s algoritmusa, addig haladunk a m\u00e1sodik t\u00f6mb elemein, \u00e9s addig megy\u00fcnk, am\u00edg nem tal\u00e1lunk egyez\u00e9st a m\u00e1sodik t\u00f6mb eleme \u00e9s az els\u0151 t\u00f6mb \u00e9ppen aktu\u00e1lis eleme k\u00f6z\u00f6tt. Ezt az algoritmust most nem magyar\u00e1zn\u00e1m el \u00fajra, de ami a l\u00e9nyeg: ha az elemet megtal\u00e1ltuk, akkor visszat\u00e9r\u00fcnk a kiv\u00e1logat\u00e1shoz<\/li>\n
- 16-17 – Ha tal\u00e1ltunk olyan els\u0151 t\u00f6mbbeli elemet, ami megfelelt a felt\u00e9tel\u00fcnknek (benne van a m\u00e1sodikban is), akkor berakjuk a metszet t\u00f6mbbe, \u00e9s n\u00f6velj\u00fck a sz\u00e1ml\u00e1l\u00f3j\u00e1t. Ez a kiv\u00e1logat\u00e1s algoritmus v\u00e9ge.<\/li>\n<\/ul>\n
Metszet egyedi elemekkel<\/h4>\n
Mi van akkor, ha val\u00f3ban csak annyit szeretn\u00e9nk megtudni, hogy mik azok a sz\u00e1mok, melyek mindk\u00e9t t\u00f6mbben megtal\u00e1lhat\u00f3ak? Ha valami t\u00f6bbsz\u00f6r szerepel a t\u00f6mbben, att\u00f3l mint sz\u00e1m csak egyszer szerepel. Ez nem alap algoritmus, hanem az eddig tanultakat kell alkalmazni. Ak\u00e1r teljesen elt\u00e9r\u0151 megold\u00e1sokat is adhatunk:<\/p>\n
\n- A k\u00e9t t\u00f6mb k\u00f6z\u00fcl az els\u0151b\u0151l l\u00e9trehozok egy olyan t\u00f6mb\u00f6t, ami az eredetiben szerepel\u0151 sz\u00e1mokat csak egyszer tartalmazza. Majd ha err\u0151l az oldalr\u00f3l metszetet k\u00e9pzek, akkor a metszetben is minden elem csak egyszer fog szerepelni.<\/li>\n
- Az els\u0151 t\u00f6mbb\u0151l csak akkor teszek be egy sz\u00e1mot a metszetbe, ha benne van a m\u00e1sodikban, \u00e9s m\u00e9g nincs benne a metszetben. Vagyis a kiv\u00e1logat\u00e1son bel\u00fcl k\u00e9t eld\u00f6nt\u00e9sre van sz\u00fcks\u00e9gem, melyeknek egyszerre kell teljes\u00fclnie. Azzal m\u00e9g finom\u00edthatom, hogy ha a m\u00e1sodik t\u00f6mbben nincs benne, akkor felesleges a metszetben ellen\u0151rizni, mert akkor oda semmik\u00e9ppen nem ker\u00fclhetett be.<\/li>\n<\/ol>\n
L\u00e1ssuk az els\u0151 megold\u00e1st:<\/p>\n
\r\nint[] t1 = new int[] { 2, 2, 3, 4 };\r\nint[] t2 = new int[] { 3, 5, 2, 6, 6 };\r\nint[] metszet = new int[t1.length];\r\n\r\nint[] egyedi = new int[t1.length];\r\nint dbe = 0;\r\n\r\nint j;\r\nfor( int i = 0; i < t1.length; i++ )\r\n{\r\n j = 0;\r\n while( j < dbe && t1[i] != egyedi[j] )\r\n {\r\n j++;\r\n }\r\n if( j == dbe )\r\n {\r\n egyedi[dbe] = t1[i];\r\n dbe++;\r\n }\r\n}\r\n\r\nint db = 0;\r\nfor( int i = 0; i < dbe; i++ )\r\n{\r\n j = 0;\r\n while(j < t2.length && t2[j] != egyedi[i])\r\n {\r\n j++;\r\n }\r\n if( j < t2.length )\r\n {\r\n metszet[db] = t2[j];\r\n db++;\r\n }\r\n}\r\n<\/pre>\nMit is csin\u00e1lunk pontosan?<\/p>\n
\n- 5 – L\u00e9trehozom azt a t\u00f6mb\u00f6t, ahova kiv\u00e1logatom az els\u0151 t\u00f6mb sz\u00e1mait. Ennek m\u00e9rete az eredetivel megegyez\u0151, mert lehet, hogy egyik sz\u00e1m sem szerepel t\u00f6bbsz\u00f6r, akkor mindet \u00e1t kell pakolni.<\/li>\n
- 6 – L\u00e9trehozok egy sz\u00e1ml\u00e1l\u00f3t, hogy nyilv\u00e1ntartsam, val\u00f3j\u00e1ban h\u00e1ny elem lesz az egyedi t\u00f6mbben.<\/li>\n
- 8-21 – Kiv\u00e1logatom az egyedi sz\u00e1mokat. (kiv\u00e1logat\u00e1sban egy eld\u00f6nt\u00e9s) Fontos, hogy akkor rakom bele az egyedi t\u00f6mbbe a sz\u00e1mot, ha az eld\u00f6nt\u00e9s hamis eredm\u00e9nyt ad, vagyis nincs benne: if( j == dbe )<\/em><\/li>\n
- 23-36 – Ez pedig a metszetk\u00e9pz\u00e9s algoritmusa, de az egyedi t\u00f6mb \u00e9s a m\u00e1sodik k\u00f6z\u00f6tt. A 24-es sorban fontos a felt\u00e9tel, hogy az egyedi t\u00f6mbnek nem az \u00f6sszes elem\u00e9t kell vizsg\u00e1lni, hanem csak addig, ameddig val\u00f3ban vannak benne elemek. Ezt a saj\u00e1t dbe sz\u00e1ml\u00e1l\u00f3ja t\u00e1rolja.<\/li>\n<\/ul>\n
A k\u00e9t r\u00e9szfeladat (egyedi t\u00f6mb el\u0151\u00e1ll\u00edt\u00e1sa, majd metszetk\u00e9pz\u00e9s) ugyanarr\u00f3l a t\u0151r\u0151l fakad, hiszen mindk\u00e9t esetben egy elemr\u0151l akarom eld\u00f6nteni, hogy benne van-e egy t\u00f6mbben. A k\u00fcl\u00f6nbs\u00e9g csak az, hogy egyedi elemek v\u00e1logat\u00e1sakor akkor rakom bele, ha nincs m\u00e9g benne, metszetk\u00e9pz\u00e9sn\u00e9l pedig akkor rakom bele, ha benne van.<\/p>\n
N\u00e9zz\u00fck a m\u00e1sik megold\u00e1st, amikor a k\u00e9t eld\u00f6nt\u00e9st teszek a kiv\u00e1logat\u00e1sba:<\/p>\n
\r\nint[] t1 = new int[] { 2, 2, 3, 4 };\r\nint[] t2 = new int[] { 3, 5, 2, 6, 6 };\r\nint[] metszet = new int[t1.length];\r\n\r\nint j;\r\nint jm;\r\nint db = 0;\r\nfor( int i = 0; i < t1.length; i++ )\r\n{\r\n j = 0;\r\n while( j < t2.length && t2[j] != t1[i] )\r\n {\r\n j++;\r\n }\r\n if( j < t2.length )\r\n {\r\n jm = 0;\r\n while( jm < db && metszet[jm] != t1[i] )\r\n {\r\n jm++;\r\n }\r\n if( jm == db )\r\n {\r\n metszet[db] = t1[i];\r\n db++;\r\n }\r\n }\r\n}\r\n<\/pre>\nL\u00e1ssuk a l\u00e9nyegi r\u00e9szeket:<\/p>\n
\n- 10-14 – Eld\u00f6ntj\u00fck, hogy az els\u0151 t\u00f6mb eleme benne van-e a m\u00e1sodikban.<\/li>\n
- 15 – Ha igen, akkor<\/li>\n
- 15-27 – Eld\u00f6ntj\u00fck, hogy benne van-e a metszetben.<\/li>\n
- 22 – Csak akkor tessz\u00fck be a metszetbe, ha m\u00e9g nincs benne. Ha m\u00e1r egyszer betett\u00fcnk ilyen sz\u00e1mot, akkor nem tessz\u00fck bele m\u00e9g egyszer.<\/li>\n<\/ul>\n
Ez a megold\u00e1s tal\u00e1n r\u00f6videbb \u00e9s egyszer\u0171bb is, mint a m\u00e1sik, \u00e9s minden esetben egyedi elemeket tartalmaz\u00f3 metszet t\u00f6mb\u00f6t kapunk.<\/p>\n
Term\u00e9szetesen ez a metszetk\u00e9pz\u00e9s algoritmus t\u00f6bb hasonl\u00f3 feladatn\u00e1l is haszn\u00e1lhat\u00f3, hiszen ha metszetet tudunk k\u00e9pezni, akkor olyan k\u00e9rd\u00e9sekre is v\u00e1laszt kaphatunk ennek seg\u00edts\u00e9g\u00e9vel, hogy van-e k\u00e9t t\u00f6mbnek azonos eleme, h\u00e1ny k\u00f6z\u00f6s eleme van k\u00e9t t\u00f6mbnek, stb.<\/p>\n
Komplex feladat<\/h2>\n
L\u00e1ssunk egy komplexebb feladatot. Adott egy 10 elem\u0171 t\u00f6mb melyet v\u00e9letlen sz\u00e1mokkal t\u00f6lt\u00f6tt\u00fcnk fel a [-9;9] intervallumb\u00f3l. \u00cdrjuk ki n\u00f6vekv\u0151 sorrendben a t\u00f6mbben szerepl\u0151 p\u00e1ros sz\u00e1mokat.<\/p>\n
\r\n\/**\r\n *\r\n * @author http:\/\/webotlet.hu\r\n *\/\r\npackage webotlet_alapalg_komplex;\r\n\r\npublic class Webotlet_alapalg_komplex\r\n{\r\n\r\n public static void main(String[] args)\r\n {\r\n int[] tomb = new int[10];\r\n\r\n for (int i = 0; i < tomb.length; i++)\r\n {\r\n tomb[i] = (int) (Math.random() * 19) - 9;\r\n }\r\n\r\n for (int i = 0; i < tomb.length; i++)\r\n {\r\n System.out.print(tomb[i] + " ");\r\n }\r\n\r\n System.out.println();\r\n\r\n int db = 0;\r\n for (int i = 0; i < tomb.length; i++)\r\n {\r\n if (tomb[i] % 2 == 0)\r\n {\r\n db++;\r\n }\r\n }\r\n\r\n int[] paros = new int[db];\r\n\r\n db = 0;\r\n for (int i = 0; i < tomb.length; i++)\r\n {\r\n if (tomb[i] % 2 == 0)\r\n {\r\n paros[db] = tomb[i];\r\n db++;\r\n }\r\n }\r\n\r\n int csere;\r\n for (int i = 0; i < db - 1; i++)\r\n {\r\n for (int j = i + 1; j < db; j++)\r\n {\r\n if (paros[i] > paros[j])\r\n {\r\n csere = paros[i];\r\n paros[i] = paros[j];\r\n paros[j] = csere;\r\n }\r\n }\r\n }\r\n\r\n for (int i = 0; i < db; i++)\r\n {\r\n System.out.print(paros[i] + " ");\r\n }\r\n \r\n System.out.println();\r\n }\r\n}\r\n<\/pre>\nEz egy t\u00f6k\u00e9letes feladat arra, hogy az eddig tanultakat \u00f6sszefoglalja. Sok ismer\u0151s r\u00e9szletet l\u00e1thatunk benne, de l\u00e1ssuk akkor r\u00e9szenk\u00e9nt:<\/p>\n
\n- 12-17 – Adott m\u00e9ret\u0171 t\u00f6mb l\u00e9trehoz\u00e1sa, majd felt\u00f6lt\u00e9se v\u00e9letlen sz\u00e1mokkal.<\/li>\n
- 19-22 – A kisorsolt t\u00f6mb ki\u00edrat\u00e1sa.<\/li>\n
- 24 – Sordob\u00e1s a sorsolt t\u00f6mb ki\u00edrat\u00e1sa ut\u00e1n, hogy ne folyjon egybe majd a rendezett t\u00f6mb ki\u00edrat\u00e1s\u00e1val.<\/li>\n
- 26-33 – A kiv\u00e1logat\u00e1shoz megsz\u00e1moljuk, h\u00e1ny elemet kell majd \u00e1trakni az \u00faj t\u00f6mbbe.<\/li>\n
- 35 – L\u00e9trehozzuk az \u00faj t\u00f6mb\u00f6t.<\/li>\n
- 37-45 – Kiv\u00e1logatjuki (\u00e1tm\u00e1soljuk) a p\u00e1ros sz\u00e1mokat az \u00faj t\u00f6mbbe.<\/li>\n
- 47-59 – Rendezz\u00fck az \u00faj t\u00f6mb\u00f6t.<\/li>\n
- 61-64 – Ki\u00edrjuk a kiv\u00e1logatott \u00e9s rendezett \u00faj t\u00f6mb\u00f6t.<\/li>\n
- 66 – Egy b\u00f3nusz sordob\u00e1s a v\u00e9g\u00e9re, hogy ha b\u0151v\u00edten\u00e9m a programot, akkor az \u00faj ki\u00edrat\u00e1s \u00faj sorban kezd\u0151dj\u00f6n.<\/li>\n<\/ul>\n
Adott teh\u00e1t egy els\u0151re bonyolultnak t\u0171n\u0151 feladat, amit sz\u00e9tbontottuk olyan r\u00e9szekre, melyeket m\u00e1r k\u00fcl\u00f6n-k\u00fcl\u00f6n meg tudunk oldani. Ezeket a k\u00e9sz megold\u00e1sokat (t\u00f6mb felt\u00f6lt\u00e9s, ki\u00edrat\u00e1s, megsz\u00e1ml\u00e1l\u00e1s, kiv\u00e1logat\u00e1s, rendez\u00e9s, stb) megfelel\u0151 sorrendben hib\u00e1tlanul<\/strong> \u00f6sszerakjuk, \u00e9s k\u00e9sz a feladat teljes megold\u00e1sa. Ugye \u00edgy jobban belegondolva nem is olyan neh\u00e9z? Felt\u00e9ve hogy az eddigi tananyagokat m\u00e1r k\u00e9szs\u00e9gszinten alkalmazni tudod. Sokszor az a legnehezebb feladat, hogy felismerj\u00fck azt, hogy az aktu\u00e1lis feladat milyen kisebb alkot\u00f3elemekre bonthat\u00f3, melyekre m\u00e1r k\u00e9sz megold\u00e1saink vannak. Ha ez a r\u00e9szekre bont\u00e1s megy, akkor gyakorlatilag sokszor g\u00e9pel\u00e9si feladatt\u00e1 tudjuk egyszer\u0171s\u00edteni a feladatok nagy r\u00e9sz\u00e9nek megold\u00e1s\u00e1t.<\/p>\nEljutott\u00e1l az alap leck\u00e9k v\u00e9g\u00e9re. Rem\u00e9lhet\u0151leg minden eddigi lecke anyag\u00e1val tiszt\u00e1ban vagy, \u00e9s azokat megfelel\u0151en alkalmazni is tudod. Akkor most sebess\u00e9get v\u00e1ltunk, j\u00f6hetnek a halad\u00f3 leck\u00e9k.<\/p>\n
K\u00f6vetkez\u0151 lecke: T\u00f6bbdimenzi\u00f3s t\u00f6mb\u00f6k <\/a><\/h4>\n","protected":false},"excerpt":{"rendered":"Alap algoritmusok, avagy mindenki tud programozni A programoz\u00e1ssal sokszor az a baj \u2013 f\u0151leg ha k\u00f6telez\u0151 tant\u00e1rgy \u00e9s nem szeretj\u00fck \u2013 hogy gondolkodni kell. Igaz, mondhatn\u00e1m ezt a matematik\u00e1ra, fizik\u00e1ra is, de egyik tant\u00e1rgy sem annyira szerte\u00e1gaz\u00f3 a helyes megold\u00e1sok Tov\u00e1bb Java programoz\u00e1s 16. – Alap algoritmusok<\/span>