L\u00e1thattad, hogy az alap algoritmusok nagyon sokf\u00e9le feladatra szinte k\u00e9sz megold\u00e1sokat adnak. A val\u00f3s\u00e1gban azonban sokszor nem ilyen tiszta form\u00e1ban fordulnak el\u0151, mivel a felt\u00e9telek lehetnek bonyolultabbak is. Nem ennyire egyszer\u0171 a dolog, ha p\u00e9ld\u00e1ul a k\u00e9rd\u00e9s nem puszt\u00e1n a legnagyobb vagy legkisebb elemre vonatkozik, hanem egy felt\u00e9telt is tartalmaz. N\u00e9zz\u00fcnk p\u00e1r p\u00e9ld\u00e1t:<\/p>\n
T\u00f6lts fel egy 10 elem\u0171 t\u00f6mb\u00f6t a [-10;50] intervallumb\u00f3l.<\/p>\n
Az els\u0151 k\u00e9t feladat val\u00f3j\u00e1ban annyira nem is v\u00e9szes, hiszen a legkisebb negat\u00edv sz\u00e1m az val\u00f3j\u00e1ban ugyanazt jelenti, mint a legkisebb sz\u00e1m, a legnagyobb pozit\u00edv pedig a legnagyobb sz\u00e1m. Innent\u0151l \u00fagy t\u0171nik, hogy csak egy egyszer\u0171 minimum \u00e9s maximumkeres\u00e9sr\u0151l van sz\u00f3. A helyzet azonban enn\u00e9l \u00e1rnyaltabb. L\u00e1ssunk egy teszt feladatot az els\u0151 feladatra:<\/p>\n
\r\nint[] tomb = {-1,3,7,6,-5,9,4,2,-7,-4};\r\n\r\n\/\/ minimumkeres\u00e9s, ahol be\u00e1ll\u00edtjuk az els\u0151 minimum hely\u00e9t\r\nint min = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] < tomb[min] ) min = i;\r\n}\r\nSystem.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);\r\n<\/pre>\nEz \u00edgy helyes is, hiszen az els\u0151 elem negat\u00edv volt, \u00e9s att\u00f3l m\u00e9g kisebbet is tal\u00e1ltunk.<\/p>\n
Mi van akkor, ha a t\u00f6mb\u00fcnk ezeket az elemeket tartalmazza:<\/p>\n
\r\nint[] tomb = {3,-2,7,6,-5,9,4,2,-7,-4};\r\nint min = 0;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] < tomb[min] ) min = i;\r\n}\r\nSystem.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);\r\n<\/pre>\nHa ekkor is az els\u0151 elemet tekintj\u00fck az els\u0151 minimumnak, akkor gond van, hiszen a legkisebb negat\u00edv sz\u00e1mot keress\u00fck, ez pedig nem is negat\u00edv? P\u00e1nikra semmi ok, hiszen az els\u0151 negat\u00edv sz\u00e1m ett\u0151l \u00fagyis kisebb lesz, \u00e9s akkor helyre\u00e1ll a vil\u00e1g rendje. Az eredm\u00e9ny: -7<\/p>\n
\u00c9s ha a t\u00f6mb \u00edgy n\u00e9z ki?<\/p>\n
\r\nint[] tomb = {3,2,7,6,5,9,4,2,7,4};\r\n<\/pre>\nBebuktuk… Az els\u0151t tekintj\u00fck az els\u0151 minimumnak, hiszen \u00edgy tanultuk. Az sem seg\u00edt rajtunk, hogy b\u00e1rmelyik negat\u00edv sz\u00e1m kisebb lesz egy pozit\u00edvn\u00e1l, \u00e9s akkor kicser\u00e9lhetj\u00fck, pontosan \u00fagy, ahogy az el\u0151z\u0151 p\u00e9ld\u00e1ban l\u00e1ttuk. De ebben a t\u00f6mbben nincs is negat\u00edv sz\u00e1m! Az eredm\u00e9ny: 2 Vagyis csak a legkisebbet tal\u00e1ltuk meg, ami viszont nem negat\u00edv!<\/p>\n
Az \u00f6tlet<\/h4>\n
Enn\u00e9l a feladatn\u00e1l azonban egy j\u00f3 \u00f6tlettel egyszer\u0171s\u00edteni lehet a feladaton. A minimumkeres\u00e9s eset\u00e9n ugye abb\u00f3l indulunk ki, hogy a t\u00f6mb els\u0151 elem\u00e9t tekintj\u00fck alaphelyzetben a legkisebbnek. Ezut\u00e1n a k\u00f6vetkez\u0151 elemt\u0151l kezd\u0151d\u0151en mindegyikkel \u00f6sszehasonl\u00edtjuk az addigi minimumot, \u00e9s ha az aktu\u00e1lis elem kisebb, akkor az lesz az \u00faj minimum. Nem felejtj\u00fck el, hogy tov\u00e1bbra is csak a minimumelem hely\u00e9t t\u00e1roljuk! Alapesetben k\u00e9tszer van gond ezzel a feladattal:<\/p>\n
\n- Az els\u0151 elem pozit\u00edv, de vannak ut\u00e1na negat\u00edv elemek.<\/li>\n
- Csak pozit\u00edv elemeket tartalmaz, teh\u00e1t az els\u0151 is az.<\/li>\n<\/ol>\n
Mindk\u00e9t esetben az a probl\u00e9ma, hogy eleve nem j\u00f3 elemet felt\u00e9telez\u00fcnk a legkisebbnek, mert a legkisebb negat\u00edvot keress\u00fck, de els\u0151k\u00e9nt egy pozit\u00edv elemet tekint\u00fcnk helyesnek.<\/p>\n
Az 1. esetben ezzel nincs gond, mivel van benne m\u00e9g negat\u00edv sz\u00e1m, az \u00fagyis kisebb lesz, teh\u00e1t gond megoldva. A 2. esetben gond van, mert az els\u0151 nem helyes elemet nem tudjuk kicser\u00e9lni egy negat\u00edv elemre, mivel nincs a t\u00f6mbben ilyen.<\/p>\n
Egy \u00f6tlettel m\u00e9gis meg tudjuk oldani a helyzetet: Ha az algoritmus v\u00e9g\u00e9n a legkisebb elem pozit\u00edv, akkor ki\u00edrhatjuk, hogy nincs benne negat\u00edv elem. Ha nem pozit\u00edv, akkor ki\u00edrjuk, hogy ez a minimum.<\/p>\n
Az univerz\u00e1lis megold\u00e1s<\/h4>\n
Akkor mit tehet\u00fcnk akkor, ha nincs \u00f6tlet\u00fcnk? Vagy az az \u00f6tlet nem haszn\u00e1lhat\u00f3 minden esetre? Akkor nem a sablon megold\u00e1st haszn\u00e1ljuk, elker\u00fclve ezzel azt, hogy rossz elemet v\u00e1lasszunk az elej\u00e9n. Vagyis nem az els\u0151t tekintj\u00fck a legkisebbnek. Senkit nem tekint\u00fcnk annak! Azt felt\u00e9telezz\u00fck, hogy nincs is ilyen. L\u00e1ssuk akkor ezt a megold\u00e1st.<\/p>\n
\r\nint[] tomb = new int[10];\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n tomb[i] = (int)(Math.random()*61)-10;\r\n}\r\n\r\nint min = -1;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] < 0 && (min == -1 || tomb[i] < tomb[min]) ) min = i;\r\n}\r\n\r\nif( min != -1 )\r\n{\r\n System.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);\r\n}\r\nelse\r\n{\r\n System.out.println("A tombben nincs negativ szam.");\r\n}\r\n<\/pre>\nA kiemelt r\u00e9szek jelent\u00e9se a k\u00f6vetkez\u0151:<\/p>\n
\n- 8 – Hopp\u00e1, -1 index\u0171 elem<\/strong> nem is l\u00e9tezhet! Igen, pont ez a l\u00e9nyeg. Az\u00e9rt hivatkozok nem l\u00e9tez\u0151 elemre, hogy a ciklus ut\u00e1n eld\u00f6nthessem, hogy tal\u00e1ltam-e egy\u00e1ltal\u00e1n olyan sz\u00e1mot, mely a felt\u00e9telemnek megfelel, vagy a t\u00f6mb nem is tartalmaz olyat.<\/li>\n
- 10 – Vedd \u00e9szre, hogy itt nem 1-t\u0151l indul a ciklusv\u00e1ltoz\u00f3<\/strong>! Mivel nem az els\u0151 elemet felt\u00e9telezz\u00fck a legkisebbnek, ez\u00e9rt az els\u0151t is meg kell vizsg\u00e1lni.<\/li>\n
- 12 – Na ez egy picit \u00f6sszetettebb:
\nAz \u00c9S-sel \u00f6sszek\u00f6t\u00f6tt r\u00e9szfelt\u00e9telek els\u0151 tagja: ha a sz\u00e1m negat\u00edv.<\/strong> Ez ugye az alapfelt\u00e9tel, hogy legkisebb negat\u00edv sz\u00e1mot keres\u00fcnk. Pozit\u00edv sz\u00e1mra nem cser\u00e9lhetj\u00fck le a minimumhelyet. Ami ut\u00e1na j\u00f6n az viszont megint egy \u00f6sszetett felt\u00e9tel:
\nha a min \u00e9rt\u00e9ke -1<\/strong>, vagyis m\u00e9g nem tal\u00e1ltunk olyan sz\u00e1mot, ami nek\u00fcnk j\u00f3
\nvagy
\naz aktu\u00e1lis elem kisebb, mint az eddigi minimum<\/strong> (ez meg az alap minimumkeres\u00e9s felt\u00e9tele)
\nHa az eg\u00e9sz felt\u00e9telt egyben n\u00e9zz\u00fck, akkor azt kapjuk, hogy ha a sz\u00e1munk negat\u00edv (teh\u00e1t megfelel az alapfelt\u00e9tel\u00fcnknek) \u00c9S m\u00e9g nem tal\u00e1ltunk egyet sem, ami j\u00f3, vagy m\u00e1r tal\u00e1ltunk olyat, ami j\u00f3, de a mostani kisebb t\u0151le, AKKOR legyen ez az \u00faj minimum helye.<\/li>\n- 15-22 – Ez a felt\u00e9teles r\u00e9sz m\u00e1r csak a v\u00e1laszt adja meg: Ha az eredeti -1 \u00e9rt\u00e9k\u0171 minimum maradt, akkor egy olyan sz\u00e1m sem volt, ami nek\u00fcnk j\u00f3 lenne, egy\u00e9bk\u00e9nt pedig ez lesz a felt\u00e9tel\u00fcnknek megfelel\u0151 sz\u00e1m helye.<\/li>\n<\/ul>\n
Ebben az \u00f6sszetett felt\u00e9telben nagyon fontos a felt\u00e9telek sorrendje!<\/p>\n
\n- El\u0151sz\u00f6r vizsg\u00e1lni kell, hogy egy\u00e1ltal\u00e1n megfelel\u0151 sz\u00e1mmal dolgozzak, ezt biztos\u00edtja azt, hogy csak negat\u00edv elemmel foglalkozzunk, a t\u00f6bbi alapb\u00f3l kiesik a kos\u00e1rb\u00f3l.<\/li>\n
- Azt\u00e1n megn\u00e9zem, hogy van-e egy\u00e1ltal\u00e1n minimum.<\/li>\n
- Majd ha m\u00e1r van minimum (vagyis nem -1 a min), akkor m\u00e1r t\u00e9nyleg \u00f6ssze lehet hasonl\u00edtani \u0151ket.<\/li>\n<\/ol>\n
Ha az \u00c9S ut\u00e1ni felt\u00e9telek nem megfelel\u0151 sorrendben \u00e1llnak, az mit okozhat? Fut\u00e1si hib\u00e1t! Mi\u00e9rt? Gondolj bele: a min -1 \u00e9rt\u00e9kr\u0151l indul. Ha negat\u00edv sz\u00e1mot tal\u00e1lok (1. felt\u00e9tel), akkor azonnal \u00f6ssze kell ezt hasonl\u00edtani a tomb[min] \u00e9rt\u00e9kkel? Nem is lehet, hiszen a min \u00e9rt\u00e9ke m\u00e9g -1, hiszen egy j\u00f3 sz\u00e1mom sem volt, akkor nincs is mihez hasonl\u00edtani. A t\u00f6mb[-1] elsz\u00e1ll, mint a gy\u0151zelmi z\u00e1szl\u00f3! A VAGY felt\u00e9teln\u00e9l az els\u0151 tag biztos\u00edtja azt, hogy a m\u00e1sodik csak akkor ker\u00fclj\u00f6n megvizsg\u00e1l\u00e1sra, ha az els\u0151 hamis. Vagyis: csak akkor vizsg\u00e1lhatom meg a tomb [min]-t, ha az val\u00f3ban l\u00e9tezik!<\/strong><\/p>\nEz a sz\u00e9p, vagy \u00e9pp ut\u00e1latos a programoz\u00e1sban, hogy gondolkodni kell benne, mert a vizsg\u00e1latok sorrendje sem biztos, hogy teljesen mindegy.<\/p>\n
Akkor l\u00e1ssuk, hogy mi\u00e9rt jobb egy \u00e1ltal\u00e1nosabb megold\u00e1st megjegyezni, mint k\u00fcl\u00f6n minden esetre egy-egy \u00f6tletet keresni. Mert az el\u0151z\u0151 tr\u00fckk a k\u00f6vetkez\u0151 feladatn\u00e1l nem m\u0171k\u00f6dik:<\/p>\n
Melyik a t\u00f6mbben szerepl\u0151 legnagyobb negat\u00edv sz\u00e1m?<\/h2>\n
N\u00e9zz\u00fck milyen esetek vannak:<\/p>\n
\n- A t\u00f6mb csak negat\u00edv elemeket tartalmaz.<\/li>\n
- A t\u00f6mb els\u0151 eleme negat\u00edv, de vannak benne pozit\u00edv elemek is.<\/li>\n
- A t\u00f6mb els\u0151 eleme pozit\u00edv, de vannak benne negat\u00edv elemek is.<\/li>\n
- A t\u00f6mb csak pozit\u00edv elemeket tartalmaz.<\/li>\n<\/ol>\n
Az els\u0151 eset m\u00e9g csak-csak m\u0171k\u00f6dne, hiszen csak negat\u00edv elemek eset\u00e9n a maximum az t\u00e9nyleg a legnagyobb negat\u00edv sz\u00e1m lesz. A t\u00f6bbin\u00e9l azonban a legnagyobb elem keres\u00e9se m\u00e1r komoly gondokba \u00fctk\u00f6zik.<\/p>\n
A maximumkeres\u00e9s sor\u00e1n arra kell figyelni, hogy a pozit\u00edv sz\u00e1mokat eleve ki kell z\u00e1rni a vizsg\u00e1latb\u00f3l, csak a negat\u00edv sz\u00e1mokra kell koncentr\u00e1lni. Most nem akarom \u00fajra v\u00e9gigmagyar\u00e1zni a teljes programot, n\u00e9zz\u00fck akkor a l\u00e9nyeget.<\/p>\n
\r\nint max = -1;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] < 0 && (max == -1 || tomb[i] > tomb[max]) ) max = i;\r\n}\r\n<\/pre>\n\n- 1 – Itt is -1 a maximum elem helye, mivel senkit nem tekint\u00fcnk alapb\u00f3l a legnagyobbnak.<\/li>\n
- 4 – Itt is 0-r\u00f3l indul a ciklusv\u00e1ltoz\u00f3, mivel az els\u0151 elemet is meg kell vizsg\u00e1lni.<\/li>\n
- 6 – A felt\u00e9tele is nagyon hasonl\u00f3: Ha negat\u00edv sz\u00e1mot tal\u00e1lunk \u00c9S eddig nincs maximum VAGY az aktu\u00e1lis elem nagyobb az eddigin\u00e9l, AKKOR ez az \u00faj maximum.<\/li>\n<\/ul>\n
Ha valakinek nagyon nem megy ez az \u00f6sszetett felt\u00e9tel, ak\u00e1r fel is bonthat\u00f3:<\/p>\n
(felt\u00e9tel1 \u00c9S (felt\u00e9tel2 VAGY felt\u00e9tel3))\r\nhelyett\r\n((felt\u00e9tel1 \u00c9S felt\u00e9tel2) VAGY (felt\u00e9tel1 \u00c9S felt\u00e9tel3))<\/pre>\nMegjegyzem, itt sem lehet a VAGY k\u00e9t tagj\u00e1t felcser\u00e9lni, az ugyan\u00fagy fut\u00e1si hib\u00e1t okozhat. A felt\u00e9telek sorrendje k\u00f6t\u00f6tt!<\/p>\n
Melyik a t\u00f6mbben szerepl\u0151 legkisebb pozit\u00edv sz\u00e1m?<\/h2>\n
Az el\u0151z\u0151h\u00f6z hasonl\u00f3. A fenti \u00f6tlet itt sem m\u0171k\u00f6dik. Pr\u00f3b\u00e1ld meg az el\u0151z\u0151 megold\u00e1s alapj\u00e1n saj\u00e1t magad meg\u00edrni a helyes algoritmust. Ha nem megy, a megold\u00e1s alul tal\u00e1lhat\u00f3 minden k\u00fcl\u00f6n\u00f6sebb magyar\u00e1zat n\u00e9lk\u00fcl.<\/p>\n
\r\nint[] tomb = new int[10];\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n tomb[i] = (int)(Math.random()*61)-10;\r\n}\r\n\r\nint min = -1;\r\n\r\nfor( int i = 0; i < tomb.length; i++ )\r\n{\r\n if( tomb[i] > 0 && (min == -1 || tomb[i] < tomb[min]) ) min = i;\r\n}\r\n\r\nif( min != -1 )\r\n{\r\n System.out.println("A tombbeli legkisebb pozitiv szam: "+tomb[min]);\r\n}\r\nelse\r\n{\r\n System.out.println("A tombben nincs pozitiv szam.");\r\n}\r\n<\/pre>\nTerm\u00e9szetesen ett\u0151l k\u00fcl\u00f6nb\u00f6z\u0151 megold\u00e1sok is l\u00e9teznek, \u00e9s azok is teljesen helyesek lehetnek. Az is lehet, hogy egyszer\u0171bb, mint a megold\u00e1som. Nyilv\u00e1n\u00a0 \u00e9n is megtehettem volna, hogy a legnagyobb negat\u00edv sz\u00e1m eset\u00e9n kiv\u00e1logatom a negat\u00edv sz\u00e1mokat egy m\u00e1sik t\u00f6mbbe, \u00e9s arra r\u00e1eresztek egy maximumkeres\u00e9st minden k\u00fcl\u00f6n\u00f6sebb felt\u00e9telvizsg\u00e1lat n\u00e9lk\u00fcl. \u00c9n csak egy gondolatmenetet k\u00edv\u00e1ntam megosztani, ami h\u00e1tha inspir\u00e1lja azokat, akik vagy nem tudt\u00e1k megoldani ezeket a feladatokat, vagy a megold\u00e1suk bonyolult.<\/p>\n","protected":false},"excerpt":{"rendered":"
L\u00e1thattad, hogy az alap algoritmusok nagyon sokf\u00e9le feladatra szinte k\u00e9sz megold\u00e1sokat adnak. A val\u00f3s\u00e1gban azonban sokszor nem ilyen tiszta form\u00e1ban fordulnak el\u0151, mivel a felt\u00e9telek lehetnek bonyolultabbak is. Nem ennyire egyszer\u0171 a dolog, ha p\u00e9ld\u00e1ul a k\u00e9rd\u00e9s nem puszt\u00e1n a Tov\u00e1bb Java kieg\u00e9sz\u00edt\u0151 lecke – Alap algoritmusok speci\u00e1lis esetekben<\/span>