{"id":1242,"date":"2015-03-31T09:18:37","date_gmt":"2015-03-31T07:18:37","guid":{"rendered":"http:\/\/www.webotlet.hu\/?p=1242"},"modified":"2024-09-21T08:53:44","modified_gmt":"2024-09-21T06:53:44","slug":"java-kiegeszito-lecke-tobbszoros-megszamlalas","status":"publish","type":"post","link":"https:\/\/www.webotlet.hu\/?p=1242","title":{"rendered":"Java kieg\u00e9sz\u00edt\u0151 lecke – T\u00f6bbsz\u00f6r\u00f6s megsz\u00e1ml\u00e1l\u00e1s"},"content":{"rendered":"

Csak akkor olvass tov\u00e1bb, ha a t\u00f6bbsz\u00f6r\u00f6s megsz\u00e1ml\u00e1l\u00e1s<\/a> feladatot megoldottad, vagy nem siker\u00fclt megoldani.<\/strong><\/h3>\n

Alapeset<\/h4>\n

Az alap probl\u00e9ma teh\u00e1t az, hogy sz\u00e1moljuk meg, egy sz\u00e1m h\u00e1nyszor fordul el\u0151 egy olyan t\u00f6mbben, amely a [0;10] intervallumb\u00f3l tartalmaz elemeket.<\/p>\n

A megold\u00e1s rendk\u00edv\u00fcl egyszer\u0171 \u00e9s eleg\u00e1ns. El\u0151sz\u00f6r is sz\u00fcks\u00e9g\u00fcnk van egy olyan t\u00f6mbre, melynek akkora a m\u00e9rete, mint ah\u00e1ny f\u00e9le sz\u00e1mot tartalmaz az a t\u00f6mb, melyben a megsz\u00e1moland\u00f3 sz\u00e1mok vannak. Ez a t\u00f6mb tartalmazza majd azt, hogy a sz\u00e1mok k\u00f6z\u00fcl melyiket h\u00e1nyszor sz\u00e1moltuk meg. Mivel a t\u00f6mb, melyben a megsz\u00e1ml\u00e1land\u00f3 sz\u00e1mok vannak csak a [0;10] intervallumb\u00f3l tartalmaz \u00e9rt\u00e9keket, ez\u00e9rt itt 11 f\u00e9le sz\u00e1m fordulhat csak el\u0151. A darabsz\u00e1mokat tartalmaz\u00f3 t\u00f6mb m\u00e9rete \u00edgy 11 lesz.<\/p>\n

A tr\u00fckk l\u00e9nyege az, hogy az megsz\u00e1ml\u00e1l\u00e1s eredm\u00e9ny\u00e9t tartalmaz\u00f3 t\u00f6mb megfelel\u0151 indexei fogj\u00e1k jelenteni a megsz\u00e1ml\u00e1land\u00f3 sz\u00e1mokat, az adott index\u0171 elem \u00e9rt\u00e9ke pedig a darabsz\u00e1mot.<\/p>\n

N\u00e9zz\u00fck mit jelent p\u00e9ld\u00e1ul az, ha a darabsz\u00e1mokat tartalmaz\u00f3 t\u00f6mb a megsz\u00e1ml\u00e1l\u00e1s ut\u00e1n \u00edgy n\u00e9z ki. Ez csak egy p\u00e9lda, nem a feladat eredm\u00e9nye. A megjegyz\u00e9s sorban a darab t\u00f6mb indexei szerepelnek, alatta pedig az adott indexhez tartoz\u00f3 \u00e9rt\u00e9kek:<\/p>\n

\r\n\/\/ 0  1  2  3  4  5  6  7  8  9  10\r\n{  5, 3, 0, 7, 3, 8, 2, 8, 9, 2, 0 }\r\n<\/pre>\n
Ez ebben az esetben azt jelenti, hogy a 0 sz\u00e1mb\u00f3l 5 darabot sz\u00e1moltunk, az 1-es sz\u00e1mb\u00f3l 3-at, 2-es sz\u00e1m nem szerepelt, stb.<\/p>\n
A sz\u00e9p az eg\u00e9szben az, hogy m\u00e9g felt\u00e9telvizsg\u00e1latra sincs sz\u00fcks\u00e9g a megsz\u00e1ml\u00e1l\u00e1sra, de p\u00e9ld\u00e1n kereszt\u00fcl hamarabb meg\u00e9rtj\u00fck.<\/p>\n
\r\nint[] szamok = { 2,5,4,0,10,1,4,8,5,2,8,1,9,10,\r\n               7,7,3,5,2,4,3,8,0,8,10,8,1,1,8,\r\n               10,7,7,3,8,3,6,6,7,5,8,9,3,9,3,\r\n               5,9,9,5,2,8,10,4,1,0,4,9,2,5,5 };\r\nint[] db = new int[11];\r\nfor( int i = 0; i < szamok.length; i++ )\r\n{\r\n  db[ szamok[i] ]++;\r\n}\r\nSystem.out.println("A tombben levo szamok darabszama:");\r\nfor( int i = 0; i < db.length; i++ )\r\n{\r\n  System.out.println(i+": "+db[i]);\r\n}\r\n<\/pre>\n
Ennyi lenne csak? Igen. Mit is csin\u00e1lunk? A db t\u00f6mb megfelel\u0151 hely\u00e9n l\u00e9v\u0151 sz\u00e1mot megn\u00f6velj\u00fck eggyel. Pontosabban: a db t\u00f6mb “sz\u00e1modik” index\u0171 elem\u00e9t megn\u00f6velj\u00fck eggyel. Vagyis ha a ‘szamok’ t\u00f6mbben \u00e9ppen egy 3-as sz\u00e1mn\u00e1l j\u00e1runk, akkor a db[3] elemet n\u00f6velj\u00fck meg eggyel, vagyis megsz\u00e1moltuk! A v\u00e9g\u00e9n pedig az eredm\u00e9nyt\u00f6mbben l\u00e1tni fogjuk, melyik indexn\u00e9l milyen \u00e9rt\u00e9k szerepel, vagyis melyik sz\u00e1mb\u00f3l h\u00e1ny darab volt.<\/p>\n
Pozit\u00edv ir\u00e1nyba eltolt intervallum<\/h4>\n
Ok\u00e9, de mi van akkor, ha az intervallum nem 0-val kezd\u0151dik, vagyis valamilyen ir\u00e1nyba el kellett tolni? P\u00e9ld\u00e1ul a t\u00f6mbben l\u00e9v\u0151 sz\u00e1mok intervalluma [5;20], mint ahogy az egyik feladatban is szerepel. Akkor a darabokat t\u00e1rol\u00f3 t\u00f6mb m\u00e9ret\u00e9t is ennek megfelel\u0151en kell megv\u00e1lasztani, vagyis 0-20 indexeknek kell rendelkez\u00e9sre \u00e1llni. Az egy dolog, hogy a 0-4 indexeknek itt semmi jelent\u0151s\u00e9ge nem lesz, de ez senkit nem \u00e9rdekel. Ami fontos, hogy k\u00fcl\u00f6nbs\u00e9get tudj tenni ak\u00f6z\u00f6tt, hogy a 3-as index eleme nulla, \u00e9s a 7-es index eleme nulla. Az els\u0151 ugye egy nem l\u00e9tez\u0151 sz\u00e1m, mert ilyen sz\u00e1m nincs az intervallumban. A 7-es index eleme pedig azt jelenti, hogy nincs 7-es sz\u00e1m a t\u00f6mbben. L\u00e1ssuk akkor \u00edgy a p\u00e9ld\u00e1t:<\/p>\n
\r\nint[] szamok = { 13,18,11,14,17,12,18,11,11,17,17,13,\r\n                 5,13,5,14,19,5,11,15,11,12,13,20,\r\n                 18,16,16,13,11,17,17,19,5,14,11,\r\n                 14,11,14,8,14,13,20,17,6,20,17,\r\n                 18,9,9,12,15,20,10,5,7,11,19,16,\r\n                 11,10,10,11,14,20,5,10,10 };\r\nint[] db = new int[21];\r\nfor( int i = 0; i < szamok.length; i++ )\r\n{\r\n  db[ szamok[i] ]++;\r\n}\r\nSystem.out.println("A tombben levo szamok darabszama:");\r\nfor( int i = 5; i < db.length; i++ )\r\n{\r\n  System.out.println(i+": "+db[i]);\r\n}\r\n<\/pre>\n
Ha jobban megn\u00e9zed, az algoritmusban gyakorlatilag csak a k\u00e9t kiemelt sorban van k\u00fcl\u00f6nbs\u00e9g. Az egyik az, hogy m\u00e1s a t\u00f6mb m\u00e9rete, amibe meg akarom sz\u00e1molni az egyes sz\u00e1mok el\u0151fordul\u00e1sait. A m\u00e1sik az, hogy amikor a darabsz\u00e1maikat ki akarom \u00edrni, akkor az els\u0151 5 elemet kihagyom, hiszen azok nem val\u00f3di eredm\u00e9nyt tartalmaznak.<\/p>\n
Negat\u00edv ir\u00e1nyba eltolt intervallum<\/h4>\n
Eddig rendben is voln\u00e1nk, b\u00e1rmilyen nem negat\u00edv sz\u00e1mokat tartalmaz\u00f3 t\u00f6mbben k\u00f6nnyen megsz\u00e1molhatjuk az el\u0151fordul\u00e1sokat. \u00c9s ha negat\u00edv ir\u00e1nyba toltuk el? Negat\u00edv indexek nem l\u00e9teznek. Akkor mit tehet\u00fcnk? Toljuk el \u00fagy, hogy nek\u00fcnk j\u00f3 legyen.<\/p>\n
A feladat alapj\u00e1n a t\u00f6mbben l\u00e9v\u0151 sz\u00e1mok a [-10;10] intervallumban vannak. Akkor mit csin\u00e1ljunk? Azt, hogy h\u00e1ny f\u00e9le sz\u00e1mot kell megsz\u00e1molni, k\u00f6nnyen megkaphatjuk, hiszen csak az intervallum m\u00e9ret\u00e9t kell kisz\u00e1molni. Ha eml\u00e9kszel r\u00e1, ezt m\u00e1r a v\u00e9letlen sz\u00e1mok sorsol\u00e1s\u00e1n\u00e1l is kihaszn\u00e1ltuk: fels\u0151-als\u00f3+1=21. Ha ez megvan, akkor l\u00e9trehozunk egy ekkora t\u00f6mb\u00f6t, melybe a darabsz\u00e1mokat r\u00f6gz\u00edtj\u00fck. A megsz\u00e1ml\u00e1l\u00e1s sor\u00e1n pedig mi figyel\u00fcnk arra, hogy az intervallumot meg az elemeket is az eltol\u00e1s m\u00e9rt\u00e9k\u00e9nek megfelel\u0151en kezelj\u00fck. Mennyivel kell \u00e9s merre eltolni ezt az intervallumot, hogy a kezd\u0151pontja a 0 legyen? +10-zel, igaz?<\/p>\n
Akkor l\u00e1ssuk a megold\u00e1st ennek megfelel\u0151en:<\/p>\n
\r\nint[] szamok = { -2,9,4,2,6,4,2,-9,5,-1,0,-6,-6,\r\n                 2,-3,-9,-4,7,-2,-9,3,5,-9,2,-5,\r\n                 -8,-5,0,-9,-7,-8,-2,9,5,7,-7,\r\n                 -1,3,-9,0,9,-3,-1,2,-3,8,-9,4,\r\n                 -2,-2,-4,6,-5,-3,6,10,-3,8,5,\r\n                 -6,1,-9,-9,-4, 8,0,3 };\r\nint[] db = new int[21];\r\nfor( int i = 0; i < szamok.length; i++ )\r\n{\r\n  db[ szamok[i]+10 ]++;\r\n}\r\nSystem.out.println("A tombben levo szamok darabszama:");\r\nfor( int i = 0; i < db.length; i++ )\r\n{\r\n  System.out.println((i-10)+": "+db[i]);\r\n}\r\n<\/pre>\n
Itt az\u00e9rt picit t\u00f6bb sort emeltem ki, n\u00e9zz\u00fck \u0151ket t\u00e9telesen:<\/p>\n