Az egyes programoz\u00e1s feladatok forr\u00e1sai nagyban k\u00fcl\u00f6nb\u00f6znek egym\u00e1st\u00f3l. A forr\u00e1sok k\u00fcl\u00f6nb\u00f6z\u0151s\u00e9ge tekintet\u00e9ben nem akarok t\u00falzottan r\u00e9szletekbe bocs\u00e1tkozni, puszt\u00e1n egyetlen szempontot vizsg\u00e1ln\u00e9k, hogy az adatok rendezett vagy nem rendezett form\u00e1ban \u00e1llnak rendelkez\u00e9sre.<\/p>\n
Mert sokkal t\u00f6bb inform\u00e1ci\u00f3t tartalmaz egy rendezett adathalmaz a rendezetlenhez k\u00e9pest. L\u00e1ssunk erre egy egyszer\u0171 p\u00e9ld\u00e1t.<\/p>\n
Adott egy t\u00f6mb, ami mondjuk a [0;9] intervallumb\u00f3l tartalmaz v\u00e9letlen eg\u00e9sz sz\u00e1mokat. R\u00e1n\u00e9z\u00e9sre milyen sz\u00e1mok hi\u00e1nyoznak a k\u00f6vetkez\u0151 t\u00f6mbb\u0151l?<\/p>\n
\r\n{5,6,2,1,7,1,1,9,8,9,5,2,3,7,6,5,6,2}\r\n<\/pre>\nKicsit macer\u00e1s megmondani. Nem lehetetlen, de az\u00e9rt beletelik egy kis id\u0151be. Na \u00e9s most?<\/p>\n
\r\n{1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9}\r\n<\/pre>\nA k\u00e9t t\u00f6mb ugyanazokat az \u00e9rt\u00e9keket tartalmazza, csak a m\u00e1sodik esetben a sz\u00e1mok n\u00f6vekv\u0151 sorrendben \u00e1llnak.<\/p>\n
Nem egy ilyen eset van, amikor valamilyen feladatot k\u00f6nnyebben meg tudunk oldani abban az esetben, ha rendezett adatokkal dolgozunk. Ez a lecke arr\u00f3l sz\u00f3l, hogy milyen t\u00edpus\u00fa feladatokra kaphatunk rendezett t\u00f6mb\u00f6k eset\u00e9n k\u00f6nnyebben (vagy m\u00e1sk\u00e9pp) v\u00e1laszt a kevert sorrend\u0171 adatokhoz k\u00e9pest.<\/p>\n
Ok\u00e9, kicsit csaltam, mert p\u00e9ld\u00e1ul az el\u0151z\u0151 k\u00e9rd\u00e9sre van egy olyan megold\u00e1s<\/a>, ami leegyszer\u0171s\u00edti a feladatot. R\u00e1ad\u00e1sul ez a megold\u00e1s t\u00f6bbf\u00e9le feladatt\u00edpusra is haszn\u00e1lhat\u00f3. Egy gond van, volt m\u00e1r olyan emelt \u00e9retts\u00e9gi feladat, ahol ezeket a megold\u00e1sokat nem lehetett haszn\u00e1lni, mert tilos volt t\u00e1rolni az adatokat. Akkor bizony menet k\u00f6zben kellett feldolgozni \u0151ket.<\/p>\nMi\u00e9rt t\u00f6mb, mi\u00e9rt nem lista?<\/h2>\n
Adatt\u00e1rol\u00e1sra a feladatok t\u00f6bbs\u00e9g\u00e9ben t\u00f6mb\u00f6ket haszn\u00e1lunk. Most j\u00f6hetn\u00e9l azzal, hogy a list\u00e1k sok tekintetben jobbak a t\u00f6mb\u00f6kn\u00e9l, ezt senki nem vitatja. A helyzet azonban az, hogy a list\u00e1kkal a tanul\u00e1s sor\u00e1n sokszor id\u0151 hi\u00e1ny\u00e1ban nincs id\u0151nk foglalkozni, \u00f6r\u00fcl\u00fcnk, ha a t\u00f6mb\u00f6kkel v\u00e9gz\u00fcnk. Sz\u00f3val egyel\u0151re maradunk a t\u00f6mb\u00f6kn\u00e9l. Amik itt elhangzanak, azok a list\u00e1kra is igazak lesznek. A list\u00e1t nagyon szeretj\u00fck, mert n\u00e9h\u00e1ny feladatra m\u00e9g ak\u00e1r egy\u00e9b be\u00e9p\u00edtett megold\u00e1sok is l\u00e9teznek, amik leegyszer\u0171s\u00edtik annak megold\u00e1s\u00e1t.<\/p>\n
Rendezni, de hogyan?<\/h2>\n
A feladatok t\u00f6bb esetben is olyan forr\u00e1st biztos\u00edtanak, ahol az adatok bizonyos szempont szerint rendezettek. \u00d6sszetett adatok eset\u00e9n, ami nyilv\u00e1n j\u00f3val gyakoribb, a rendez\u00e9s sokf\u00e9le szempont t\u00f6rt\u00e9nhet, \u00e9s nem biztos, hogy pont olyan m\u00f3don rendezettek az adatok, amire nek\u00fcnk \u00e9ppen sz\u00fcks\u00e9g\u00fcnk lenne.<\/p>\n
Amennyiben \u00f6sszetett adatokr\u00f3l besz\u00e9l\u00fcnk (objektumok), a rendez\u00e9s t\u00f6bb r\u00e9sz-adatra is megval\u00f3s\u00edthat\u00f3, ezek az adatok r\u00e1ad\u00e1sul nem kell, hogy azonos t\u00edpus\u00faak legyenek. K\u00e9pzeld el, hogy a forr\u00e1sban egy-egy aut\u00f3 adatai szerepelnek, az aut\u00f3 m\u00e1rk\u00e1ja, \u00e9s az aut\u00f3 \u00e1ltal futott km. Az adatokat most csak nyers form\u00e1ban v\u00e1gom be ide:<\/p>\n
Toyota;70337
\nSuzuki;80852
\nHonda;96352
\nSkoda;27825
\nRenault;29802
\nHonda;76084
\nOpel;34258
\nSuzuki;64809
\nSuzuki;17348
\nToyota;10469
\nOpel;20875<\/p>\n
Ezeket az adatokat rendezhetem csak km szerint n\u00f6vekv\u0151 sorrendbe, vagy m\u00e1rka szerint abc \u00e9s azon bel\u00fcl km szerint n\u00f6vekv\u0151 sorrendbe. Hogy ez ut\u00f3bbit hogyan oldhatod meg, ebben a leck\u00e9ben<\/a> megtal\u00e1lod.<\/p>\nA rendezett adatok teh\u00e1t sokkal t\u00f6bb inform\u00e1ci\u00f3t hordoznak a kevert adatokhoz k\u00e9pest. L\u00e1ssuk p\u00e9ld\u00e1ul milyeneket!<\/p>\n
Rendezett t\u00f6mb\u00f6k rejtett inform\u00e1ci\u00f3i<\/h2>\n
Ha az adatok eredetileg kevertek, akkor mindenk\u00e9ppen rendezni kell, hogy ezek a megold\u00e1sok m\u0171k\u00f6djenek. A rendez\u00e9s ir\u00e1nya (n\u00f6vekv\u0151 vagy cs\u00f6kken\u0151) nem minden feladatn\u00e1l sz\u00e1m\u00edt, de egyes esetekben kicsit m\u00f3dos\u00edt n\u00e9h\u00e1ny utas\u00edt\u00e1son. A k\u00f6vetkez\u0151kben p\u00e1r p\u00e9ld\u00e1t mutatn\u00e9k be, hogy mi minden hat\u00e1rozhat\u00f3 meg egy rendezett t\u00f6mbb\u0151l. A megold\u00e1sok l\u00e9nyegi r\u00e9sz\u00e9t alaphelyzetben elrejtem, csak a kiindul\u00f3 adatokat mutatom meg. Mindezt puszt\u00e1n az\u00e9rt, hogy te is pr\u00f3b\u00e1lkozhass, miel\u0151tt megn\u00e9zn\u00e9d a megold\u00e1st.<\/p>\n
\n- H\u00e1nyf\u00e9le egyedi \u00e9rt\u00e9k van?<\/a><\/li>\n
- Melyik \u00e9rt\u00e9kb\u0151l van a legt\u00f6bb?<\/a><\/li>\n
- Melyik \u00e9rt\u00e9kb\u0151l van a legkevesebb?<\/a><\/li>\n
- Van-e hi\u00e1nyz\u00f3 \u00e9rt\u00e9k?<\/a><\/li>\n
- Mennyi a legnagyobb k\u00fcl\u00f6nbs\u00e9g?<\/a><\/li>\n
- Mennyi a legkisebb k\u00fcl\u00f6nbs\u00e9g?<\/a><\/li>\n
- Melyik a legnagyobb?<\/a><\/li>\n
- Melyik a legkisebb?<\/a><\/li>\n
- Mekkora az intervallum?<\/a><\/li>\n<\/ul>\n
<\/a>H\u00e1nyf\u00e9le egyedi \u00e9rt\u00e9k van a t\u00f6mbben?<\/h3>\nSokszor sz\u00fcks\u00e9g\u00fcnk lehet arra, hogy meghat\u00e1rozzuk, h\u00e1nyf\u00e9le egyedi adat tal\u00e1lhat\u00f3 egy t\u00f6mbben. Ez a sz\u00e1m nem felt\u00e9tlen\u00fcl egyezik meg a t\u00f6mb m\u00e9ret\u00e9vel, hiszen az adatokban ism\u00e9tl\u0151d\u00e9sek is el\u0151fordulhatnak.<\/p>\n
H\u00e1nyf\u00e9le sz\u00e1m van a t\u00f6mbben?<\/p>\n
\r\nint[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint db = 1;\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i] != tomb[i + 1] )\r\n {\r\n db++;\r\n }\r\n}\r\nSystem.out.println("A tombben " + db + " kulonfele ertek van.");\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
Ez a feladat val\u00f3j\u00e1ban egy megsz\u00e1ml\u00e1l\u00e1s, de nem a m\u00e1r ismert alap algoritmus. Itt az adatok k\u00fcl\u00f6nb\u00f6z\u0151s\u00e9g\u00e9t sz\u00e1moljuk meg. Abb\u00f3l indulok ki, hogy legal\u00e1bb egyf\u00e9le \u00e9rt\u00e9k van a t\u00f6mbben (mind ugyanaz), ez\u00e9rt a sz\u00e1ml\u00e1l\u00f3t 1-r\u0151l ind\u00edtom. Ez persze kap\u00e1sb\u00f3l ellentmond a megsz\u00e1ml\u00e1l\u00e1s alap algoritmus\u00e1nak, de ez nem pontosan az, hanem annak kib\u0151v\u00edt\u00e9se. Azt sz\u00e1molom meg, hogy h\u00e1nyszor v\u00e1ltozik az sz\u00e1m az el\u0151z\u0151h\u00f6z k\u00e9pest. az\u00e9rt kell 1-r\u0151l ind\u00edtani a sz\u00e1ml\u00e1l\u00f3t, mert egyfajta sz\u00e1m biztosan van a t\u00f6mbben, lehet, hogy mind egyforma. Itt a rendez\u00e9s ir\u00e1nya nem is sz\u00e1m\u00edt, hiszen csak azt sz\u00e1moljuk, h\u00e1ny szomsz\u00e9dos \u00e9rt\u00e9k nem ugyanaz.<\/p>\n
Ez a m\u00f3dszer r\u00e1ad\u00e1sul nem csak sz\u00e1mokra, sz\u00f6vegekre is m\u0171k\u00f6dik, felt\u00e9telezve, hogy azokat m\u00e1r rendezt\u00fck:<\/p>\n
\r\nString[] nevek = new String[]{ "Bela", "Eva", "Eva", "Pal", "Pal" };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint db = 1;\r\nfor( int i = 0; i < nevek.length - 1; i++ )\r\n{\r\n if( !nevek[i].equals(nevek[i + 1]) )\r\n {\r\n db++;\r\n }\r\n}\r\nSystem.out.println("A tombben " + db + " kulonfele nev van.");\r\n<\/pre>\n[\/expand]<\/p>\n
Nem is kell t\u00f6bb magyar\u00e1zat az el\u0151z\u0151 p\u00e9ld\u00e1hoz, hiszen az alap logika ugyanaz. Csak egyet ne feledj: Stringek eset\u00e9n == helyett equals()!<\/p>\n
<\/a>Melyik \u00e9rt\u00e9kb\u0151l van a legt\u00f6bb?<\/h3>\nA nagy k\u00e9rd\u00e9s az, hogy melyik sz\u00e1m fordul el\u0151 legt\u00f6bbsz\u00f6r a t\u00f6mbben?<\/p>\n
\r\nint[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9};\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint db = 1;\r\nint maxDb = 1;\r\nint mibol = tomb[0];\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i] == tomb[i + 1] )\r\n {\r\n db++;\r\n if( db > maxDb )\r\n {\r\n maxDb = db;\r\n mibol = tomb[i];\r\n }\r\n }\r\n else\r\n {\r\n db = 1;\r\n }\r\n}\r\nSystem.out.println("A tombben a legtobb a " + mibol \r\n + " szambol van: " + maxDb + " db.");\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
Az el\u0151z\u0151h\u00f6z kism\u00e9rt\u00e9kben hasonl\u00edt. Ez egyfajta maximumkeres\u00e9s, de nem egy konkr\u00e9t maxim\u00e1lis \u00e9rt\u00e9ket keresek, hanem a t\u00f6mbben l\u00e9v\u0151 sz\u00e1mok darabsz\u00e1m\u00e1nak maximum\u00e1t. A v\u00e1lasz r\u00e1ad\u00e1sul nem a darabsz\u00e1m, hanem az, hogy ez melyik sz\u00e1mhoz tartozik. Ok\u00e9, erre is haszn\u00e1lhat\u00f3 lenne k\u00f6nny\u00edt\u00e9sk\u00e9nt a t\u00f6bbsz\u00f6r\u00f6s megsz\u00e1ml\u00e1l\u00e1s<\/a>, de most az\u00e9rt sem haszn\u00e1lom \ud83d\ude1b Nemsok\u00e1ra megmondom, mi\u00e9rt.<\/p>\nAz egyszer\u0171 megsz\u00e1ml\u00e1l\u00e1st\u00f3l ez annyiban bonyolultabb, hogy itt minden \u00e9rt\u00e9k eset\u00e9n meg kell sz\u00e1molni azok darabsz\u00e1m\u00e1t, de mindig csak az \u00e9rdekel, amelyikb\u0151l eddig a legt\u00f6bb volt. Abb\u00f3l indulok ki, hogy rendezett t\u00f6mb eset\u00e9n az egyforma sz\u00e1mok egym\u00e1s mellett vannak, a rendez\u00e9s ir\u00e1nya l\u00e9nyegtelen. L\u00e1ssuk mire van sz\u00fcks\u00e9gem m\u00e1r r\u00f6gt\u00f6n az elej\u00e9n.<\/p>\n
\n- Arra vagyok k\u00edv\u00e1ncsi, hogy az egym\u00e1s melletti egyforma \u00e9rt\u00e9kekb\u0151l h\u00e1ny darab van. Emiatt sz\u00fcks\u00e9gem van egy sz\u00e1ml\u00e1l\u00f3ra, amit 1-r\u0151l ind\u00edtok, mert az els\u0151 sz\u00e1mb\u00f3l biztosan van legal\u00e1bb egy a t\u00f6mbben.<\/li>\n
- Nyilv\u00e1n kell tartanom, hogy eddig mennyi volt a legnagyobb darabsz\u00e1m az egym\u00e1s melletti egyforma sz\u00e1mokb\u00f3l, ami logikusan szint\u00e9n 1-r\u0151l indul.<\/li>\n
- Tudnom kell, hogy eddig melyik sz\u00e1mb\u00f3l volt a legt\u00f6bb, ami indul\u00e1skor nyilv\u00e1n a t\u00f6mb els\u0151 eleme lesz.<\/li>\n<\/ol>\n
A megold\u00e1s sor\u00e1n azt vizsg\u00e1lom, hogy egym\u00e1s mellett egyforma sz\u00e1mok vannak-e. Amennyiben igen, n\u00f6velem a megfelel\u0151 sz\u00e1ml\u00e1l\u00f3t. K\u00f6zvetlen\u00fcl ezut\u00e1n azt is meg kell vizsg\u00e1lni, hogy az aktu\u00e1lisan vizsg\u00e1lt sz\u00e1mokb\u00f3l a n\u00f6vel\u00e9s ut\u00e1n t\u00f6bb lett-e, mint az eddigi maximum. Amennyiben igen, megjegyzem az \u00faj maximumot, \u00e9s a hozz\u00e1 tartoz\u00f3 \u00e9rt\u00e9ket. Ha a k\u00f6vetkez\u0151 sz\u00e1m nem ugyanaz, mint az el\u0151z\u0151, akkor az aktu\u00e1lis sz\u00e1mok darabsz\u00e1m\u00e1t ism\u00e9t 1-re \u00e1ll\u00edtom, hiszen \u00faj sz\u00e1m k\u00f6vetkezik, azokat \u00fajra meg kell sz\u00e1molnom.<\/p>\n
Ok\u00e9-ok\u00e9, de mi\u00e9rt kellett ennyire megbonyol\u00edtani ennek a feladatnak a megold\u00e1s\u00e1t az el\u0151z\u0151leg emlegetett t\u00f6bbsz\u00f6r\u00f6s megsz\u00e1ml\u00e1l\u00e1shoz k\u00e9pest?<\/p>\n
Pr\u00f3b\u00e1ld csak meg val\u00f3s sz\u00e1mokra alkalmazni! Sok sikert \ud83d\ude42 Hogy a String-eket m\u00e1r ne is emlegessem… Az egyetlen fontos kit\u00e9tele az el\u0151z\u0151leg ismertetett megold\u00e1snak, hogy az elemek k\u00f6zvetlen\u00fcl \u00f6sszehasonl\u00edthat\u00f3ak legyenek, hogy ugyanazok-e vagy sem. Ak\u00e1r objektumok is, megfelel\u0151 equals() met\u00f3dussal felv\u00e9rtezve.<\/p>\n
<\/a>Melyik \u00e9rt\u00e9kb\u0151l van a legkevesebb?<\/h3>\nAz el\u0151z\u0151 feladathoz nagyon hasonl\u00f3, a k\u00e9rd\u00e9s ez\u00fattal az, hogy melyik \u00e9rt\u00e9kb\u0151l van a legkevesebb. M\u00e1r tiszt\u00e1ztuk, hogy ennek a megold\u00e1snak az er\u0151ss\u00e9ge, hogy gyakorlatilag b\u00e1rmilyen \u00f6sszehasonl\u00edthat\u00f3 adatt\u00edpusra m\u0171k\u00f6dik, nem csak eg\u00e9sz sz\u00e1mokra. A megold\u00e1st tov\u00e1bbra is sz\u00e1mokra adom meg, de megfelel\u0151 \u00f6sszehasonl\u00edt\u00e1s ut\u00e1n b\u00e1rmilyen adatt\u00edpusra haszn\u00e1lhat\u00f3.<\/p>\n
\r\nint[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9};\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint db = 1;\r\nint minDb = tomb.length;\r\nint mibol = tomb[0];\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i] == tomb[i + 1] )\r\n {\r\n db++;\r\n }\r\n else\r\n {\r\n if( db < minDb )\r\n {\r\n minDb = db;\r\n mibol = tomb[i];\r\n }\r\n db = 1;\r\n }\r\n}\r\n\r\nif( db < minDb )\r\n{\r\n minDb = db;\r\n mibol = tomb[tomb.length - 1];\r\n}\r\n\r\nSystem.out.println("A tombben a legkevesebb a " + mibol \r\n + " szambol van: " + minDb + " db.");\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
M\u00edg a minimum \u00e9s maximumkeres\u00e9s eset\u00e9n a k\u00e9t megold\u00e1s k\u00f6z\u00f6tt egyetlen rel\u00e1ci\u00f3s jel a k\u00fcl\u00f6nbs\u00e9g, itt azt l\u00e1thatjuk, hogy szerkezetileg el\u00e9gg\u00e9 elt\u00e9r\u0151 a k\u00e9t megold\u00e1s. N\u00e9zz\u00fck mire van sz\u00fcks\u00e9gem az elej\u00e9n:<\/p>\n
\n- Itt is kell egy sz\u00e1ml\u00e1l\u00f3, melyben nyilv\u00e1ntartom, hogy az aktu\u00e1lis sz\u00e1mb\u00f3l h\u00e1ny darabot tal\u00e1ltam eddig, a kezd\u0151\u00e9rt\u00e9k itt is 1.<\/li>\n
- Nyilv\u00e1n kell tartanom, hogy eddig mennyi volt a minim\u00e1lis darabsz\u00e1m az egyforma sz\u00e1mokb\u00f3l, ami viszont m\u00e1r teljesen m\u00e1s kezd\u0151\u00e9rt\u00e9ket kap. Itt nem tekinthetem 1-nek az elej\u00e9n, mert lehet, hogy nincs is olyan sz\u00e1m, amib\u0151l csak egy van. Akkor mit felt\u00e9telezhetek? Azt, hogy minden sz\u00e1m ugyanaz. Ha majd tal\u00e1lok k\u00fcl\u00f6nb\u00f6z\u0151ket, akkor m\u00f3dos\u00edtom ezt a darabsz\u00e1mot.<\/li>\n
- Tudnom kell, hogy eddig melyik sz\u00e1mb\u00f3l volt a legkevesebb, teh\u00e1t az \u00e9rt\u00e9ket is t\u00e1rolnom kell. Ennek kezd\u0151\u00e9rt\u00e9ke ism\u00e9t a t\u00f6mb els\u0151 eleme.<\/li>\n<\/ol>\n
A megold\u00e1s sor\u00e1n azt vizsg\u00e1lom, hogy egym\u00e1s mellett egyforma sz\u00e1mok vannak-e. Amennyiben igen, n\u00f6velem a megfelel\u0151 sz\u00e1ml\u00e1l\u00f3t. Itt nincs is m\u00e1s teend\u0151m. Azt, hogy az \u00e9ppen sz\u00e1molt sz\u00e1mok darabsz\u00e1ma kevesebb-e, mint az eddigi legkevesebb, akkor d\u00f6nthetem el, ha az egyform\u00e1kb\u00f3l mindet megsz\u00e1moltam, vagyis amikor \u00faj sz\u00e1m k\u00f6vetkezik. Ha teh\u00e1t a k\u00f6vetkez\u0151 sz\u00e1m m\u00e1r nem ugyanaz, akkor megn\u00e9zem, hogy az el\u0151z\u0151leg megsz\u00e1molt sz\u00e1mok darabsz\u00e1ma kisebb-e, mint az eddigi minimum. Ha igen, megjegyzem a t\u00f6mb aktu\u00e1lis \u00e9rt\u00e9k\u00e9t (tomb[i]), ami az egym\u00e1s melletti egyforma sz\u00e1mok k\u00f6z\u00fcl a utols\u00f3 lesz. Ez az “egyform\u00e1k k\u00f6z\u00fcl az utols\u00f3” m\u00e9g hamarosan visszak\u00f6sz\u00f6n.<\/p>\n
\u00c9rdekes a db v\u00e1ltoz\u00f3 1-re \u00e1ll\u00edt\u00e1sa. Ezt akkor tehetem meg, amikor \u00faj sz\u00e1m k\u00f6vetkezik, vagyis a k\u00f6vetkez\u0151 \u00e9rt\u00e9k nem egyezik az aktu\u00e1lissal (else \u00e1g). Ezt mindenk\u00e9ppen az else-en bel\u00fcli minimum vizsg\u00e1lat (if) ut\u00e1n lehet megtenni, hiszen a minimum vizsg\u00e1lathoz m\u00e9g sz\u00fcks\u00e9g van az el\u0151z\u0151leg megsz\u00e1molt egyforma sz\u00e1mok darabsz\u00e1m\u00e1ra.<\/p>\n
De itt m\u00e9g nem v\u00e9gezt\u00fcnk!<\/strong><\/p>\nGondolj bele, mi van akkor, ha a t\u00f6mb k\u00e9t vagy t\u00f6bb utols\u00f3 sz\u00e1ma megegyezik? Ilyenkor gond van, mert ugyan befejezz\u00fck a sz\u00e1mok megsz\u00e1ml\u00e1l\u00e1s\u00e1t, de az utols\u00f3 ciklusban kimarad az else \u00e1g. Ezzel kimarad a minimum vizsg\u00e1lat, hogy az utolj\u00e1ra gy\u0171jt\u00f6tt darabsz\u00e1m kisebb-e, mint az eddigi legkisebb. Vizsg\u00e1lni musz\u00e1j, mert lehet, hogy pont ezek azok az egyforma sz\u00e1mok, amelyekb\u0151l a legkevesebb van, mert el\u0151tte mindegyikb\u0151l ezekn\u00e9l t\u00f6bb volt! Ezt a ciklus befejez\u00e9se ut\u00e1n mindenk\u00e9ppen meg kell vizsg\u00e1lni! Ha val\u00f3ban ezekb\u0151l a sz\u00e1mokb\u00f3l van a legkevesebb, akkor itt a t\u00f6mb utols\u00f3 elem\u00e9t \u00edrjuk ki, ami ugye megint az utols\u00f3 az egyforma \u00e9rt\u00e9kek k\u00f6z\u00fcl. “Egyform\u00e1k k\u00f6z\u00fcl az utols\u00f3.”<\/p>\n
Ha jobban belegondolsz, egy probl\u00e9ma m\u00e9g mindig lehet…<\/strong><\/p>\n\u00c9s ha csak az utols\u00f3 sz\u00e1m k\u00fcl\u00f6nb\u00f6zik az el\u0151z\u0151t\u0151l, vagyis egyedi \u00e9rt\u00e9k? Mi van, ha el\u0151tte m\u00e9g egyik sz\u00e1mb\u00f3l sem volt egyetlen darab? Akkor is helyesen m\u0171k\u00f6dik az algoritmus. Ha az utols\u00f3 \u00e9rt\u00e9k egy \u00faj sz\u00e1m, akkor az utols\u00f3 ciklusban az else \u00e1g futott le. Megn\u00e9zte, hogy az utols\u00f3 el\u0151tti sz\u00e1mb\u00f3l kevesebb volt-e, mint eddig, majd a db v\u00e1ltoz\u00f3t 1-re \u00e1ll\u00edtotta. A ciklus meg\u00e1ll\u00e1sa ut\u00e1n a db pontosan az utols\u00f3 sz\u00e1m darabsz\u00e1m\u00e1t adja meg. Ilyenkor is helyesen m\u0171k\u00f6dik az el\u0151z\u0151 esetben eml\u00edtett cikluson k\u00edv\u00fcli vizsg\u00e1lat, mert pont a t\u00f6mb utols\u00f3 eleme az, amib\u0151l a legkevesebb volt. “Egyform\u00e1k k\u00f6z\u00fcl az utols\u00f3.” (ok\u00e9, befejeztem)<\/p>\n
Sok feladatra igaz az, hogy a t\u00f6mb\u00f6kre megadott megold\u00e1sok a t\u00f6mb v\u00e9g\u00e9n, esetleg elej\u00e9n l\u00e9v\u0151 elemre vagy elemekre nem m\u0171k\u00f6dnek, ez\u00e9rt mindig gondold \u00e1t, hogy ezeken a pontokon is helyes-e az algoritmus, vagy ezeket valamif\u00e9le kiv\u00e9telk\u00e9nt k\u00fcl\u00f6n kezelned kell. Amit ak\u00e1r az \u00e1ltal\u00e1nos megold\u00e1st ad\u00f3 ciklus el\u0151tt kell megoldanod!<\/p>\n
<\/a>Van-e hi\u00e1nyz\u00f3 \u00e9rt\u00e9k?<\/h3>\nEz a r\u00e9sz megint nem lesz olyan egyszer\u0171. Hi\u00e1nyz\u00f3 \u00e9rt\u00e9kekr\u0151l egy rendezett t\u00f6mb eset\u00e9ben akkor besz\u00e9lhet\u00fcnk, ha k\u00e9t \u00e9rt\u00e9k k\u00f6z\u00f6tt egy\u00e9rtelm\u0171en meghat\u00e1rozhat\u00f3ak a k\u00f6ztes \u00e9rt\u00e9kek.<\/p>\n
\n- Eg\u00e9sz sz\u00e1mokra eset\u00e9ben ez igaz, hiszen egy\u00e9rtelm\u0171, hogy 22 \u00e9s 83 k\u00f6z\u00f6tt milyen sz\u00e1mok tal\u00e1lhat\u00f3k, de val\u00f3s sz\u00e1mok eset\u00e9n ez m\u00e1r nem oldhat\u00f3 meg.<\/li>\n
- Karakterekn\u00e9l (konkr\u00e9tabban bet\u0171k) szint\u00e9n lehet m\u0171k\u00f6d\u0151 megold\u00e1sokat k\u00e9sz\u00edteni, hiszen ott is meg tudjuk mondani, milyen karakterek hi\u00e1nyoznak mondjuk a c \u00e9s h bet\u0171k k\u00f6z\u00f6tt. Az\u00e9rt oldhat\u00f3 meg, mert a karakterek val\u00f3j\u00e1ban eg\u00e9sz sz\u00e1mok.<\/li>\n
- Stringek eset\u00e9ben speci\u00e1lisan gener\u00e1lhat\u00f3ak k\u00f6ztes \u00e9rt\u00e9kek, amennyiben r\u00f6gz\u00edtett a String hossza \u00e9s szerkezete. Gondolj mondjuk olyan rendsz\u00e1mokra, amelyekn\u00e9l az elej\u00e9n kik\u00f6tj\u00fck, hogy mindig 3 bet\u0171b\u0151l, \u00e9s ut\u00e1na 3 sz\u00e1mb\u00f3l \u00e1llnak. Itt, m\u00e9g ha nem is egyszer\u0171en, de legener\u00e1lhat\u00f3ak k\u00e9t rendsz\u00e1m k\u00f6z\u00f6tt a t\u00f6bbiek, csak itt kicsit keverni kell a karakterek \u00e9s sz\u00e1mok kezel\u00e9s\u00e9t. Nem mondom, hogy egyszer\u0171, de j\u00f3 kis agytorna ezt elk\u00e9sz\u00edteni. Erre hamarosan k\u00e9sz\u00edtek egy feladatot is.<\/li>\n<\/ul>\n
A k\u00f6vetkez\u0151 k\u00e9t megold\u00e1s eg\u00e9sz sz\u00e1mokra m\u0171k\u00f6dik, aminek megold\u00e1sa k\u00e9t k\u00e9rd\u00e9s alapj\u00e1n k\u00e9t r\u00e9szre bonthat\u00f3:<\/p>\n
\n- Csak a t\u00f6mb bels\u0151 hi\u00e1nyz\u00f3 elemeire vagyok k\u00edv\u00e1ncsi. (Ez az egyszer\u0171bb)<\/li>\n
- Tudom, hogy milyen \u00e9rt\u00e9kk\u00e9szletb\u0151l kellett felt\u00f6lteni a t\u00f6mb\u00f6t, \u00e9s minden hi\u00e1nyz\u00f3 sz\u00e1m \u00e9rdekel.<\/li>\n<\/ol>\n
Bels\u0151 hi\u00e1nyz\u00f3 \u00e9rt\u00e9kek meghat\u00e1roz\u00e1sa:<\/strong><\/p>\nEz a megold\u00e1s csak a t\u00f6mb bels\u0151 hi\u00e1nyz\u00f3 elemeit adja meg. A k\u00e9rd\u00e9s: Milyen sz\u00e1mok hi\u00e1nyoznak a t\u00f6mb elemei k\u00f6z\u00f6tt? A megold\u00e1sn\u00e1l nem tudjuk, vagy nem fontos, hogy 8 \u00e9s 9 is lehetett volna a t\u00f6mbben, csak a k\u00e9t sz\u00e9ls\u0151 elemet tekintj\u00fck a hat\u00e1roknak, \u00e9s a k\u00f6z\u00f6tt\u00fck l\u00e9v\u0151 hi\u00e1nyz\u00f3 \u00e9rt\u00e9keket keress\u00fck.<\/p>\n
\r\nint[] tomb = new int[] { 1,1,1,3,3,3,7,7,7 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution” rel=”missing-values-highlander”]<\/p>\n
\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] > 1 )\r\n {\r\n for( int j = tomb[i] + 1; j < tomb[i + 1]; j++ )\r\n {\r\n System.out.print(j + " ");\r\n }\r\n }\r\n}\r\nSystem.out.println();\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
Azt vizsg\u00e1lom, hogy a szomsz\u00e9dos elemek k\u00f6z\u00f6tt hi\u00e1nyzik-e valami. Ha k\u00e9t szomsz\u00e9dos elem k\u00fcl\u00f6nbs\u00e9ge 1-n\u00e9l nagyobb, akkor egy bels\u0151 ciklussal ki\u00edrom a k\u00e9t szomsz\u00e9dos elem k\u00f6z\u00f6tti sz\u00e1mokat. A bels\u0151 ciklusn\u00e1l az\u00e9rt nagyon figyelj, hogy mit jelent az i, \u00e9s mit jelent a j. Az i az eredeti t\u00f6mb elemeinek helye, a j pedig a k\u00e9t elem k\u00f6z\u00f6tti hi\u00e1nyz\u00f3 sz\u00e1mokat jelenti.<\/p>\n
\u00d6sszes hi\u00e1nyz\u00f3 \u00e9rt\u00e9k meghat\u00e1roz\u00e1sa:<\/strong><\/p>\nEz a megold\u00e1s abb\u00f3l indul ki, hogy tudjuk, milyen sz\u00e1mok lehetn\u00e9nek a t\u00f6mbben, mondjuk az [1;9] intervallumb\u00f3l b\u00e1rmi. A k\u00e9rd\u00e9s az, hogy ezek k\u00f6z\u00fcl melyik maradt ki?<\/p>\n
\r\nint[] tomb = new int[] { 3,3,3,6,7,7,7 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution” rel=”missing-values-highlander”]<\/p>\n
\r\nint also = 1;\r\nint felso = 9;\r\n\r\nif( tomb[0] > also )\r\n{\r\n for( int i = also; i < tomb[0]; i++ )\r\n {\r\n System.out.print(i + " ");\r\n }\r\n}\r\n\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] > 1 )\r\n {\r\n for( int j = tomb[i] + 1; j < tomb[i + 1]; j++ )\r\n {\r\n System.out.print(j + " ");\r\n }\r\n }\r\n}\r\n\r\nif( tomb[tomb.length - 1] < felso )\r\n{\r\n for( int i = tomb[tomb.length - 1] + 1; i <= felso; i++ )\r\n {\r\n System.out.print(i + " ");\r\n }\r\n}\r\nSystem.out.println();\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
Itt gyakorlatilag az el\u0151z\u0151 megold\u00e1st kell kieg\u00e9sz\u00edteni az alulr\u00f3l \u00e9s fel\u00fclr\u0151l hi\u00e1nyz\u00f3 elemek meghat\u00e1roz\u00e1s\u00e1val.<\/p>\n
\n- 4-10 – Ha a t\u00f6mb els\u0151 eleme nagyobb az als\u00f3 hat\u00e1rn\u00e1l, ind\u00edtok egy ciklust az alulr\u00f3l hi\u00e1nyz\u00f3 elemek meghat\u00e1roz\u00e1s\u00e1ra.<\/li>\n
- 12-20 – A bels\u0151 hi\u00e1nyz\u00f3 elemek meghat\u00e1roz\u00e1sa ugyanaz, mint az el\u0151z\u0151 k\u00e9rd\u00e9s megold\u00e1sa.<\/li>\n
- 22-28 – Ha a t\u00f6mb utols\u00f3 eleme kisebb a fels\u0151 hat\u00e1rn\u00e1l, ind\u00edtok egy ciklust az fel\u00fclr\u0151l hi\u00e1nyz\u00f3 elemek meghat\u00e1roz\u00e1s\u00e1ra.<\/li>\n<\/ul>\n
<\/a>Mennyi a legnagyobb k\u00fcl\u00f6nbs\u00e9g?<\/h3>\nEnn\u00e9l a feladatn\u00e1l arra vagyunk k\u00edv\u00e1ncsiak, hogy a szomsz\u00e9dos eleme k\u00f6z\u00f6tt mekkora a legnagyobb k\u00fcl\u00f6nbs\u00e9g. Ennek nyilv\u00e1n sz\u00e1mok eset\u00e9n van \u00e9rtelme, amik lehetnek ak\u00e1r val\u00f3s sz\u00e1mok is. Ez eddig rendben is van, de az eg\u00e9sz feladat nem rendezett t\u00f6mbn\u00e9l is megoldhat\u00f3, ugyan\u00fagy \u00e9rtelmezhet\u0151 a szomsz\u00e9dos elemek k\u00fcl\u00f6nbs\u00e9ge. Mikor \u00e9rtelme van akkor a rendez\u00e9snek?<\/p>\n
Tegy\u00fck fel, hogy adott egy kevert t\u00f6mb egy h\u00f3nap napjait tartalmazza, amiket valami okb\u00f3l r\u00f6gz\u00edtett\u00fcnk, \u00e9s az a k\u00e9rd\u00e9s, hogy mekkora volt a legnagyobb sz\u00fcnet k\u00e9t nap k\u00f6z\u00f6tt. Ezt m\u00e1r csak rendezett t\u00f6mbk\u00e9nt lehet megoldani, mert \u00edgy tudom meghat\u00e1rozni az egym\u00e1s ut\u00e1n k\u00f6vetkez\u0151 napok k\u00fcl\u00f6nbs\u00e9g\u00e9t. A rendez\u00e9s ir\u00e1nya gyakorlatilag mindegy, csak a k\u00fcl\u00f6nbs\u00e9g k\u00e9pz\u00e9sn\u00e9l kell odafigyelni, hogy melyikb\u0151l melyiket vonjuk ki.<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint maxKulonbseg = tomb[1] - tomb[0];\r\nfor( int i = 1; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] > maxKulonbseg )\r\n {\r\n maxKulonbseg = tomb[i + 1] - tomb[i];\r\n }\r\n}\r\nSystem.out.println(maxKulonbseg);\r\n<\/pre>\n[\/expand]<\/p>\n
Magyar\u00e1zat:<\/h4>\n
Ebben igaz\u00e1b\u00f3l semmi rendk\u00edv\u00fcli dolog nincs. A legnagyobb k\u00fcl\u00f6nbs\u00e9g kezd\u0151\u00e9rt\u00e9k\u00e9nek nyugodtan be\u00e1ll\u00edthatom az els\u0151 k\u00e9t elem k\u00fcl\u00f6nbs\u00e9g\u00e9t. Ut\u00e1na viszont c\u00e9lszer\u0171 (b\u00e1r nem k\u00f6telez\u0151) 1-t\u0151l ind\u00edtani a ciklust, hogy ugyanannak a k\u00e9t sz\u00e1mnak a k\u00fcl\u00f6nbs\u00e9g\u00e9t ne vizsg\u00e1ljam meg \u00fajra.<\/p>\n
Mi van, ha az is a k\u00e9rd\u00e9s r\u00e9sze, hogy melyik k\u00e9t nap k\u00f6z\u00f6tt volt a legnagyobb k\u00fcl\u00f6nbs\u00e9g? Csak ki kell eg\u00e9sz\u00edteni azzal, hogy meg kell jegyezni a k\u00fcl\u00f6nbs\u00e9g els\u0151 napj\u00e1nak az index\u00e9t. L\u00e1ssuk ezzel kieg\u00e9sz\u00edtve:<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint maxKulonbseg = tomb[1] - tomb[0];\r\nint maxIdx = 0;\r\nfor( int i = 0; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] > maxKulonbseg )\r\n {\r\n maxKulonbseg = tomb[i + 1] - tomb[i];\r\n maxIdx = i;\r\n }\r\n}\r\nSystem.out.println(maxKulonbseg);\r\nSystem.out.println(tomb[maxIdx] + " - " + tomb[maxIdx + 1]);\r\n<\/pre>\n[\/expand]<\/p>\n
A k\u00e9t kiemelt sorban l\u00e1that\u00f3 a kieg\u00e9sz\u00edt\u00e9s, a legnagyobb k\u00fcl\u00f6nbs\u00e9g\u0171 tagok k\u00f6z\u00fcl az els\u0151 index\u00e9t jegyzem meg, abb\u00f3l m\u00e1r megvan a m\u00e1sik is.<\/p>\n
<\/a>Mennyi a legkisebb k\u00fcl\u00f6nbs\u00e9g?<\/h3>\nEnn\u00e9l a feladatn\u00e1l arra vagyunk k\u00edv\u00e1ncsiak, hogy a rendezett t\u00f6mb szomsz\u00e9dos elemei k\u00f6z\u00f6tt mekkora a legkisebb k\u00fcl\u00f6nbs\u00e9g. Az el\u0151z\u0151h\u00f6z hasonl\u00f3an szint\u00e9n csak sz\u00e1mok eset\u00e9n van \u00e9rtelme, amik lehetnek ak\u00e1r val\u00f3s sz\u00e1mok is. A rendez\u00e9s ir\u00e1nya mindegy, csak itt is figyelni kell arra, hogy melyikb\u0151l melyiket vonjuk ki. Eml\u00e9kszel, hogy a legt\u00f6bb-legkevesebb probl\u00e9m\u00e1n\u00e1l is a legkevesebb megold\u00e1sa j\u00f3val bonyolultabb volt a m\u00e1sikn\u00e1l? Lehet m\u00e1r ott motoszk\u00e1l benned, hogy itt sem \u00faszod meg k\u00f6nnyen a dolgot. A helyzet az, hogy igaz\u00e1b\u00f3l a k\u00e9t megold\u00e1s k\u00fcl\u00f6nbs\u00e9ge ugyanaz, mint az alap minimum \u00e9s maximumkeres\u00e9s eset\u00e9n, egyetlen rel\u00e1ci\u00f3s jel. De l\u00e1ssuk akkor ennek a megold\u00e1s\u00e1t.<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint minKulonbseg = tomb[1] - tomb[0];\r\nfor( int i = 1; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] < minKulonbseg )\r\n {\r\n minKulonbseg = tomb[i + 1] - tomb[i];\r\n }\r\n}\r\nSystem.out.println(minKulonbseg);\r\n<\/pre>\n[\/expand]<\/p>\n
Az egyetlen k\u00fcl\u00f6nbs\u00e9g a 4-es sorban tal\u00e1lhat\u00f3 rel\u00e1ci\u00f3s jel (a v\u00e1ltoz\u00f3k nevein k\u00edv\u00fcl).<\/p>\n
\u00c9s ha a k\u00e9t napra is sz\u00fcks\u00e9g van, melyek k\u00fcl\u00f6nbs\u00e9ge a legkisebb?<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\n<\/pre>\n[expand title=”Megold\u00e1s” swaptitle=”Bez\u00e1r” trigclass=”show_program_solution”]<\/p>\n
\r\nint minKulonbseg = tomb[1] - tomb[0];\r\nint minIdx = 0;\r\nfor( int i = 1; i < tomb.length - 1; i++ )\r\n{\r\n if( tomb[i + 1] - tomb[i] < minKulonbseg )\r\n {\r\n minKulonbseg = tomb[i + 1] - tomb[i];\r\n minIdx = i;\r\n }\r\n}\r\nSystem.out.println(minKulonbseg);\r\nSystem.out.println(tomb[minIdx] + " - " + tomb[minIdx + 1] );\r\n<\/pre>\n[\/expand]<\/p>\n
Ugyan\u00fagy megjegyezz\u00fck a megfelel\u0151 indexet, abb\u00f3l m\u00e1r megvan a k\u00e9t elem is.<\/p>\n
<\/a>Melyik a legnagyobb? Melyik a legkisebb?<\/h3>\nNem v\u00e9letlen\u00fcl t\u00e1rgyalom a k\u00e9t k\u00e9rd\u00e9st egyetlen pontban. Ezt a feladatot megold\u00e1sra sem m\u00e9ltatom \ud83d\ude42 Az al\u00e1bbi felsorol\u00e1s alapj\u00e1n \u00fagyis egy\u00e9rtelm\u0171 lesz (rem\u00e9lhet\u0151leg). P\u00e1r dolgot az\u00e9rt megjegyezn\u00e9k ezzel kapcsolatban:<\/p>\n
\n- Ha eredetileg rendezett t\u00f6mb\u00fcnk van, akkor a rendez\u00e9s ir\u00e1ny\u00e1t\u00f3l f\u00fcgg\u0151en a legkisebb elem mindig a t\u00f6mb megfelel\u0151 v\u00e9g\u00e9n van.\n
\n- N\u00f6vekv\u0151 rendez\u00e9s eset\u00e9n a legnagyobb mindig az utols\u00f3 elem, a legkisebb pedig az els\u0151.<\/li>\n
- Cs\u00f6kken\u0151 rendez\u00e9s eset\u00e9n a legnagyobb mindig az els\u0151 elem, a legkisebb pedig az utols\u00f3.<\/li>\n<\/ul>\n<\/li>\n
- Ha eredetileg NEM rendezett t\u00f6mb\u00fcnk van, a rendez\u00e9s ut\u00e1n valamelyik v\u00e9g\u00e9n tal\u00e1ljuk meg a legnagyobb vagy legkisebb elemet, de ezzel elvesz\u00edtj\u00fck azt az inform\u00e1ci\u00f3t, hogy eredetileg ez pontosan melyik helyen volt eredetileg.<\/li>\n
- Ha a k\u00e9rd\u00e9st kombin\u00e1ljuk egyfajta rangsorral is, akkor a rendezett t\u00f6mbben k\u00f6nnyel v\u00e1laszt kaphatunk a hasonl\u00f3 k\u00e9rd\u00e9sekre:\n
\n- Melyik a t\u00f6mb m\u00e1sodik legnagyobb eleme?<\/li>\n
- Melyik a t\u00f6mb harmadik legkisebb eleme?<\/li>\n
- Stb.<\/li>\n<\/ul>\n<\/li>\n
- Ha az el\u0151z\u0151 k\u00e9rd\u00e9sek eset\u00e9n az eredeti t\u00f6mb nem rendezett, akkor a rendez\u00e9s ut\u00e1n term\u00e9szetesen ism\u00e9t elvesz\u00edtj\u00fck a megtal\u00e1lt 2. legnagyobb, 3. legkisebb, stb elemek eredeti hely\u00e9t.<\/li>\n<\/ul>\n
Ezekn\u00e9l a k\u00e9rd\u00e9sekn\u00e9l mindig m\u00e9rlegelni kell, hogy felt\u00e9tlen\u00fcl kell-e rendezni a t\u00f6mb\u00f6t a k\u00e9rd\u00e9s megold\u00e1s\u00e1hoz, hiszen a maximum \u00e9s minimumkeres\u00e9st az alap algoritmusok<\/a> leck\u00e9b\u0151l megtanulhattad. A m\u00e1sodik legkisebb, \u00e9s hasonl\u00f3 k\u00e9rd\u00e9sekn\u00e9l pedig azt kell m\u00e9rlegelned, hogy el\u00e9g-e csak a konkr\u00e9t \u00e9rt\u00e9ket meghat\u00e1roznod, vagy az adott \u00e9rt\u00e9k pontos helye is fontos.<\/p>\nTerm\u00e9szetesen megteheted azt, hogy a t\u00f6mbr\u0151l egy m\u00e1solatot k\u00e9sz\u00edtesz, \u00e9s azzal m\u00e1r azt csin\u00e1lsz, amit akarsz, az eredetit nem rontod el, de ez alapvet\u0151en csak a primit\u00edv \u00e9rt\u00e9kekn\u00e9l oldhat\u00f3 meg:<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\nint[] masolat = tomb.clone();\r\n<\/pre>\nItt a m\u00e1sodik t\u00f6mb az els\u0151nek egy pontos, \u00e9rt\u00e9k szerinti m\u00e1solata lesz. \u00cdgy b\u00e1rmilyen m\u0171veletet v\u00e9gzel az egyikkel, az a m\u00e1sikra nincs hat\u00e1ssal.<\/p>\n
Ha azonban az al\u00e1bbi m\u00f3don oldan\u00e1d meg a m\u00e1solat elk\u00e9sz\u00edt\u00e9s\u00e9t, azzal a k\u00e9t t\u00f6mb\u00f6t gyakorlatilag \u00f6sszek\u00f6t\u00f6d referencia (mem\u00f3riabeli hivatkoz\u00e1s) szerint, \u00e9s b\u00e1rmelyiket v\u00e1ltoztatod, az mindkett\u0151re hat\u00e1ssal van, mert mindk\u00e9t v\u00e1ltoz\u00f3 ugyanarra a t\u00f6mbre mutat. Pr\u00f3b\u00e1ld csak ki:<\/p>\n
\r\nint[] tomb = new int[] { 3,8,11,12,15,22,25,31 };\r\nint[] masolat = tomb;\r\n\r\ntomb[0] = -100;\r\n\r\nfor( int i = 0; i < masolat.length; i++ )\r\n{\r\n System.out.print(masolat[i] + " ");\r\n}\r\nSystem.out.println();\r\n<\/pre>\n<\/a>Mekkora az intervallum?<\/h3>\nHa adott egy t\u00f6mb, amiben valamilyen sz\u00e1mok vannak, akkor k\u00f6nnyen megadhatjuk, hogy val\u00f3j\u00e1ban milyen intervallumbeli elemek vannak a t\u00f6mbben. Amire sz\u00fcks\u00e9g\u00fcnk van, az a t\u00f6mb legkisebb \u00e9s legnagyobb eleme, teh\u00e1t mindkett\u0151re sz\u00fcks\u00e9g\u00fcnk van. Itt is csak megeml\u00edten\u00e9k p\u00e1r gondolatot felsorol\u00e1sszer\u0171en.<\/p>\n
\n- Ha a t\u00f6mb eredetileg rendezett, akkor a legkisebb \u00e9s legnagyobb elemek a t\u00f6mb megfelel\u0151 sz\u00e9lein tal\u00e1lhat\u00f3ak. Nyilv\u00e1n itt is figyelembe kell venni a rendez\u00e9s ir\u00e1ny\u00e1t.<\/li>\n
- Ha a t\u00f6mb nem rendezett, akkor rendez\u00e9s ut\u00e1n a sz\u00e9leken ott lesz az eredm\u00e9ny a rendez\u00e9s ir\u00e1ny\u00e1nak megfelel\u0151en. Fontos azonban figyelembe venni, hogy sz\u00fcks\u00e9g van-e m\u00e9g az eredeti sorrendre, mert akkor nem \u00edgy kellene megoldani.<\/li>\n
- A legegyszer\u0171bb m\u00f3dszer term\u00e9szetesen a tanult minimum \u00e9s maximumkeres\u00e9s alkalmaz\u00e1sa, mert ez a t\u00f6mb szerkezet\u00e9t\u0151l \u00e9s t\u00edpus\u00e1t\u00f3l teljesen f\u00fcggetlen, \u00e9s semmit nem v\u00e1ltoztat rajta.<\/li>\n<\/ul>\n
Rendezz\u00fcnk, vagy nem?<\/h2>\n
Magad is l\u00e1thattad, hogy a rendezett t\u00f6mb\u00f6kb\u0151l sok plusz inform\u00e1ci\u00f3 kinyerhet\u0151. A gond az, hogy a t\u00f6mb alapesetben nem mindig rendezett. Lehetnek olyan feladatok, ahol nagyon j\u00f3l j\u00f6nne a rendez\u00e9s, de lehet, hogy k\u00e9s\u0151bbi feladatokn\u00e1l pont azzal vesz\u00edt\u00fcnk inform\u00e1ci\u00f3t, hogy az eredeti t\u00f6mb\u00f6t sorrendileg \u00e1talak\u00edtottuk.<\/p>\n
Bizonyos esetekben k\u00e9sz\u00edthet\u0151 a t\u00f6mbr\u0151l egy m\u00e1solat, de objektumok eset\u00e9n m\u00e1r nem ennyire trivi\u00e1lis a dolog. Ott azzal az eszk\u00f6zzel \u00e9lhet\u00fcnk, hogy minden objektumhoz hozz\u00e1adunk egy plusz tulajdons\u00e1got, gyakorlatilag egy indexet, ami az eredeti sorrendj\u00fcket tartalmazza. \u00cdgy b\u00e1rmikor b\u00e1rhogy rendezhetj\u00fck \u0151ket, hogy egy adott r\u00e9sz feladatra egyszer\u0171bben kapjunk v\u00e1laszt, az eredeti indexek alapj\u00e1n b\u00e1rmikor visszarendezhetj\u00fck \u0151ket. K\u00e9rd\u00e9s, hogy \u00e9rdemes-e mindig ennyit rendezgetni az elemeinket. Nem biztos. M\u00e9rlegelni kell.<\/p>\n
Ez a lecke nem azt sugallja – legal\u00e1bbis nem ez volt a sz\u00e1nd\u00e9kom – hogy a rendez\u00e9s mindig mindenre megold\u00e1s lesz, vagy nagyban megk\u00f6nny\u00edti a dolgunk. Bizonyos t\u00edpusfeladatokra ad megold\u00e1sokat, amelyek egy rendezett t\u00f6mb eset\u00e9n haszn\u00e1lhat\u00f3ak. Nem tilos egy t\u00f6mb\u00f6t rendezni, hogy bizonyos feladatokat k\u00f6nnyebben oldhassunk meg vele kapcsolatban, csak mindig figyelni kell arra, hogy k\u00e9s\u0151bb okoz-e az eredeti sorrend megv\u00e1ltoztat\u00e1sa valamilyen probl\u00e9m\u00e1t.<\/p>\n","protected":false},"excerpt":{"rendered":"
Rendezett adatok, avagy a rend \u00e1tl\u00e1that\u00f3bb Az egyes programoz\u00e1s feladatok forr\u00e1sai nagyban k\u00fcl\u00f6nb\u00f6znek egym\u00e1st\u00f3l. A forr\u00e1sok k\u00fcl\u00f6nb\u00f6z\u0151s\u00e9ge tekintet\u00e9ben nem akarok t\u00falzottan r\u00e9szletekbe bocs\u00e1tkozni, puszt\u00e1n egyetlen szempontot vizsg\u00e1ln\u00e9k, hogy az adatok rendezett vagy nem rendezett form\u00e1ban \u00e1llnak rendelkez\u00e9sre. Mi\u00e9rt j\u00f3, ha Tov\u00e1bb Java kieg\u00e9sz\u00edt\u0151 lecke – Rendezett t\u00f6mb\u00f6k<\/span>