Nézzük meg a csomagok és az osztályok közötti összefüggéseket egy kicsit.
A típusok könnyebb megtalálásához és használatához, névütközések elkerüléséhez és az elérés szabályozásához a programozók egybe csomagolhatják az összetartozó típusaikat csomagokká.
Definíció: A csomag összetartozó típusok gyűjteménye.
A Java platform típusai funkciók szerint különböző csomagokba vannak szervezve: az alapvető osztályok a java.lang csomagban, az I/O osztályok a java.io-ban, és így tovább. Ezen kívül a saját típusainkat is tehetjük csomagokba.
A következő osztályokat megvizsgálva látszik, hogy közös csomagba érdemes őket sorolni, mivel grafikus objektumok csoportjába tartoznak a körök, téglalapok, vonalak és pontok. Ha írunk egy Draggable interfészt, az azt megvalósító osztályok lehetővé teszik a vonszolást is.
//in the Graphic.java file
public abstract class Graphic {
. . .
}
//in the Circle.java file
public class Circle extends Graphic implements Draggable {
. . .
}
//in the Rectangle.java file
public class Rectangle extends Graphic implements Draggable {
. . .
}
//in the Draggable.java file
public interface Draggable {
. . .
}
A következő okok miatt érdemes az osztályokat és interfészeket közös csomagba helyezni:
Más programozók számára is látszik, hogy kapcsolódó típusokról van szó.
Más programozók is láthatják, hol kell keresni a grafikához kapcsolódó osztályokat.
A típusaink nevei nem kerülnek összeütközésbe más csomagok neveivel, mert a csomagok önálló névtereket hoznak létre.
A típusaink korlátlanul láthatják egymást, de egyéb típusok csak korlátozottan férhetnek a
típusokhoz.
Importálásról egy kicsit; Egy csomag tag importálása
Ahhoz hogy importálhassuk a megadott tagot az aktuális fájlban, a fájl elején ki kell adni az import utasítást az osztály vagy interfész definiálása előtt, de a package utasítás után, ha van olyan. Úgy tudjuk importálni a Circle osztályt a graphics csomagból, hogy:
import graphics.Circle;
Most már tudunk hivatkozni a Circle osztályra az egyszerű nevével:
Circle myCircle = new Circle();
Ez a szemlélet akkor működik jól, ha csak néhány tagot használunk a graphics csomagból. De ha sok típusát használjuk egy csomagnak, akkor inkább importáljuk az egész csomagot.Egy teljes csomag importálása
Ahhoz hogy egy csomagnak az összes típusát importáljuk, az import utasítást a csillag (*) helyettesítő karakterrel kell használnunk:
import graphics.*;
Most már hivatkozhatunk bármelyik osztályra vagy interfészre a graphics csomagból az egyszerű rövid nevével:
Circle myCircle = new Circle();
Rectangle myRectangle = new Rectangle();
Az import utasításban a csillag karakterrel az összes osztályát megadjuk a csomagnak. Nem használhatunk olyan megfeleltetést, amely egy csomagban egy osztály részhalmazára utal. Például helytelen megfeleltetés az, hogy a graphics csomagból az ’A’ betűvel kezdődő összes osztály importáljuk:
import graphics.A*;
Ez az utasítás fordítási hibát generál. Az import utasítással, egy csomagnak egyetlen tagját vagy egész csomagot importálhatunk.
Ugyanígy nem megengedett, hogy egyszerre több csomagot importáljunk, pl.:
import graphics.*.*;
Megjegyzés: Ha kevesebb tagot akarunk importálni, akkor megengedett, hogy csak egy osztályt, és annak a belső osztályait importáljuk. Például, ha a graphics.Rectangle osztálynak a belső osztályait akarjuk használni, mint Rectangle.DoubleWide és Rectangle.Square, a következőképpen importálhatjuk:
import graphics.Rectangle.*;
Könnyítésül a Java fordító automatikusan importál három teljes csomagot:
A névtelen csomagot (ha nem hozunk létre csomagot, vagyis nem használjuk a package utasítást)
Az alapértelmezés szerinti aktuális csomagot (ha létrehozunk csomagot)
A java.lang csomagot
Megjegyzés: A csomagok nem hierarchikusak. Ha például importáljuk a java.util.*-ot, nem hivatkozhatunk a Pattern osztályra. Minden esetben úgy kell hivatkoznunk, hogy java.util.regex.Pattern, vagy ha importáljuk a java.util.regex.*-ot, akkor csak egyszerűen Pattern.
Mik a csomagok?
A típusok könnyebb megtalálásához és használatához, névütközések elkerüléséhez és az elérés szabályozásához a programozók egybe csomagolhatják az összetartozó típusaikat csomagokká.
Definíció: A csomag összetartozó típusok gyűjteménye.
A Java platform típusai funkciók szerint különböző csomagokba vannak szervezve: az alapvető osztályok a java.lang csomagban, az I/O osztályok a java.io-ban, és így tovább. Ezen kívül a saját típusainkat is tehetjük csomagokba.
A következő osztályokat megvizsgálva látszik, hogy közös csomagba érdemes őket sorolni, mivel grafikus objektumok csoportjába tartoznak a körök, téglalapok, vonalak és pontok. Ha írunk egy Draggable interfészt, az azt megvalósító osztályok lehetővé teszik a vonszolást is.
//in the Graphic.java file
public abstract class Graphic {
. . .
}
//in the Circle.java file
public class Circle extends Graphic implements Draggable {
. . .
}
//in the Rectangle.java file
public class Rectangle extends Graphic implements Draggable {
. . .
}
//in the Draggable.java file
public interface Draggable {
. . .
}
A következő okok miatt érdemes az osztályokat és interfészeket közös csomagba helyezni:
Más programozók számára is látszik, hogy kapcsolódó típusokról van szó.
Más programozók is láthatják, hol kell keresni a grafikához kapcsolódó osztályokat.
A típusaink nevei nem kerülnek összeütközésbe más csomagok neveivel, mert a csomagok önálló névtereket hoznak létre.
A típusaink korlátlanul láthatják egymást, de egyéb típusok csak korlátozottan férhetnek a
típusokhoz.
Csomag létrehozása
A csomag létrehozásához mindössze bele kell tenni egy típust (osztály, interfész). A csomag megnevezést a forrásállomány elején, a típusdefiníciók előtt kell megtenni.
package graphics;
public class Circle extends Graphic implements Draggable {
. . .
}
Ez után a graphics csomag összes forráskódja elején ugyanezt a csomagmegjelölést kell alkalmaznunk, hogy közös csomagba kerüljenek:
package graphics;
public class Rectangle extends Graphic implements Draggable {
. . .
}
Ha nem alkalmazunk csomagmegjelölést, akkor az osztály(ok) egy úgynevezett alapértelmezett név nélküli csomagba kerülnek.
Egy csomag elnevezése
Az egész világon írnak a programozók a Java programnyelvhez osztályokat, interfészeket, kulcsszavakat és megjegyzéseket, és valószínűleg két programozó ugyanazt a nevet két különböző feladatú osztálynál fogja használni. Valójában, az előző példa esetén, amikor definiálunk egy Rectangle osztályt, akkor a Rectangle osztály már benne van a java.awt csomagban. A fordító mégis engedélyezi két osztálynak ugyanazt a nevet. Miért? Mert azok különböző csomagokban vannak, és mindegyik osztálynak a teljes neve magába foglalja a csomag nevét. Tehát a graphics csomagban levő Rectangle osztály teljes neve graphics.Rectangle, és a java.awt csomagban levő Rectangle osztály teljes neve java.awt.Rectangle. Ez rendszerint csak akkor működik jól, hogyha két egymástól független programozó nem ugyanazt a nevet adja a csomagoknak. Mivel hárítható el ez a probléma? Megállapodással.
Megállapodás: Fordított domain (tartomány) nevet használnak a csomagok nevének, ilyen módon: com.company.package. Névütközés előfordulhat egyetlen cégen belül is, amit a cégnek le kell kezelni egy belső megállapodással. Lehet, hogy emiatt tartalmazni fog tartomány vagy projekt neveket a társaság neve után, mint például com.company.region.package.
Csomag tagok használata
Csak a publikus csomag tagok érhetőek el a csomagon kívül. Ahhoz hogy használjunk egy publikus csomag tagot a csomagján kívülről, a következők valamelyikét kell tennünk (vagy akár többet):
A teljes (vagy más néven minősített) nevén keresztül kell hivatkoznunk rá
Importáljuk a csomag tagot
Importáljuk a tag teljes csomagját
Mindegyiket különböző szituációkban alkalmazhatjuk, amelyeket a következő részekben tisztázunk.
Név szerinti hivatkozás egy csomag tagra
Eddig a példákban a típusokra az egyszerű nevükön keresztül hivatkoztunk, mint például Rectangle. Akkor használhatjuk egy csomag tagjának az egyszerű nevét, ha az osztály ugyanabban a csomagban van, mint a tag, vagy ha a tag importálva van.
Ha megpróbálunk használni egy tagot egy másik csomagból, és a csomagot nem importáltuk, akkor a tag teljes nevét használnunk kell. A Rectangle osztály teljes neve:
graphics.Rectangle
A következőképpen használhatjuk a minősített nevet, hogy létrehozzuk a graphics.Rectangle osztály egy példányát:
graphics.Rectangle myRect = new graphics.Rectangle();
Ha minősített neveket használunk, valószínűleg bosszantó lesz, hogy újra és újra be kell gépelni a graphics.Rectangle-t. Ezen kívül rendezetlen és nehezen olvasható programot kapunk. Ilyen esetekben inkább importáljuk a tagot.
Egy csomag tag importálása
Ahhoz hogy importálhassuk a megadott tagot az aktuális fájlban, a fájl elején ki kell adni az import utasítást az osztály vagy interfész definiálása előtt, de a package utasítás után, ha van olyan. Úgy tudjuk importálni a Circle osztályt a graphics csomagból, hogy:
import graphics.Circle;
Most már tudunk hivatkozni a Circle osztályra az egyszerű nevével:
Circle myCircle = new Circle();
Ez a szemlélet akkor működik jól, ha csak néhány tagot használunk a graphics csomagból. De ha sok típusát használjuk egy csomagnak, akkor inkább importáljuk az egész csomagot.
Egy teljes csomag importálása
Ahhoz hogy egy csomagnak az összes típusát importáljuk, az import utasítást a csillag (*) helyettesítő karakterrel kell használnunk:
import graphics.*;
Most már hivatkozhatunk bármelyik osztályra vagy interfészre a graphics csomagból az egyszerű rövid nevével:
Circle myCircle = new Circle();
Rectangle myRectangle = new Rectangle();
Az import utasításban a csillag karakterrel az összes osztályát megadjuk a csomagnak. Nem használhatunk olyan megfeleltetést, amely egy csomagban egy osztály részhalmazára utal. Például helytelen megfeleltetés az, hogy a graphics csomagból az ’A’ betűvel kezdődő összes osztály importáljuk:
import graphics.A*;
Ez az utasítás fordítási hibát generál. Az import utasítással, egy csomagnak egyetlen tagját vagy egész csomagot importálhatunk.
Ugyanígy nem megengedett, hogy egyszerre több csomagot importáljunk, pl.:
import graphics.*.*;
Tehát!
A Java programozási nyelv támogatja az alapvető aritmetikai számításokat az aritmetikai operátorokkal együtt: +, -, *, /, és %.
A java.lang csomagban a Java platform biztosítja a Math osztályt.
Ez olyan metódusokat és változókat biztosít, amik segítségével már magasabb rendű matematikai számítások is elvégezhetők, mit például egy szög szinuszának kiszámítása, vagy egy szám bizonyos hatványra emelése.
A Math osztály metódusai osztálymetódusok, tehát közvetlenül az osztály nevével kell őket meghívni, például így:
Math.round(34.87);
A Math osztály metódusai közül elsőként különböző alapvető matematikai függvényeket nézzük meg, mint például egy szám abszolút értékének kiszámítása vagy egy szám kerekítése valamelyik irányban. A következő lista ezeket a metódusokat tartalmazza:
double abs(double) float abs(float) int abs(int) long abs(long) A paraméterként kapott paraméter abszolút értékével tér vissza.
double ceil(double) A legkisebb double értékkel tér vissza, ami nagyobb vagy egyenlő a paraméterrel, és egyenlő egy egész számmal. (felfelé kerekít)
double floor(double) A legnagyobb double értékkel tér vissza, ami kisebb vagy egyenlő a paraméterrel, és azonos egy egész számmal. (lefelé kerekít)
double rint(double) A paraméterhez legközelebb álló double értékkel tér vissza, és azonos egy egész számmal. (a legközelebbi egészhez kerekít)
long round(double) int round(float) A legközelebbi long vagy int értéket adja vissza, ahogy azt a metódus visszatérési értéke jelzi.
A következő BasicMathDemo program néhány alkalmazási módot illusztrál a fentiekre:
public class BasicMathDemo {
public static void main(String[] args) {
double aNumber = -191.635;
System.out.println("The absolute value of " + aNumber + " is " + Math.abs(aNumber));
System.out.println("The ceiling of " + aNumber +" is "+ Math.ceil(aNumber));
System.out.println("The floor of " + aNumber + " is " + Math.floor(aNumber));
System.out.println("The rint of " + aNumber + " is " + Math.rint(aNumber));
}
}
A program kimenetei:
The absolute value of -191.635 is 191.635
The ceiling of -191.635 is -191
The floor of -191.635 is -192
The rint of -191.635 is -192
További két alapvető metódus található a Math osztályban. Ezek a min és a max. Az alábbi táblázat mutatja be a min és max metódusok különböző formáit, amik két számot hasonlítanak össze, és a megfelelő típusú értékkel térnek vissza.
double min(double, double) float min(float, float) int min(int, int) long min(long, long) A két paraméterből a kisebbel térnek vissza.
double max(double, double) float max(float, float) int max(int, int) long max(long, long) A két paraméterből a nagyobbal térnek vissza.
A MinDemo program mutatja be a min alkalmazását két érték közül a kisebb kiszámítására:
public class MinDemo {
public static void main(String[] args) {
double enrollmentPrice = 45.875;
double closingPrice = 54.375;
System.out.println("A vételár: $" + Math.min(enrollmentPrice, closingPrice));
}
}
A program valóban az alacsonyabb árat adta vissza:
A vételár: $45.875
A Math osztály következő metódusai a hatványozással kapcsolatosak. Ezen kívül megkaphatjuk az e értékét a Math.E használatával.
double exp(double) A szám exponenciális értékével tér vissza.
double log(double) A szám természetes alapú logaritmusával tér vissza.
double pow(double, double) Az első paramétert a második paraméternek megfelelő hatványra emeli.
double sqrt(double) A paraméter négyzetgyökével tér vissza.
A következő ExponentialDemo program kiírja az e értékét, majd meghívja egyenként a fenti táblázatban látható metódusokat egy számra:
public class ExponentialDemo {
public static void main(String[] args) {
double x = 11.635;
double y = 2.76;
System.out.println("Az e értéke: " + Math.E);
System.out.println("exp(" + x + ") is " + Math.exp(x));
System.out.println("log(" + x + ") is " + Math.log(x));
System.out.println("pow(" + x + ", " + y + ") is " + Math.pow(x, y));
System.out.println("sqrt(" + x + ") is " + Math.sqrt(x));
}
}
Az ExponentialDemo kimenete:
Az e értéke: 2.71828
exp(11.635) is 112984
log(11.635) is 2.45402
pow(11.635, 2.76) is 874.008
sqrt(11.635) is 3.41101
A Math osztály egy sor trigonometrikus függvényt is kínál, ezek a következő táblázatban vannak összefoglalva. A metóduson áthaladó szögek radiánban értendők. Radiánból fokká, és onnan visszakonvertálásra két függvény áll rendelkezésünkre: toDegrees és toRadians. Előbbi fokká, utóbbi radiánná konvertál. A Math.PI függvény meghívásával a PI értékét kapjuk meg a lehető legpontosabban.
double sin(double) Egy double szám szinuszával tér vissza.
double cos(double) Egy double szám koszinuszával tér vissza.
double tan(double) Egy double szám tangensével tér vissza.
double asin(double) Egy double szám arc szinuszával tér vissza.
double acos(double) Egy double szám arc koszinuszával tér vissza.
double atan(double) Egy double szám arc tangensével tér vissza.
double atan2(double) Derékszögű koordinátákat konvertál (b, a) polárissá (r, théta).
double toDegrees(double) double toRadians(double) A paramétert radiánná vagy fokká konvertálják, a függvények adják magukat.
A következő TrigonometricDemo program használja a fenti táblázatban bemutatott összes metódust, hogy különböző trigonometrikus értékeket számoljon ki a 45 fokos szögre:
public class TrigonometricDemo {
public static void main(String[] args) {
double degrees = 45.0;
double radians = Math.toRadians(degrees);
System.out.println("The value of pi is " + Math.PI);
System.out.println("The sine of " + degrees + " is " + Math.sin(radians));
System.out.println("The cosine of " + degrees + " is " + Math.cos(radians));
System.out.println("The tangent of " + degrees + " is " + Math.tan(radians));
}
}
A program kimenetei:
The value of pi is 3.141592653589793
The sine of 45.0 is 0.8060754911159176
The cosine of 45.0 is -0.5918127259718502
The tangent of 45.0 is -1.3620448762608377
Megjegyezzük, hogy a NaN akkor jelenik meg, amikor az eredmény matematikailag nem definiált. A Double és a Float osztályok is tartalmazzák a NaN konstanst. Összehasonlítva a visszatérési értéket az egyik ilyen konstanssal, a programunk el tudja dönteni, hogy a visszaadott érték érvényes-e. Ilyen módon a programunk elfogadhatóan tud reagálni, ha egy metódus nem definiált értéket kap.
Az utolsó Math metódus, amiről szót ejtünk, a random. A metódus egy kvázi-véletlen 0.0 és 1.0 közé eső számmal tér vissza. Pontosabban leírva:
0.0 ≤ Math.random() < 1.0
Hogy más intervallumban kapjunk meg számokat, műveleteket hajthatunk végre a függvény által visszaadott értéken. Például, ha egy egész számot szeretnénk kapni 1 és 10 között, akkor a következőt kell begépelnünk:
int number = (int)(Math.random() * 10 + 1);
Megszorozva ezt az értéket 10-el a lehetséges értékek intervalluma megváltozik:
0.0 ≤ szám < 10.0.
1-et hozzáadva az intervallum ismét megváltozik:
1.0 ≤ szám < 11.0.
Végül, az érték egésszé konvertálásával egy konkrét számot (int) kapunk 1 és 10 között.
A Math.random használata tökéletes, ha egy egyszerű számot kell generálni. Ha egy véletlen számsorozatot kell generálni, akkor egy hivatkozást kell létrehozni a java.util.Random–ra, és meghívni ennek az objektumnak a különböző metódusait.
Osztály és csomag
Tartalom:
12.1. Osztály létrehozása
12.2. Adattagok
12.3. Inicializáló blokkok
12.4. Konstruktorok, példányosítás
12.5. Metódusok
12.6. Csomag
12.7. Tesztkérdések
12.8. Feladatok
12.1. Osztály létrehozása
A Java nyelven való programozás az adattagokkal és metódusokkal rendelkező objektumok programozását jelenti. Nem beszélhetünk klasszikus értelemben vett eljárásokról és függvényekről, csak objektumok együttműködéséről, amely a közöttük lévő kommunikációval valósul meg.
Objektumot egy osztály példányosításával hozhatunk létre. Ha nem áll rendelkezésünkre megfelelő osztály, akkor nekünk kell definiálni egyet. Azaz először a "tervrajzot" kell elkészíteni, majd az alapján lehet objektumokat létrehozni.
Az osztálydefiníció általános szintaxisa a következő:
Osztály fej:
[módosítók] class <osztály_neve> [extends <szülő_osztály_neve>] [implements <interfészek_neve>]
Osztály törzs:
{
[adattag deklarációk];
[inicializáló blokkok];
[konstruktor deklarációk];
[metódus deklarációk];
}
Az osztály fejrészének módosítói nemcsak hozzáférési szinteket takarhatnak, hanem opcionálisan egyéb attribútumokat is:
Osztály-fejrész módosítók:
[hozzáférési szint]: public | üres (csomagszintű)
[abstract]: nem példányosítható osztály, amely öröklődés kiindulópontjaként használható;
legalább egy absztrakt metódust tartalmazó osztály kötelező minősítője
[final]: végleges osztály, metódusai nem módosíthatók, az öröklődés okafogyott
Az extends (leszármazott osztály létrehozása) és az implements (interfészek osztályhoz fűzése) kulcsszavak a későbbi fejezetek témáját képezik.
12.2. Adattagok
Egy objektum tulajdonságait (aktuális állapotát) az adattagjainak értékei reprezentálják. Egy adattagnak mindig van azonosítója (neve), valamint típusa, amely lehet primitív típus (pl. egész szám, string, logikai), vagy akár osztálytípus is. Az adattagok a típusuknak megfelelő értékek tárolására szolgálnak, de értéküket az objektum életciklusa során megváltoztathatják (kivéve a konstansokat).
Az adattagok lehetnek példányszintűek, azaz minden objektumpéldányban egyedileg létezők, valamint osztályszintűek, amelyek egy osztályon belül csak egyszer léteznek, és magához az osztályhoz kapcsolódnak. Utóbbi az adattag-definíciót bevezető static kulcsszóval deklarálható.
Egy példányszintű adattag mindig egy objektumhoz tartozik. Ha a deklarációs részben nem adunk kezdőértéket egy adattagnak, a Java automatikusan feltölti a típusának megfelelő "nullaszerű" kezdőértékkel: pl. boolean - false, számok - 0, char - nullás kódú karakter, osztály típusú adattagok - null referencia.
Az adattag neve lehet minden megengedett azonosító, amelyet szokás szerint kisbetűvel kezdünk. Két adattagnak nem lehet azonos neve egy osztályon belül.
Adattagok deklarációja:
[módosítók] <típus> <adattag_neve> [=<kezdőérték>][, ...];
Az adattagok deklarációja az osztálytörzsben, bármilyen konstruktor- ill. metódusdeklaráción kívül történik. A módosítók itt sem kizárólag hozzáférési szinteket takarhatnak, hanem más eszközöket is:
Adattag-deklarációs módosítók:
[hozzáférési szint]: public | protected | üres (csomagszintű) | private
[static]: osztályváltozó deklarálása
[final]: az adattag értéke végleges, konstans
Az alábbi példában definiálunk egy kezdőérték nélküli adattagokkal rendelkező Bankbetét nevű osztályt:
Lássuk ugyanezt az osztályt két kezdőértékadással rendelkező adattaggal definiálva:
A tömörebb kódok elérése miatt megengedett, hogy egy adattag-deklaráción belül több azonos típusú adattagot is megadjunk, megjelölve a típust, majd az egymástól vesszővel elválasztott neveket felsorolva:
A példaprogram forráskódja: Bankbetet.rar.
12.3. Inicializáló blokkok
Az osztály adattagjainak kezdőértékét osztály- ill. példány-inicializáló blokkban is beállíthatjuk. Az inicializáló blokkok speciális, fej nélküli metódusok, melyeket csak a blokk-képző kapcsos zárójelpárok határolnak, és return utasítást sem tartalmaznak. Az osztály-inicializáló blokkot a blokk előtti static kulcsszóval kell jelölni. Fontos tudni, hogy az inicializáló blokk csak egyszer fut le: típusától függően az osztály létrehozásakor, ill. a példányosítások alkalmával egyszer-egyszer példányonként.
12.4. Konstruktorok, példányosítás
Egy osztály példányosítása mindig valamelyik konstruktorának meghívásával történik. A konstruktor egy konkrét objektum életciklusa alatt pontosan egyszer fut le, létrehozva ezzel az objektumot, s beállítva az adattagjainak kezdeti értékét. A konstruktor lefutása után az objektum kész az üzenetek fogadására, feladatának elvégzésére.
A konstruktor neve kötött (mindig megegyezik az őt hordozó osztály nevével), így egy osztálynak csak akkor lehet több konstruktora (konstruktor túlterhelés), ha azok eltérő formális paraméterlistával rendelkeznek. A konstruktor egy speciális, típus nélküli metódusként fogható fel, amelynek nincs visszatérési értéke. Más megfogalmazásban a konstruktor egy - az osztály típusával visszatérő - névtelen metódus.
Egy osztályhoz mindig tartoznia kell legalább egy konstruktornak, hiszen nélküle az osztály nem példányosítható, vagyis nem hozhatók létre az osztály típusának megfelelő objektumpéldányok. Ha nem adunk meg konstruktort, akkor a Java fordító mindig létrehoz egy alapértelmezett, paraméter nélküli konstruktort. Ennek meghívása olyan példányt hoz létre, amelynek adattagjai "nullaszerű" értékekkel rendelkeznek: a numerikus típusok nulla, a karakteres típusok "null", a logikai típusok false értéket vesznek fel. Ha azonban készítünk valamilyen konstruktort, akkor a paraméter nélküli konstruktor "elvész". Így ha mégis szükségünk van rá, definiálnunk kell!
Csak olyan paraméterlistát adhatunk át egy konstruktornak, amelynek megfelelő konstruktort készítettünk, egyébként a fordító hibát jelez.
Konstruktor deklarációja:
[módosítók] <osztály_neve>([<típus> <adattag_neve>[, ...]]) {
[this.]<adattag_neve> = <adattag_neve>[, ...];
}
A metódusokhoz hasonlóan ha egy konstruktorban olyan változó- vagy paraméternevet alkalmazunk, amely egyben az osztály egy adattagjának is az azonosítója, akkor a this kulcsszóval minősítve hivatkozhatunk az adattagra, míg minősítés nélkül a változóra ill. a paraméterre. Figyelem! A this minősítő ezen alkalmazása nem tévesztendő össze a this() alakú konstruktorhívással!
Nézzük az alábbi konstruktorfajtákat!
Az első konstruktor a paraméterek alapján hozza létre az objektumpéldányt, a második esetben nincs paraméterátadás, mégis minden adattag kezdőértéket kap. Az ilyen üres paraméterlistájú konstruktorban a this minősítő felesleges az adattagok elé, mivel ilyenkor nincsenek őket eltakaró lokális nevek vagy paraméterek. A harmadik esetben csak egy paraméterrel hívunk meg egy újabb konstruktorfajtát, a többi paramétert maga a konstruktor állítja be a this([<aktuális paraméterlista>]) - osztályon belüli konstruktorhívást kezdeményező - kulcsszó használatával.
Egy konstruktor meghívása a new kulcsszóval történhet:
Példányosítás:
<osztály_neve> <objektumpéldány_neve>;
<objektumpéldány_neve> = new <osztály_neve>([aktuális paraméterlista]);
vagy
<osztály_neve> <objektumpéldány_neve> = new <osztály_neve>([aktuális paraméterlista]);
A háromféle konstruktor meghívásának módja:
Lássuk a konstruktorhívások eredményeképpen létrejövő objektumok adattagjainak tartalmát is (az osztály toString() metódusának megfelelő módosítása után):
Egy konstruktorból az osztály egy másik konstruktorát, ill. a közvetlen ősosztály egy konstruktorát a this() ill. a super() kulcsszó alkalmazásával érhetjük el.
12.5. Metódusok
Az osztályokhoz tartozó objektumok viselkedését (vagyis az objektumokhoz küldhető üzeneteket) az osztály definíciójában felsorolt metódusok határozzák meg. A metódus egy olyan programrutin, amely egy objektum egy konkrét feladatának algoritmusát valósítja meg.
A Java nyelvben a metódusoknak két nagy csoportját különböztethetjük meg a visszatérési értéküknek megfelelően. Az egyik a visszatérési értékkel nem rendelkező eljárások, míg a másik az ezzel rendelkező függvények csoportja. Függvények esetén meg kell adni a visszatérési érték típusát, míg a másik csoport esetén a void kulcsszó helyettesíti azt.
A metódusdefiníció általános szintaxisa a következő:
Metódus fej:
[módosítók] <típus> <metódus_neve>([formális paraméterlista]) [throws <kivételnévlista>]
Metódus törzs:
{
[lokális változó-deklarációk];
[utasítások];
[return[<kifejezés>]];
}
A metódus fejrészének módosítói nemcsak hozzáférési szinteket takarhatnak, hanem opcionálisan egyéb attribútumokat is:
Metódus-fejrész módosítók:
[hozzáférési szint]: public | protected | üres (csomagszintű) | private
[abstract]: öröklődés céljából készült, üres metódus: nincs metódusblokk (kapcsos zárójelpár),
kifejtésére egy leszármazott osztályban kerül sor, a metódusfejet pontosvessző zárja
[final]: végleges metódus, a leszármazott osztályokban a metódus nem módosítható
[static]: osztálymetódus, csak statikus osztályszintű adattagra és metódusra hivatkozhat
Ha a static kulcsszó nem szerepel a fejrész módosítói között, akkor példánymetódusról van szó, amely példánymetódus példányszintű adattagokra és más példánymetódusokra (összefoglaló néven példánytagokra), valamint nyilvános (public) osztálytagokra (azaz osztályszintű adattagokra és metódusokra) hivatkozhat.
A <típus> a metódus visszatérési értékének típusát határozza meg. Az eljárások visszatérési típusa void, a függvényeké pedig bármilyen primitív típus, vagy hivatkozási típus lehet.
A formális paraméterlistát egy típusokból és szintaktikailag lokális változónak minősülő adattagokból álló párosok alkotják. Egy metódushíváskor az aktuális- és a formális paraméterlisták elemeinek páronként meg kell egyezniük, azaz értékadás szerint kompatibilisnek és páronként megfelelő sorrendűeknek kell lenniük. A Java-ban csak érték szerinti paraméterátadás létezik.
A throws (kivételek továbbküldése) kulcsszó egy későbbi fejezet témája lesz.
Egy metódust a neve és a paraméterlistája azonosít egyértelműen, tehát egy osztályon belül megadható két azonos nevű metódus, ha azok paraméterlistája (szignatúrája) vagy a listában szereplő paraméterek típusaiban, vagy azok sorrendjében, esetleg mindkettőben eltérnek. Hivatkozáskor a futtató környezet a megadott paraméterek típusából és sorrendjéből el tudja dönteni, hogy a két azonos nevű metódus körül melyiket kell végrehajtania. Az így létrehozott szerkezetet a polimorfizmus egyik formájának tekinthetjük (metódusnevek túlterhelése - overload).
Ha egy metódusban olyan változó-, vagy paraméternevet alkalmazunk, amely egyben az osztály egy adattagjának is az azonosítója, akkor a this kulcsszóval minősítve hivatkozhatunk az adattagra, míg minősítés nélkül a változóra ill. a paraméterre.
A metódusok visszatérési értékének típusa a metódus deklarációjakor adható meg. A metóduson belül a return - feltétel nélküli vezérlésátadó - utasítással lehet a visszaadott értéket előállítani. A void-ként deklarált metódusok nem adnak vissza értéket, ezért return utasítást sem szükséges tartalmazniuk. Viszont minden olyan metódusnak, amely nem void-ként lett deklarálva, kötelezően tartalmaznia kell a return utasítást. Sőt, a Java fordító azt is kikényszeríti, hogy return utasítással végződjön minden lehetséges végrehajtási ág. A visszaadott érték adattípusának meg kell egyeznie a metódus deklarált visszatérési értékével. Ezért nem lehetséges pl. egész számot visszaadni olyan metódusból, amelynek visszatérési értéke logikai típusú.
Az alábbi két metódus egyike eljárás, amely eldönti, hogy pozitív összeg-e a bankbetét, a másik pedig egy függvény (a paraméterként kapott egész számmal megnöveli az adó mértékét):
A két metódus meghívása és futásuk eredménye:
Speciális metódus a main metódus, amelyet célszerű az osztályon belül utolsóként deklarálni. Egy alkalmazás végrehajtása során a Java futtatórendszere először mindig meghívja az alkalmazás valamelyik osztályának main metódusát, és ez a metódus fogja az összes többit meghívni.
public static void main(String[] args) {
}
A public módosító biztosítja, hogy a metódus a programon belül bárhonnan elérhető legyen, a static jelzi, hogy osztálymetódusról van szó, és a void kulcsszóból láthatjuk, hogy a metódusnak nincs visszatérési értéke. A main metódusnak egy string-tömb típusú paramétere van, amely a parancssori paramétereket tartalmazza.
12.6. Csomag
A csomag logikailag összefüggő osztály- és interfészdefiníciók gyűjteménye. Hierarchikus felépítésével rendszerezhetjük típusainknak, külön névtereket létrehozva számukra. A csomag elnevezése a package <csomagnév> utasítás segítségével történhet, amelyet a fordítási egység legelső sora kell, hogy legyen.
Ha olyan osztályokat is szeretnénk sokszor használni, amelyek más csomagokban vannak, akkor azokat (az állandó csomagnév hivatkozást elkerülendő) importálni érdemes. Formái:
teljes csomag: import <csomagnév>.*;
csomagon belüli csomag: import <csomagnév>.<belső_csomagnév>.*;
csomag egy osztálya: import <csomagnév>.<Osztálynév>;
Az importáló utasítások kötelezően a csomagdeklarációs sor után következnek. Egy utasításban csak egy osztály (vagy a .*-gal egy teljes csomag) importálható. A Java fordító minden csomaghoz automatikusan hozzáfordítja az alapvető osztályokat (pl. System, String) tartalmazó java.lang csomagot, így ezt nem szükséges külön importálni. Az importálás művelete nem rekurzív, tehát egy teljes csomag importálásakor nem lesznek elérhetők az alcsomagok osztályainak definíciói.
Megadhatunk egy osztályt egy másik osztály tagjaként. Egy ilyen osztályt beágyazott osztálynak hívunk, és a következőképpen néz ki:
class EnclosingClass {
...
class ANestedClass {
...
}
}
A beágyazott osztályokat arra használjuk, hogy kifejezzük és érvényesítsük két osztály között a kapcsolatot. Megadhatunk egy osztályt egy másik osztályon belül, hogyha a beágyazott osztálynak a magába foglaló osztályon belüli környezetben van értelme. Pl. a szövegkurzornak csak a szövegkomponensen belüli környezetben van értelme.
A beágyazó osztály tagjaként a beágyazott osztály kiváltságos helyzetben van. Korlátlan hozzáféréssel rendelkezik a beágyazó osztályok tagjaihoz még akkor is, hogy ha azok privátként vannak deklarálva. Azonban ez a speciális kiváltság nem mindig speciális. A hozzáférést biztosító tagok korlátozzák a hozzáféréseket az olyan osztálytagokhoz, amelyek a beágyazó osztályon kívül esnek. A beágyazott osztály a beágyazó osztályon belül található, ebből kifolyólag hozzáférhet a beágyazó osztály tagjaihoz.
Mint ahogyan más tagokat is, a beágyazott osztályokat is statikusként, avagy nem statikusként lehet deklarálni, ezért ezeket pontosan így is hívják: statikus beágyazott osztály. A nem statikus beágyazott osztályokat belső osztályoknak hívjuk.
class EnclosingClass {
...
static class StaticNestedClass {
...
}
class InnerClass {
...
}
}
Ahogy a statikus metódusok és változók esetén, amelyeket mi osztálymetódusoknak és változóknak hívunk, a statikus beágyazott osztályt a beágyazó osztályával kapcsoljuk össze. Ahogy az osztálymetódusok, a statikus beágyazott osztályok sem hivatkozhatnak közvetlenül olyan példányváltozókra vagy metódusokra, amely az ő beágyazó osztályában van megadva. A példánymetódusok és változók esetén egy belső osztály az ő beágyazó osztályának a példányával kapcsolódik össze, és közvetlen hozzáférése van annak az objektumnak a példányváltozóihoz és metódusaihoz. Mivel egy belső osztályt egy példánnyal társítanak, ezért önmaga nem definiálhat akármilyen statikus tagot.
Hogy a továbbiakban könnyebb legyen megkülönböztetni a beágyazott osztály és a belső osztály fogalmát, érdemes ezekre a következőféleképpen tekinteni: a beágyazott osztály két osztály közötti szintaktikus kapcsolatot fejez ki, azaz szintaktikailag az egyik osztályban levő kód megtalálható a másikon belül. Ezzel ellentétben a belső osztály olyan objektumok közötti kapcsolatot fejez ki, amelyek két osztálynak a példányai. Tekintsük a következő osztályokat:
class EnclosingClass {
...
class InnerClass {
...
}
}
Az e két osztály közötti kapcsolatnál nem az az érdekes, hogy az InnerClass szintaktikusan definiálva van az EnclosingClass-on belül, hanem az, hogy az InnerClass-nak a példánya csak az EnclosingClass-nak a példáján belül létezhet, és közvetlen hozzáférése van a példányváltozók és a beágyazó osztály példánymetódusaihoz.
A beágyazott osztályok mindkét fajtájával találkozhatunk a Java API-n belül, és kell is használni őket. Azonban a legtöbb beágyazott osztály, amelyeket használunk, valószínűleg belső osztály lesz.
Lássunk egy példát
Készítsünk saját osztályt
Ember osztály az adattárolásra és rövidítésre:
package tarsalgo;
public class Ember
{
private int ora;
private int perc;
private int azon;
private String irany;
private boolean be;
public Ember( String[] tomb )
{
ora = Integer.parseInt(tomb[0]);
perc = Integer.parseInt(tomb[1]);
azon = Integer.parseInt(tomb[2]);
irany = tomb[3];
be = tomb[3].equals("be");
}
public int getOra()
{
return ora;
}
public int getPerc()
{
return perc;
}
public int getAzon()
{
return azon;
}
public String getIrany()
{
return irany;
}
public boolean isBe()
{
return be;
}
@Override
public String toString()
{
return "Ember{" + "ora=" + ora + ", perc=" + perc +
", azon=" + azon + ", irany=" + irany + ", be=" + be + '}';
}
}
A main()-t tartalmazó osztály, mely a fájlkezelést és a feladatokat tartalmazza:
package tarsalgo;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Scanner;
public class Tarsalgo
{
public static void main(String[] args)
{
// 1. feladat
Ember[] emberek = null;
try
{
RandomAccessFile raf = new RandomAccessFile("ajto.txt","r");
String sor;
int db = 0;
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
db++;
}
emberek = new Ember[db];
raf.seek(0);
db = 0;
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
emberek[db] = new Ember(sor.split(" "));
db++;
}
raf.close();
}
catch( IOException e )
{
System.out.println("HIBA");
}
// for( Ember e : emberek )
// {
// System.out.println(e);
// }
// 2. feladat
System.out.println("2. feladat");
System.out.println("Az elso belepo: "+emberek[0].getAzon());
int hely = -1;
for( int i = emberek.length-1; i >= 0; i-- )
{
if( !emberek[i].isBe() )
{
hely = i;
}
}
if( hely != -1 )
{
System.out.println("Az utolso kilepo: "+emberek[hely].getAzon());
}
else
{
System.out.println("Senki nem ment ki a tarsalgobol.");
}
// 3. feladat
int max = 0;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() > max )
{
max = emberek[i].getAzon();
}
}
int[] darabok = new int[max+1];
for( int i = 0; i < emberek.length; i++ )
{
darabok[emberek[i].getAzon()]++;
}
try
{
RandomAccessFile ki = new RandomAccessFile("athaladas.txt","rw");
for( int i = 1; i < darabok.length; i++ )
{
ki.writeBytes(i+" "+darabok[i]+"\n");
}
ki.close();
}
catch( IOException e )
{
System.out.println("HIBA");
}
// 4. feladat
System.out.println("4. feladat");
int[] bent = new int[max+1];
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].isBe() )
{
bent[emberek[i].getAzon()]++;
}
else
{
bent[emberek[i].getAzon()]--;
}
}
System.out.print("A vegen a tarsalgoban voltak: ");
for( int i = 1; i < bent.length; i++ )
{
if( bent[i] > 0 )
{
System.out.print(i+" ");
}
}
System.out.println();
// 5. feladat
System.out.println("5. feladat");
int[] bentvannak = new int[emberek.length];
int elozo = 0;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].isBe() )
{
bentvannak[i] = elozo + 1;
}
else
{
bentvannak[i] = elozo - 1;
}
elozo = bentvannak[i];
}
max = 0;
for( int i = 1; i < bentvannak.length; i++ )
{
if( bentvannak[i] > bentvannak[max] )
{
max = i;
}
}
System.out.println("Peldaul: "+emberek[max].getOra()+":"+
emberek[max].getPerc()+"-kor voltak a legtobben a tarsalgoban.");
// 6. feladat
System.out.println("6. feladat");
System.out.print("Adja meg egy szemely azonositojat: ");
Scanner sc = new Scanner(System.in);
int azon = Integer.parseInt(sc.nextLine());
// 7. feladat
System.out.println("7. feladat");
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() == azon )
{
if( emberek[i].isBe() )
{
System.out.print(emberek[i].getOra()+":"+
emberek[i].getPerc()+"-");
}
else
{
System.out.println(emberek[i].getOra()+":"+
emberek[i].getPerc());
}
}
}
System.out.println();
// 8. feladat
System.out.println("8. feladat");
int osszeg = 0;
int be = 0;
int ki = 0;
boolean bentvan = false;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() == azon )
{
if( emberek[i].isBe() )
{
be = emberek[i].getOra()*60+emberek[i].getPerc();
bentvan = true;
}
else
{
osszeg += (emberek[i].getOra()*60+emberek[i].getPerc()) - be;
bentvan = false;
}
}
}
// ha a legvegen nem jott ki, akkor az utolso bemenetel
// es a 15:00 kozotti idot hozzaadjuk az ossz idejehez
if( bentvan )
{
osszeg += (15*60)-be;
}
System.out.print("A(z) "+azon+". szemely osszesen "+osszeg+
" percet volt bent");
if( bentvan )
{
System.out.println(", a megfigyeles vegen a tarsalgoban volt.");
}
else
{
System.out.println(".");
}
}
}
Megszámlálásra példa
Az alap feladatot a fenti linken megtalálod, az ott bemeneti adatokat fogom használni.
A feladatot két osztály írásával oldom meg. Először kell egy Hivas osztály, amely a beolvasott adatokat tárolja, és azokból különféle tulajdonságokat számít ki. A tulajdonságokból az óra és másodperc tárolását kihagytam, ennek a feladatnak nincs rá szüksége. Természetesen ha híváshossz vagy valami más számított adatra lenne szükség, akkor azokat is tárolnám a megfelelő helyen.
/**
*
* @author http://webotlet.hu
*/
package webotlet_kombinaltmegszamlalas;
public class Hivas
{
private String szam;
private String ido;
private int ora;
private boolean csucs;
private boolean mobil;
public Hivas(String[] tomb)
{
szam = tomb[0].substring(3);
ido = tomb[1];
ora = Integer.parseInt(ido.split(":")[0]);
csucs = ora >= 8 && ora < 18;
mobil = szam.startsWith("21") || szam.startsWith("31") ||
szam.startsWith("71");
}
public int getOra()
{
return ora;
}
public boolean isCsucs()
{
return csucs;
}
public boolean isMobil()
{
return mobil;
}
}
Akkor jöjjön az osztály, mely a fájlkezelést végzi, megszámolja a megfelelő tulajdonságú objektumokat és kiírja a végeredményt:
/**
*
* @author http://webotlet.hu
*/
package webotlet_kombinaltmegszamlalas;
import java.io.*;
import java.util.ArrayList;
public class Webotlet_KombinaltMegszamlalas
{
public static void main(String[] args)
{
ArrayList<Hivas> hivasok = new ArrayList<>();
String sor;
RandomAccessFile raf;
try
{
raf = new RandomAccessFile( "kombihivasok.csv","r");
raf.readLine();
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
hivasok.add( new Hivas( sor.split(";") ) );
}
raf.close();
// ora: cs, ncs, m, v
// cs - csucsido, ncs - nem csucsido, m - mobil, v - vezetekes
int[][] db = new int[24][4];
int ora;
for( Hivas h : hivasok )
{
ora = h.getOra();
// csucsideju, nem csucsideju
if( h.isCsucs() ) db[ora][0]++;
else db[ora][1]++;
// mobil, vezetekes
if( h.isMobil() ) db[ora][2]++;
else db[ora][3]++;
}
for( int i = 0; i < db.length; i++ )
{
System.out.println( i+". ora: "+db[i][0]+", "+db[i][1]+
", "+db[i][2]+", "+db[i][3] );
}
}
catch( IOException e )
{
System.err.println("HIBA");
}
}
}
----------------
Alap algoritmusok, avagy mindenki tud programozni
A programozással sokszor az a baj – főleg ha kötelező tantárgy és nem szeretjük – hogy gondolkodni kell. Igaz, mondhatnám ezt a matematikára, fizikára is, de egyik tantárgy sem annyira szerteágazó a helyes megoldások tekintetében, mint a programozás. Itt ugyanazt a problémát sokféleképp meg lehet oldani, és minden megoldás helyes. Mégis, a megoldások között az árnyalatnyi különbségek azok, amelyek eldöntik azt, hogy helyes-e a megoldás, vagy sem.
Bármilyen bonyolult programot veszünk szemügyre és bontunk részekre, a végén ugyanaz a 4 építőelem marad:
szekvencia (utasítások egymás utáni sorozatának végrehajtása)
változóhasználat
elágazások
ciklusok
A sorrend nem véletlen, ebben a sorrendben kell ezeket megtanulni használni, mert ezek egymásra épülő darabok a programozásnak nevezett kirakó játékban. Ha nem az építőelemeit nézzük a programoknak, akkor is találhatunk olyan sablonokat, olyan már tanult megoldásokat, amelyek újra és újra előfordulnak a programjainkban. Ezeket a sablonokat, kész megoldásokat nevezzük programozási tételeknek.
Ezek valójában betanulható kész algoritmusok, melyek egy adott problémára kész megoldást adnak. Nem mindig fordulnak elő tiszta formában, vagyis néha apró változtatásokra szükség van, hogy ezeket az algoritmusokat egy adott feladathoz igazítsuk, de ha ezeket ismerjük és biztosan használjuk, akkor sokféle programozási feladatot meg tudunk oldani.
Ezek az alap algoritmusok tömbökhöz kapcsolódnak, vagyis sok egyforma adattal végeznek valamit. Megkeresik egy tömbből a legnagyobb értéket, sorba rendezik a számokat, eldöntik, hogy benne van-e egy adott érték a tömbben, megadják két halmaz metszetét, stb. Lássunk akkor néhány alap algoritmust:
Megszámlálás
Összegzés
Eldöntés
Kiválasztás
Keresés
Minimum/maximum keresés
Rendezés
Kiválogatás
Szétválogatás
Metszet
Unió (hiányzik)
Ezen algoritmusok mindegyikére igaz, hogy ciklusokhoz kapcsolódnak, hiszen ha tömbökkel dolgozunk, akkor mindenképpen ciklusra van szükség, hogy az elemeket egyenként megvizsgálhassuk, összehasonlíthassuk, stb. Ezek az algoritmusok kicsit leegyszerűsítik a programozást, hiszen ezekkel a megtanulható kész receptekkel sokféle feladatot megoldhatunk. A probléma az, hogy a feladatban fel kell ismerni, hogy valójában mit is akarunk eredményként megkapni, és az melyik algoritmusnak felel meg. Ha ez megvan, onnantól szinte csak gépelési feladattá sikerült egyszerűsíteni a programozási feladatot.
Az alap algoritmusok valamennyi fajtájához létezik pszeudokód, olyan általános leírás, amely programozási nyelvtől független. Ráadásul, mivel 3 fajta ciklus létezik, ezért alapból szerteágazó megoldásokat adhatunk ugyanarra a feladatra. Az alap algoritmusokat nagyon sok helyen ugyanazzal a megoldási formával adják meg, és biztos vagyok benne, hogy több tanár csak így fogadja el megoldásként. Én azt vallom, hogy bármilyen jó megoldás elfogadható, a lényeg, hogy a diák alkalmazni tudja azt, amit tanult. Léteznek lecsupaszított, hatékony és egyszerű megoldások, de sokszor én sem azt alkalmazom, mert nem írunk olyan szintű programokat, hogy ennyire optimalizált és gyors algoritmusra lenne szükség. Aki esetleg az alap algoritmusaimban hibát talál, mondván, hogy ő ezt nem így tanulta, az nem feltétlenül hiba, egyszerűen más a megoldás. Az példáknál sok helyen kész ténynek veszem azt, hogy rendelkezésre áll az a tömb a megfelelő adatokkal, amelyekkel dolgozni kell. Ezeknek a tömböknek a feltöltésével, ellenőrzésével nem foglalkozok. Vegyük akkor sorra ezeket az algoritmusokat:
Megszámlálás
Kezdjük valami egyszerűvel. Az alapfeladat az, hogy számoljuk meg, hogy egy adott tömbben hány darab adott tulajdonságú elem van. Ez jelentheti azt is, hogy nincs ilyen tulajdonságú elem a tömbben, akkor a darabszám nyilván 0. Ennél a feladatnál minden esetben végig kell menni a tömbön, hiszen minden elemről meg kell állapítanom, hogy rendelkezik-e a tulajdonsággal, vagy sem. Mivel megszámolunk, ezért valahol tárolnom kell, hogy éppen hol járok a számolásban, hány olyat találtam, ami megfelelt a feltételemnek. Ehhez szükség van egy úgynevezett gyűjtőváltozóra. Az adott algoritmus egy darabszámot ad eredményül minden esetben, ami a [0;méret] intervallumban lesz, vagyis lehet, hogy egy elem sem felel meg a feltételnek, de az is előfordulhat, hogy mindegyik. Nézzünk pár példát, hogy mikor alkalmazható ez az algoritmus:
Hány 180 cm-nél magasabb diák jár az osztályba?
Hány napon esett az eső tavaly?
Hány férfi tanár tanít az iskolában?
Láthatjuk, hogy minden esetben egy darabszámra kíváncsi minden kérdés. Lássuk akkor azt az algoritmust, ami ezekre a kérdésekre választ ad. A példában az első kérdésre keressük a választ.
int szamlalo = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] > 180 )
{
szamlalo = szamlalo + 1;
}
}
System.out.println("Az osztalyba "+szamlalo+" db 180 cm-nel "
"magasabb diak jar.");
Nézzük akkor részletesebben, mi történik.
Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek darabszámát tároljuk.
A gyűjtőváltozót 0 kezdőértékre állítjuk be. Ez egyébként általános szabály, hogy minden gyűjtőváltozót legkésőbb a használata előtt (a ciklus előtt) nullázni kell!
Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
Ha megfelel, a számlálót eggyel megnöveljük.
A ciklus után kiírjuk az eredményt.
A kiemelt sorban a változó növelését kicserélhetjük a már tanult inkrementáló operátorra. Azért, mert lusták vagyunk, és nem akarunk sokat gépelni 🙂
szamlalo = szamlalo + 1;
helyett
szamlalo++;
A többi feladatnál gyakorlatilag ugyanezt kell begépelni, igazából az egyetlen dolog ami változik az maga a feltétel, ami alapján megszámolunk.
Összegzés
Az összegzés tétele kísértetiesen hasonlít a megszámlálásra. Egyetlen különbség van csak, a gyűjtőváltozó növelése. A feladatok is hasonlóak, de az összegzés csak számszerű adatokra vonatkozik. Néhány példa ilyen kérdésekre:
Mennyi a tömbben található páros számok összege?
Mennyi a negatív számok összege?
Mennyi a páratlan számok átlaga?
Lássuk akkor mondjuk az első megoldását:
int osszeg = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
osszeg = osszeg + tomb[i];
}
}
System.out.println("A tombben levo paros szamok osszege: "+osszeg);
Láthatjuk, hogy az összegzés algoritmusa szinte ugyanaz, mint a megszámlálásé.
Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek összegét tároljuk.
A gyűjtőváltozót 0 kezdőértékre állítjuk be.
Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
Ha megfelel, az összeghez hozzáadjuk az aktuális elemet.
A ciklus után kiírjuk az eredményt.
A lényegi különbséget kiemeltem. Látható, hogy szinte ugyanaz. Ettől függetlenül ne keverjük a két algoritmust, mert teljesen más a feladatuk!
A kiemelt sorban a változó növelését kicserélhetjük már tanult összeadással kombinált értékadó operátorra. Ismét csak azért, mert lusták vagyunk, és nem akarunk sokat gépelni.
osszeg = osszeg + tomb[i];
helyett
osszeg += tomb[i];
A harmadik feladat kilóg a többi közül, ez nem csak tiszta összegzés. Itt egyszerre kell az előzőleg ismertetett megszámlálást és összegzést elvégezni. Szükségünk van a páratlan számok összegére, valamint a darabszámára is az átlagoláshoz:
int osszeg = 0;
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
osszeg = osszeg + tomb[i];
db++;
}
}
double atlag = (double)osszeg/db;
System.out.println("A tomb paratlan szamainak atlaga: "+atlag );
Láthatjuk, hogy a ciklussal ugyanúgy végigmegyünk az egész tömbön. Ha találunk egy megfelelő számot, akkor hozzáadjuk az összeghez és növeljük a darabszámot is. Az átlag már csak egy osztás. De nem egyszerű osztás. Az osszeg és db változók egész típusok. Mi lenne az eredménye annak, ha mondjuk az összeg 11 a darabszám pedig 5? 11/5 = ?
Ne felejtsd el! Ha két egész számot osztunk egymással, az egész osztás! Az eredmény nem a sokszor várt 2,2 lenne, hanem 2,0. Az osztás akkor nem egész osztás, ha legalább az egyik műveletben részt vevő szám nem egész. Előzőleg már mutattam egy trükköt, írhatnánk így is:
osszeg/(db+0.0)
Helyette azonban legyünk elegánsabbak, használjunk típuskényszerítést, amit a véletlen számok témakörben már bemutattam:
(double)osszeg/db
A típuskényszerítés során az összeg változóból kiolvasott értéket lebegőpontos számmá alakítjuk, majd osztjuk egy egésszel. Ennek eredménye már megfelelő: 2,2.
Fontos, hogy ez a típuskényszerítés nem az eredeti összegváltozóban tárolt értéket változtatja meg, nincs értékadás! Nem is változtathatja meg az összegváltozó tartalmát, mivel annak típusa egész. Csak a változóból felhasznált értéket alakítja át a megadott típusra.
Eldöntés
Ennél a feladattípusnál azt vizsgáljuk, hogy egy tömbben található-e egy bizonyos tulajdonságú elem. Nem érdekel, hogy hány ilyen elem van, csak az a fontos, hogy van-e benne ilyen. Itt logikai eredményt kapunk, vagyis a válasz igaz vagy hamis lehet. Lássunk pár példát olyan kérdésekre, amelyekre ezzel az algoritmussal kaphatunk választ:
Van-e az osztályban lány?
Van-e az osztályban 190 cm-nél magasabb diák?
Volt-e melegebb 38 foknál tavaly nyáron?
Van-e 30 évnél fiatalabb tanár az iskolában?
Ezekhez a feladatokhoz természetesen szükség van tömbökre, melyek azokat az adatokat tárolják, amelyek között keressük azt a bizonyos tulajdonságú elemet, azok közül is a legelsőt. Emlékezz, nem érdekel hány ilyen elem van, csak az számít, hogy van-e ilyen, és ez nyilván a legelső megtalált elem lesz. Az első példához szükség van egy tömbre, amely a tanulók nemét tárolja, akár logikai típusként (lány – true, fiú – false). A második esetben kell egy tömb, ami az osztályba járó diákok magasságait tartalmazza, a harmadikban egy tömb, ami a nyári napok maximum hőmérsékletét tartalmazza, a negyediknél egy tömb, amiben benne van az iskolában tanító tanárok életkora. Maradjunk a második példánál, és vegyük úgy, hogy rendelkezésre áll egy „tomb” nevű tömb, ami az osztályba járó diákok magasságait rögzíti.
int i = 0;
while( i < tomb.length && tomb[i] <= 190 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("Van az osztalyban 190 cm-nel magasabb diak.");
}
Na de mit is csinál ez pontosan?
Először deklarálunk egy ciklusváltozót, amit arra fogunk használni, hogy indexelhessük (hivatkozhassunk) az egyes tömbelemekre, jelen esetben a diákok magassági adataira. Ez a sorszám természetesen 0-tól indul, mert a Java nyelvben a tömbök indexei 0 számmal kezdődnek.
Aztán indítunk egy ciklust, melynek az a feladata, hogy végigmehessünk egyenként a tömb elemein. A ciklus feje viszont egy összetett feltételt tartalmaz. Ennek első fele azt vizsgálja, hogy végigértünk-e már a tömbön – vagyis, hogy az index kisebb-e, mint a tömb mérete. Ha az i egyenlő lenne a tömbmérettel, az már azt jelentené, hogy túljutottunk az utolsó elemen, tehát a ciklus megáll. Mivel a tömbök indexe 0-val kezdődik, ebből következik, hogy az utolsó elem indexe tömbméret-1. A feltétel másik része a tulajdonság vizsgálat, amelyre csak akkor kerül sor, ha még nem értünk a tömb végére. Itt azt vizsgáljuk, hogy a tomb[i] – vagyis az aktuális diák magassága – NEM RENDELKEZIK a keresett tulajdonsággal. Ez fura, mert nem pont ennek a fordítottját keressük? De igen, ez az algoritmus lényege. Addig kell keresni, amíg NEM találtuk meg, amit kerestünk, hiszen ha megvan, akkor megállhatunk. Ha ez a két feltétel egyszerre igaz (nem értünk még a tömb végére ÉS nem rendelkezik az aktuális diák a keresett tulajdonsággal), akkor lépünk be a ciklusba, ami semmi mást nem csinál, csak lépteti a számlálót, vagyis jöhet a következő vizsgálandó diák. Az algoritmus nagyon fontos része az, hogy a ciklus két feltételének sorrendje kötött! Először kell azt vizsgálni, hogy nem értünk-e a végére, és ha nem, csak akkor szabad megvizsgálni, hogy az aktuális elem nem rendelkezik-e a keresett tulajdonsággal. Hiszen ha már végignéztük a tömböt, akkor már nincs mit vizsgálni.
A ciklus befejeződése után már csak értelmeznünk kell a kapott eredményt. Az i változó értéke az, ami a megoldást tartalmazza. Ha találtunk olyan diákot, aki rendelkezett a keresett tulajdonsággal, akkor a ciklus idő előtt megállt, vagyis az i értéke kisebb, mint a tömb mérete. Ha egyetlen diák sem volt 190 cm-nél magasabb, akkor a ciklus azért állt meg, mert az i változó már nem kisebb a tömb méreténél (vagyis egyenlő), tehát nem találtunk olyat, aki a feltételnek megfelelt volna
Természetesen a többi feladatra is hasonló a megoldás, lássuk mondjuk a negyedik feladatot:
int i = 0;
while( i < tomb.length && tomb[i] >= 30 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("Van az iskolaban 30 evnel fiatalabb tanar.");
}
Nagyon fontos eleme tehát az eldöntésnek, hogy második részfeltételnek azt adjuk meg, hogy az aktuális elem a keresett tulajdonsággal nem rendelkezik! Mivel a feltételek többsége relációt tartalmaz, itt a relációk ellentettjét kell használni!
// 30 évnél fiatalabbat keresünk
while( ... && tomb[i] < 30 )
helyett
// 30 évnél nem fiatalabb kell a feltételbe
while( ... && tomb[i] >= 30 )
Írhatnám úgy is, hogy valóban tagadom az eredeti állítást:
// 30 évnél nem fiatalabb
while( ... && !(tomb[i] < 30)
Az eredeti állítás valódi tagadását tomb[i] < 30 -> !( tomb[i] < 30) én inkább a reláció ellentettjével helyettesíteném, mivel ott egy reláció marad csak, így csak egy műveletet kell végrehajtani. Valódi tagadás esetén ott marad az eredeti reláció, majd a reláció logikai értékének tagadása is kell, ami két művelet, de ezekből az egyik megspórolható. Itt visszautalnék a relációs operátoroknál arra a táblázatra, ahol ismertettem a relációk tagadásait. Ne feledd: a kisebb tagadása nem a nagyobb!
Mi az, amit még észrevehettél ebben az algoritmusban? Ezzel vissza is kanyarodtunk egy nagyon fontos részhez, a logikai kifejezéseknél. Láthatod, hogy a while ciklus fejében egy összetett kifejezés szerepel. Ennek az első fele az, hogy elértünk-e már a tömb végéig, a második pedig az, hogy az aktuális elem nem rendelkezik a keresett tulajdonsággal. Látható, hogy a második feltétel kész tényként veszi azt, hogy ott csak valódi elemet vizsgálhatok. Egy tömbnek, ha emlékszel, fix tulajdonsága a mérete. Vagyis csak akkora indexet lehet használni, amilyen elem még szerepel a tömbben. Egy 10 elemű tömbben nem lehet pl a tomb[12] elemre hivatkozni, mert ilyen elem nem létezik.
Ez futási hibát eredményez. Na de itt hol ellenőrzöm azt, hogy nehogy túl nagy indexet használjak? Az első feltételben. Ez egy logikai rövidzár. Ha az első részfeltétel, hogy az i számláló kisebb, mint a tömbméret (vagyis az i lehet a tömb egy indexe) teljesül, csak akkor vizsgálja meg a második részfeltételt, az adott elem keresett tulajdonságának hiányát. Ha az i elérte a tömbméretet (vagyis nem kisebb), akkor a logikai rövidzár miatt a második feltételt logikai és esetén már meg sem vizsgálja. Nem fog olyan elemet vizsgálni, ami nem létezik! Nagyon fontos eleme az algoritmusnak az, hogy a két részfeltételnek pontosan ilyen sorrendben kell szerepelnie, mert így oldja meg a rövidzár azt az ellenőrzést is, hogy csak valódi emelet vizsgáljunk meg, és ne kapjunk futási hibát.
Kiválasztás
Ezzel az algoritmussal azt adhatjuk meg, hogy egy adott elem pontosan hol szerepel a tömbben. Ez természetesen az adott elem indexét jelenti, amellyel a tömbben hivatkozunk rá. Ez az algoritmus feltételezi azt, hogy az elem tényleg benne van a tömbben, ez ugyanis nem keverendő össze a keresés algoritmusával, amit következőként fogok ismertetni. Lássunk erre egy pár kérdést.
Válasszuk ki a tömbből az 50-es számot (nem index, hanem érték!).
Hányadik a sorban az a diák, akinek a magassága 190 cm-nél nagyobb.
Lássuk az első példa megoldását:
int i = 0;
while( tomb[i] != 50 )
{
i++;
}
System.out.println("Az 50-es szám indexe: "+i);
Ha megnézzük, ez egy lecsupaszított eldöntés algoritmusnak tűnik, amikor ciklusban működési feltételként furcsa módon azt adjuk meg, hogy a ciklus addig menjen, amíg az aktuális elem NEM rendelkezik a tulajdonsággal. Vagyis addig megyünk, amíg meg nem találjuk. Hiányzik viszont a eldöntéses algoritmus összetett feltételének első része, ami azt vizsgálja, hogy túlszaladtunk-e a tömb végén. Itt erre nincs is szükség, mivel abból indultunk ki, hogy a kiválasztandó elem biztosan benne van a tömbben.
Kiválasztásnál lehetséges, hogy több elem is megfelel a feltételnek, ez az algoritmus a legelső olyan elemet választja ki, akire a feltételünk igaz lesz. Viszonylag könnyen megoldható az is, hogy a legutolsó olyat válasszuk ki, ez csak a ciklus haladási irányától és az i kezdőértékétől függ.
Keresés
A keresés algoritmusa gyakorlatilag szinte ugyanaz, mint az eldöntés algoritmusa, mindössze az i változó ciklus utáni értelmezésénél van különbség. Azért szerepeljen itt újra az algoritmus egy konkrét példával. A feladatban azt keressük, hogy van-e 190 cm-nél magasabb diák és hogy ő hányadik a tömbben:
int i = 0;
while( i < tomb.length && tomb[i] <= 190 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("A 190 cm-nél magasabb diák helye: "+i);
}
else
{
System.out.println("Nincs ilyen diák.");
}
Látható az, hogy ez biztonságosabb algoritmus az előzőnél. Ez akkor is használható, ha nem tudjuk, hogy egyáltalán létezik-e ilyen diák, ezért eggyel több a feltétel is, mert azt is figyelni kell, hogy a tömb végén ne szaladjunk túl. A ciklus után pedig az i értékéből határozhatjuk meg a keresett elem helyét, ha ugyanis az i kisebb a tömb méreténél (vagyis nem szaladtunk túl rajta, tehát benne van), akkor az i már a keresett elem helyét jelenti. Ha nem így van, akkor nincs benne. Itt is logikai rövidzárat használunk, tehát a két feltétel sorrendje nagyon fontos. Az első feltétel biztosítja azt, hogy a második nem lehet hibás. Keresési algoritmusból többféle létezik, ez csak a legegyszerűbb lineáris keresés algoritmusa.
Minimum/maximum keresés
Nagyon gyakori feladat az, amikor egy tömbből meg kell határozni a legkisebb/legnagyobb elemet. Ez nem csak egyszerű típusoknál használható, akár objektumok (több tulajdonsággal rendelkező adattárolók) közül is kiválaszthatjuk a legkisebb/legnagyobb tulajdonságút. Technikailag az, hogy a minimum vagy maximum értéket keressük csak egy reláció megfordítását jelenti. Nézzük akkor hogy néz ki ez az algoritmus. Keressük meg a tomb nevű tömbben a legnagyobb értéket!
int max = 0;
for( int i = 1; i < tomb.length; i++ )
{
if( tomb[i] > tomb[max] ) max = i;
}
System.out.println("A tombben levo legnagyobb szam: "+tomb[max]);
Nézzük akkor részenként a programot. Először is deklarálunk egy max nevű változót, amelynek azonnal adunk is egy 0 kezdőértéket. Fontos, hogy ez nem egy változó nullázás, mint a megszámlálás vagy összegzés algoritmusánál tettük. Ennek a 0 értéknek jelentése van. Azt jelenti, hogy a legnagyobb elem a legelső, vagyis a 0 indexű! A max változóban tehát nem a legnagyobb elem értékét, hanem a helyét (indexét) tároljuk. Mindjárt világos lesz, miért. Azt mondjuk tehát, hogy a legnagyobb elem a 0. helyen van, vagyis ez az első elem. Ez teljesen egyértelmű, hiszen amíg meg nem vizsgálom a tömböt, az első elem tekinthető a legnagyobbnak, mivel a többit még nem ismerem. A ciklust, amivel végigmegyek az egész tömbön természetesen a 2. elemtől indul (indexe 1) és a tömbméret-1 indexű az utolsó, amit vizsgálnom kell. Ha az éppen vizsgált elem (tomb[i]) nagyobb, mint az eddigi legnagyobb tomb[max], akkor az új maximum helye megváltozik az aktuálisra -> max = i.
Fura lehet, hogy miért a legnagyobb elem helyét tároljuk és nem az értékét. Mi van akkor, ha ez a kérdés: Hányadik elem a legnagyobb a tömbben? Ha a maximumban a legnagyobb elem értékét tárolnánk, azzal a helyét nem tudjuk megmondani, csak az értékét. A helyéből viszont meghatározhatjuk mindkettőt.
Ha a legkisebb elemet keressük, akkor a kiemelt sorban fordul meg a relációs jel, és máris a legkisebb elemet kapjuk meg a végén. Természetesen minimum keresésnél célszerű a max változó nevét min-re változtatni, hogy utaljon arra, mit is keresek.
Ne felejtsd el tehát, minimum és maximum keresésnél a helyet tároló változó kezdőértéke 0, mivel az első elem lesz először a legkisebb vagy legnagyobb, ha elkezdem a keresést.
Más oka is van annak, hogy a helyet és nem az értéket tároljuk. Tételezzük fel, hogy csak negatív számokat tartalmaz a tömbünk és a legnagyobbat keressük közülük. Létrehozunk egy max változót, azt nullázzuk, de ez most a legnagyobb elem értékét jelentené. Találhatunk negatív számok között olyat, ami nagyobb, mint 0? Könnyen belátható, hogy csak pozitív számokat tartalmaz a tömb és a legkisebbet keressük, akkor sem állja meg a helyét a nullázás. A nulla nem pozitív, tehát nem találsz ettől kisebb pozitív számot, vagyis a tömb egyik eleme sem kerülhet a helyére.
Rendezés
Nagyon gyakori a programjainkban az a típusfeladat, hogy sorba kell rendezni egy tömb elemeit. A Java nyelvben az egyszerű típusokra, és a Stringekre is létezik beépített rendezés, mégis ritkán használjuk őket, mert javarészt objektumokkal fogunk dolgozni, azokra pedig ezek nem működnek. Rendezési algoritmusból nagyon sokféle létezik, vannak egyszerűbb, de lassabb típusok, és vannak nagyon hatékonyak. A valódi helyzet az, hogy a rendezendő adatoktól mennyiségétől is függ az, hogy melyik rendezési algoritmus a hatékony, de középiskolai szinten mindegy hogyan rendezünk, csak oldjuk meg a feladatot. Két rendezési algoritmust fogok megmutatni, amelyeket használni/tanítani szoktam, ha ezeket tudod, akkor bármilyen típusú tömböt rendezni tudsz.
A rendezések legtöbbje összehasonlításokon és cseréken alapul. Összehasonlítunk két elemet, és ha azok sorrendje nem megfelelő, akkor megcseréljük őket. Az algoritmusok sokszor abban különböznek, hogy melyik kettőt hasonlítjuk össze és utána melyik kettőt, stb. Létezik olyan speciális rendezés is, amelyik nem használ összehasonlításokat és cseréket, de ezek csak bizonyos esetekben használhatóak, akkor viszont hihetetlen gyorsak.
A rendezés esetén már összetettebb módon kell bejárni a tömböt, amelynek elemeit rendezni szeretnénk. Itt is igaz az, hogy nem csak egyszerű típusú értékeket tartalmazó tömböket lehet rendezni, az elemek lehetnek összetett objektumok is, melyek többféle típusú értéket tartalmazhatnak.
A tömbök kezelésekor, és az alap algoritmusok használatakor minden esetben ciklusokat használunk arra, hogy bejárjuk az adott tömböt, és annak értékeihez egymás után hozzáférjünk. Abban vannak csak különbségek, hogy ténylegesen bejárjuk-e az egészet, vagy sem, esetleg a bejárás iránya változik. Itt azonban másról lesz szó. Itt találkozunk először az egymásba ágyazott ciklusokkal.
A rendezések, melyeket jellemzően használunk minden esetben azt az elvet követik, hogy a tömb bizonyos elemeit hasonlítják össze, hogy azok egymáshoz képest a kívánt sorrendben helyezkednek-e el. Ha ez nem így van, akkor ezt a két elemet meg kell cserélni. Itt azonban nem csak az egymás melletti szomszédokat vizsgáljuk,
Egyszerű cserés rendezés
Ezt a rendezést több néven is megtalálhatjuk az alap algoritmusok között, én ezt a nevet használom. Az elv, ami alapján dolgozik az az, hogy minden elemet összehasonlít az összes mögötte lévővel, és ha azok sorrendje nem megfelelő, akkor megcseréli őket. Két egymásba ágyazott ciklust igényel, ezeket tradicionálisan i és j ciklusváltozókkal használjuk. Lássuk akkor magát az algoritmust, ahol feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve és a meret nevű változóban a tömb méretét találjuk meg:
1
2
3
4
5
6
7
8
9
10
11
12
13
int csere;
for( int i = 0; i < tomb.length-1; i++ )
{
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[i] > tomb[j] )
{
csere = tomb[i];
tomb[i] = tomb[j];
tomb[j] = csere;
}
}
}
A ciklus úgy dolgozik, hogy a j változó mindig az i utáni helyet jelöl, mivel a j kezdőértéke minden esetben i+1-ről indul. Éppen ezért az i soha nem mehet el a tömb végéig, mert akkor az utolsó elem utáni összehasonlítást is elvégezne, ami mindenképp hibás.
Tehát még egyszer a lényeg: az i van elöl, a j van hátul!
Lássuk a kiemelt részek magyarázatát:
1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
2 – Az i változó soha nem mehet el a tömb végéig, vagyis i < tomb.length-1;
4 – A j mindig az i után áll, ezért int j = i+1;
6 – Mindig összehasonlítjuk az elöl és hátul lévő elemeket, és ha ezek sorrendje nem megfelelő…
8-10 – Akkor jön az elemek cseréje.
A rendezés iránya csak és kizárólag a 6. sorban megadott relációs jeltől függ. Ha az elöl lévő nagyobb és akkor cserélünk, akkor a nagyok kerülnek hátra, vagyis növekvő rendezést alkalmazunk. Ha az elől lévő kisebb és akkor cserélünk, akkor a kicsik kerülnek hátra, és csökkenő rendezést írunk. A fenti példa tehát növekvő rendezést valósít meg, mivel az első esetnek megfelelő a relációs jel.
A csökkenő rendezés ehhez képest tehát minimális változtatással jár:
1
2
3
4
5
6
7
8
9
10
11
12
13
int csere;
for( int i = 0; i < tomb.length-1; i++ )
{
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[i] < tomb[j] )
{
csere = tomb[i];
tomb[i] = tomb[j];
tomb[j] = csere;
}
}
}
Minimum/maximum kiválasztásos rendezés
Ez a rendezés az előző továbbfejlesztett változata. Az előző algoritmus úgy dolgozik, hogy minden esetben megcseréli a két elemet, ha az aktuális két elem helyzete nem megfelelő. Ez azt eredményezi, hogy több csere is lesz, mire a legkisebb a tömb elejére kerül növekvő rendezés esetén. De ha már egyszer növekvő rendezést akarunk megvalósítani, akkor nem lenne jobb, hogy ha először megkeresnénk a legkisebb elemet, majd azt helyeznénk a lista elejére, majd utána megkeresnék a második legkisebbet, azt beraknánk az első után, és így tovább? Jóval kevesebb cserével járna, mint az előző. Természetesen megoldható, az előző rendezési algoritmusa tökéletesen kombinálható a már tanult minimum/maximumkeresési algoritmusokkal. Lássuk akkor hogyan:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int csere;
int min;
for( int i = 0; i < tomb.length-1; i++ )
{
min = i;
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[j] < tomb[min] )
{
min = j;
}
}
if( min != i )
{
csere = tomb[i];
tomb[i] = tomb[min];
tomb[min] = csere;
}
}
Lássuk akkor a magyarázatot:
1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
2 – Kell egy változó, ahol a legkisebb elem helyét tároljuk (mint a minimumkiválasztásnál), de ennek itt még nem adunk kezdőértéket.
5 – Mielőtt elkezdjük a belső ciklust, ami az elöl lévő elem mögöttiek indexén megy végig, az elöl lévő elemet feltételezzük a legkisebbnek. Itt a belső ciklus futását gyakorlatilag egy minimum kiválasztásnak írtuk meg. A tomb[i] az első elem, ezért ennek a helyét feltételezzük a legkisebb elem helyének,
8 – majd, ha az eddigi minimumtól valamelyik mögötte lévő (tomb[j]) tőle kisebb,
10 – akkor a hátul lévő elem helyét (j) jegyezzük meg, mint aktuális legkisebbet.
13 – Ha a belső ciklussal végeztünk, akkor a min változóban benne van a hátul lévő elemek közül a legkisebbnek a helye. Ha ez a hely nem egyenlő az elöl lévővel (vagyis nem önmaga a legkisebb), akkor találtunk az elöl lévő (i) elem mögött tőle kisebbet, melynek helyet a min változóban tároljuk.
15-17 – Ebben az esetben a két elemet (i és min helyen lévőket) megcseréljük.
Ezt az algoritmust inkább csak érdekességképp mutattam meg, érettségire tökéletesen elég, ha az egyszerű cserés rendezést megtanulod, mert csak az a követelmény, hogy rendezni tudj, teljesen mindegy, melyik algoritmussal. Nyilván a legegyszerűbbet célszerű megtanulni, a hatékonyság nem követelmény.
Kiválogatás
Szintén az alap algoritmusok közé tartozik az a feladattípus, amikor bizonyos tulajdonságnak, vagy tulajdonságoknak megfelelő elemeket kell egy tömbből egy másik tömbbe kiválogatni. Tegyük fel, van egy egészeket tartalmazó tömbünk, melyet a [-9;9] intervallumból töltöttünk fel. Hogyan oldhatjuk meg, hogy ebből a tömbből egy másik tömbbe kigyűjtjük a negatív számokat? Minden esetben létre kell hozni egy másik tömböt, amibe a megfelelő elemeket másoljuk. De mekkora legyen ez a tömb? Ez az ami alapvetően meghatározza, hogy milyen megoldási módot alkalmazunk. Kétféle esetet különböztetünk meg:
Létrehozunk egy eredeti tömbnek megfelelő méretű tömböt, azt feltételezve, hogy akár az összes elem lehet negatív, így mindet át kell másolni. Ha azonban nem minden elem negatív, akkor az új tömbben maradnak üres helyek, ahova nem rakunk át semmit. Így nyilván kell tartanunk, hogy hány elemet másoltunk át az új tömbbe, és mennyi maradt “üresen” a végén.
Megoldhatjuk úgy is, hogy először megszámoljuk, hogy hány elem felel meg a feltételnek, ami alapján a kiválogatást el akarjuk végezni, és az új tömböt pontosan akkorának állítjuk be. Így a megoldás végén az új tömbben csak azok az elemek lesznek benne, amelyeket mi helyeztünk el benne.
A két megoldásból a második nyilván picivel több munkával jár, mert kapcsolódik hozzá egy megszámlálás is, viszont utána már nem kell attól tartanunk, hogy az eredmény tömbben olyan elem is előfordul, ami nem felel meg a kiválogatás feltételének.
Lássuk akkor a két különböző megoldást. Mindkét esetben feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve. Az új tömbbe a páratlan számokat szeretnénk kiválogatni:
1
2
3
4
5
6
7
8
9
10
11
int[] paratlan = new int[tomb.length];
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
paratlan[db] = tomb[i];
db++;
}
}
Lássuk akkor a kiemelt sorok magyarázatát:
1 – Létrehozok egy ugyanakkora tömböt, mint az eredeti, lehetőséget adva arra, hogy akár minden elemet kiválogathassak.
3 – Létrehozok egy db nevű változót, ami jelen esetben az első üres helyet fogja tárolni, ahova a következő kiválogatott elemet elhelyezhetem, a kiválogatás végeztével pedig tárolni fogja, hogy az új tömbbe hány elem került bele.
4 – Végigmegyek az eredeti tömbön,
6 – és ha az eredeti tömbben páratlan számot találunk,
8 – akkor az új tömbben a első üres helyre (db) elhelyezem az elemet,
9 – majd megnövelem a db-ot, hogy az esetleges következő átmásolt elem ne írja felül az előzőt.
Látható, hogy nem olyan bonyolult algoritmusról van szó, a kulcs az, hogy mindig tárolom egy változóban, hogy hol van az új tömbben az első üres hely, mert csak oda rakhatok bele a kiválogatás során elemeket. A gond csak annyi, hogy ha van egy 1000 méretű tömböm, amibe 3 elemet kellene csak kiválogatni, akkor is a memóriában foglalja az 1000 elemnyi helyet a 3 kedvéért.
Lássuk akkor a másik megoldást:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
db++;
}
}
int[] paratlan = new int[db];
db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
paratlan[db] = tomb[i];
db++;
}
}
Ha jól megnézed nem sokkal bonyolultabb, picit többet kell gépelni, és ki kellett egészíteni a megszámlálás alap algoritmusával:
1-8 – Megszámoljuk, hány elemet kell majd kiválogatni az új tömbbe.
10 – Létrehozunk egy ugyanakkora tömböt.
12-20 – Ez pedig pontosan az első megoldás.
Az egész algoritmus kulcs momentuma a db változó használata! Ennek több szerepe is van. Először a kiválogatandó elemek darabszámát gyűjtjük bele, utána a következő üres helyet jelöli az új tömbben, végül a kiválogatás végeztével az új tömb méretét jelenti, bár ezt a tömbből úgyis ki lehet nyerni a .length változóból.
Szétválogatás
A szétválogatás algoritmusa a kiválogatás kibővítése. Az alapfeladat az, hogy az eredeti tömb minden elemét két külön tömbbe kell elhelyezni. Feltételezzük, hogy minden elem bekerül valamelyik új tömbbe, vagyis nem hagyunk ki semmit sem. A kiválogatásnál ennek a feladatnak a felét gyakorlatilag megoldottuk. Amit egy kiválogatásnál kiválogatunk, az itt az egyik tömb elemeinek felelne meg. Az összes többi elemet a másik tömbbe pakoljuk. Így már nem is tűnik olyan nehéznek, igaz?
A szétválogatás feltétele minden esetben gyakorlatilag egyetlen feltétel.
Válogassuk szét a tömb elemeit 5-től nagyobb és nem nagyobb elemekre. (emlékezz a relációs jelekre!)
Válogassuk szét a tömb elemeit 5-tel osztható és nem osztható elemekre.
Válogassuk szét az elemeket egyjegyű és nem egyjegyű számokra
Válogassuk szét a tömb elemeit páros és páratlan elemekre.
Ha megfigyelted, a feladatok jó része úgy fogalmazza meg a feltételt, hogy szétválogatjuk valamilyen és NEM valamilyen elemekre. Egy feltétel és annak az ellentettje minden elemet le kell hogy fedjen. Ezért szétválogatás, nem maradhat ki egyetlen elem sem. És az utolsó esetben? Amelyik szám nem páros, az páratlan, tehát ez is lefed minden számot.
A szétválogatásnál is ugyanaz a dilemma lesz először, mint amit a kiválogatásnál írtam:
Nem foglalkozok az új tömbök méreteivel, a legrosszabb esetből indulok ki, hogy minden elemet be kell tennem az egyik tömbbe, a másik pedig üres marad. Ebben az esetben mindkét új tömb méretének az eredeti tömb méretét állítom be, így a két új tömb kétszer annyi helyet foglal majd, amennyire valóban szükség lenne.
Előre megszámolom, hány elem felel meg a szétválogatás feltételének, ezután beállítom a kívánt tömbméreteket, majd utána válogatom szét az elemeket. Ez a legtakarékosabb megoldás, mert mindkét tömb mérete pontosan akkora lesz, amekkorára szükségem lesz. Ha emlékszel, a kiválogatásnál itt egy megszámlálással bővítettem ki az alap megoldást.
Lássuk akkor az első esetet. Tételezzük fel, hogy van egy adott méretű tömböm, feltöltve elemekkel. Válogassuk szét az elemeket páros és páratlan elemeket tartalmazó tömbökbe. Vedd észre, hogy ez valójában egyetlen feltétel. Ami nem páros, az páratlan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int[] paros = new int[tomb.length];
int[] paratlan = new int[tomb.length];
int dbparos = 0;
int dbparatlan = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
paros[dbparos] = tomb[i];
dbparos++;
}
else
{
paratlan[dbparatlan] = tomb[i];
dbparatlan++;
}
}
Ha a kiválogatás algoritmusát megértetted, akkor ezzel se lesz probléma. Nem véletlenül csak két részt emeltem ki. A kiválogatásnál kellett egy számláló, amelyben nyilvántartottam, hogy hány elemet válogattam ki, ami egyúttal azt is jelezte, hogy hol van az új tömbben a következő üres hely. Itt is hasonló a helyzet, csak itt két tömb esetén két külön változóban kell tárolni, hogy hány elem van az egyikben-másikban, és ezáltal melyik tömbben hol van a következő üres hely, ahova az elemeket pakolhatom. A belső feltétel sem sokat változott, ha a feltételnek megfelel az elem, akkor berakom az egyik tömbbe, ha nem, akkor mindenképpen (else) a másik tömbbe kell tennem. Emlékszel: minden elem bekerül valamelyik tömbbe, ha nem az elsőbe, akkor a másodikba, nem hagyhatok ki semmit sem.
Ne felejtsd el, a két új tömb mérete nagyobb, mint amennyi tényleges elemet tartalmaznak. Az algoritmus után a két darabszámot tároló változó az, amiből megtudhatod, hogy mekkora valójában a tömb, amit kezelned kell. Nem a paros.length lesz az a határ, ameddig be kell járnod egy ciklussal, hanem a dbparos változó.
Lássuk akkor a második megoldást. Emlékeztetőül: megszámolom hány elemet kell majd beraknom az egyik tömbbe, akkor meglesznek a megfelelő tömbméretek.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int parosdb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
parosdb++;
}
}
int[] paros = new int[parosdb];
int[] paratlan = new int[tomb.length-parosdb];
parosdb = 0;
paratlandb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
paros[parosdb] = tomb[i];
parosdb++;
}
else
{
paratlan[paratlandb] = tomb[i];
paratlandb++;
}
}
Lássuk akkor a kiemelt részeket:
1-9 – Megszámolom, hány elem felel meg a szétválogatás feltételének.
11-12 – Létrehozom a két megfelelő méretű tömböt. A páratlan tömb méretét úgy kapom meg, hogy a tömb elemeinek darabszámából kivonom a párosok darabszámát, így megvan a páratlanok száma.
14-31 – Lenullázom a két számlálót, és elvégzem a szétválogatást az első megoldásnak megfelelően, csak itt már biztos lehetek benne, hogy mindkét új tömböt teljesen feltöltöm.
Az előzőhöz képest ez nyilván bonyolultabb megoldás. Cserébe takarékosabb, másrészt nem kell külön tárolni, hogy a tömbök valójában meddig vannak feltöltve, mivel a méretük pontosan megfelel a szétválogatott elemek darabszámának.
És ha nem mindent válogatok szét?
Ez az algoritmus csak abban az esetben használható, ha minden elemet szét kell válogatni. Ez mondjuk a szétválogatás elvéből is következik, mivel nem hagyhatunk ki elemeket, különben nem szétválogatásnak neveznénk. Mégis a példa kedvéért tételezzük fel, hogy egy tömbből szeretnénk a pozitív és negatív számokat két másik tömbbe átpakolni. Ebben az esetben már figyelnünk kell arra, hogy mi a helyzet a nullákkal. Természetesen ezt is meg kell oldani, csak itt az elemek megszámolásánál figyelembe kell venni, hogy kihagyunk elemeket, valamint a tényleges válogatásnál is ügyelni kell rájuk. Szándékosan kerültem a szétválogatás szót, mert ez valójában a kihagyott elemek miatt nem az lesz. Lássunk akkor erre egy példát.
Válogassuk ki egy tömb elemei közül a pozitív és negatív számokat. (Észrevetted? Kiválogatás)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int pozitivdb = 0;
int negativdb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] > 0 )
{
pozitivdb++;
}
else if( tomb[i] < 0 )
{
negativdb++;
}
}
int[] pozitiv = new int[pozitivdb];
int[] negativ = new int[negativdb];
pozitivdb = 0;
negativdb = 0;
for( int i = 0; i < tomb.length; i++ ) { if( tomb[i] > 0 )
{
pozitiv[pozitivdb] = tomb[i];
pozitivdb++;
}
else if( tomb[i] < 0 )
{
negativ[negativdb] = tomb[i];
negativdb++;
}
}
1-13 – Egy ciklusban megszámolom a pozitív és negatív számokat.
15-16 – Létrehozom nekik a megfelelő méretű tömböket.
És kiválogatom őket egyetlen ciklusban.
Ez gyakorlatilag két kiválogatás egy ciklusba pakolva, a két feltételnek (pozitív vagy negatív) lényegében semmi köze egymáshoz, a számlálóik is teljesen függetlenek, mert nem tudom, hogy a két feltétel lefedi-e az összes eredeti elemet vagy sem. Ha a két feltétel minden elemet besorol valahova, akkor szétválogatás, egyébként két egymástól független kiválogatásról beszélünk.
Metszet
A metszet algoritmus egy kis magyarázatot igényel. Az alap algoritmusok metszetképzése nem egyezik meg a halmazelméletben tanult metszettel. A halmazt elemek sokaságának tekintjük, ahol az elemeknek nincs sorrendje, és minden elem csak egyszer szerepelhet a halmazban. Ez a tömböknél nyilvánvalóan nem áll fenn. A halmazoknál metszetként azon elemek halmazát vesszük, amelyek mindkét halmazban megtalálhatóak.
Tömbök esetén ez azt jelenti, hogy az egyik tömbből vesszük azokat az elemeket, amelyek benne vannak a másikban. Ezzel az algoritmussal csak az a bajom, hogy nem mindegy, hogy melyik tömb oldaláról kezdjük ez a dolgot. Lássuk a következő példát, hogy miről is van szó.
{2,2,3,4}
{3,5,2,6,6}
Ha az első tömb elemeiből hagyjuk meg azokat, amelyek benne vannak a másodikban, akkor ezt az eredményt kapjuk:
{2,2,3}
Ha a második tömb elemeiből hagyjuk meg azokat, amelyek benne vannak az elsőben, akkor ezt az eredményt kapjuk:
{3,2}
Nyilván látszik mi a gond. Ez pedig abból fakad, hogy egy elem többször is lehet egy tömb eleme. A sorszámozás miatt ezek egyértelműen megkülönböztethetőek. A halmazban viszont az elemek nem sorszámozottak, ezért két azonos értékű elemet nem különböztethetnénk meg. Az algoritmus nem foglalkozik ezzel a problémával, és nekünk sem kell. Más kérdés, hogy meg tudnánk oldani azt is, hogy minden elem egyszer szerepeljen csak a metszetben, később ezt is megmutatom.
Mint már fent említettem, az algoritmus annyiból áll, hogy az vesszük az egyik tömb elemei közül azokat, amelyek benne vannak a másikban. Nézzük meg jobban, mi is ez? Kiválogatjuk az egyik tömb elemei közül azokat, amelyek megfelelnek annak a feltételnek, hogy benne vannak a másik tömbben. Kiválogatás, amiben van egy eldöntés. A metszetképzés tehát két tanult algoritmus kombinációja.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int[] t1 = new int[] {2,2,3,4};
int[] t2 = new int[] {3,5,2,6,6};
int[] metszet = new int[t1.length];
int j;
int db = 0;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < t2.length && t2[j] != t1[i] )
{
j++;
}
if( j < t2.length )
{
metszet[db] = t2[j];
db++;
}
}
Lássuk a kiemelt részek magyarázatát:
3 – A metszet tömb mérete akkora, mint az első tömb mérete, hiszen lehet, hogy annak minden eleme megtalálható a másikban. Természetesen a kiválogatáshoz hasonlóan itt is ügyelni kell arra, hogy nem feltétlen kerül minden elem a metszet tömbbe, ezért majd a db változó fogja tárolni a metszet tömb valódi elemeinek számát.
7 – Ebben a sorban elkezdünk egy kiválogatást, vagyis elindulunk az első tömbön azt keresve, hogy ezek közül melyiket kell majd átrakni a metszetbe.
9-14 – Ez gyakorlatilag az eldöntés algoritmusa, addig haladunk a második tömb elemein, és addig megyünk, amíg nem találunk egyezést a második tömb eleme és az első tömb éppen aktuális eleme között. Ezt az algoritmust most nem magyaráznám el újra, de ami a lényeg: ha az elemet megtaláltuk, akkor visszatérünk a kiválogatáshoz
16-17 – Ha találtunk olyan első tömbbeli elemet, ami megfelelt a feltételünknek (benne van a másodikban is), akkor berakjuk a metszet tömbbe, és növeljük a számlálóját. Ez a kiválogatás algoritmus vége.
Metszet egyedi elemekkel
Mi van akkor, ha valóban csak annyit szeretnénk megtudni, hogy mik azok a számok, melyek mindkét tömbben megtalálhatóak? Ha valami többször szerepel a tömbben, attól mint szám csak egyszer szerepel. Ez nem alap algoritmus, hanem az eddig tanultakat kell alkalmazni. Akár teljesen eltérő megoldásokat is adhatunk:
A két tömb közül az elsőből létrehozok egy olyan tömböt, ami az eredetiben szerepelő számokat csak egyszer tartalmazza. Majd ha erről az oldalról metszetet képzek, akkor a metszetben is minden elem csak egyszer fog szerepelni.
Az első tömbből csak akkor teszek be egy számot a metszetbe, ha benne van a másodikban, és még nincs benne a metszetben. Vagyis a kiválogatáson belül két eldöntésre van szükségem, melyeknek egyszerre kell teljesülnie. Azzal még finomíthatom, hogy ha a második tömbben nincs benne, akkor felesleges a metszetben ellenőrizni, mert akkor oda semmiképpen nem kerülhetett be.
Lássuk az első megoldást:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int[] t1 = new int[] { 2, 2, 3, 4 };
int[] t2 = new int[] { 3, 5, 2, 6, 6 };
int[] metszet = new int[t1.length];
int[] egyedi = new int[t1.length];
int dbe = 0;
int j;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < dbe && t1[i] != egyedi[j] )
{
j++;
}
if( j == dbe )
{
egyedi[dbe] = t1[i];
dbe++;
}
}
int db = 0;
for( int i = 0; i < dbe; i++ )
{
j = 0;
while(j < t2.length && t2[j] != egyedi[i])
{
j++;
}
if( j < t2.length )
{
metszet[db] = t2[j];
db++;
}
}
Mit is csinálunk pontosan?
5 – Létrehozom azt a tömböt, ahova kiválogatom az első tömb számait. Ennek mérete az eredetivel megegyező, mert lehet, hogy egyik szám sem szerepel többször, akkor mindet át kell pakolni.
6 – Létrehozok egy számlálót, hogy nyilvántartsam, valójában hány elem lesz az egyedi tömbben.
8-21 – Kiválogatom az egyedi számokat. (kiválogatásban egy eldöntés) Fontos, hogy akkor rakom bele az egyedi tömbbe a számot, ha az eldöntés hamis eredményt ad, vagyis nincs benne: if( j == dbe )
23-36 – Ez pedig a metszetképzés algoritmusa, de az egyedi tömb és a második között. A 24-es sorban fontos a feltétel, hogy az egyedi tömbnek nem az összes elemét kell vizsgálni, hanem csak addig, ameddig valóban vannak benne elemek. Ezt a saját dbe számlálója tárolja.
A két részfeladat (egyedi tömb előállítása, majd metszetképzés) ugyanarról a tőről fakad, hiszen mindkét esetben egy elemről akarom eldönteni, hogy benne van-e egy tömbben. A különbség csak az, hogy egyedi elemek válogatásakor akkor rakom bele, ha nincs még benne, metszetképzésnél pedig akkor rakom bele, ha benne van.
Nézzük a másik megoldást, amikor a két eldöntést teszek a kiválogatásba:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int[] t1 = new int[] { 2, 2, 3, 4 };
int[] t2 = new int[] { 3, 5, 2, 6, 6 };
int[] metszet = new int[t1.length];
int j;
int jm;
int db = 0;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < t2.length && t2[j] != t1[i] )
{
j++;
}
if( j < t2.length )
{
jm = 0;
while( jm < db && metszet[jm] != t1[i] )
{
jm++;
}
if( jm == db )
{
metszet[db] = t1[i];
db++;
}
}
}
Lássuk a lényegi részeket:
10-14 – Eldöntjük, hogy az első tömb eleme benne van-e a másodikban.
15 – Ha igen, akkor
15-27 – Eldöntjük, hogy benne van-e a metszetben.
22 – Csak akkor tesszük be a metszetbe, ha még nincs benne. Ha már egyszer betettünk ilyen számot, akkor nem tesszük bele még egyszer.
Ez a megoldás talán rövidebb és egyszerűbb is, mint a másik, és minden esetben egyedi elemeket tartalmazó metszet tömböt kapunk.
Természetesen ez a metszetképzés algoritmus több hasonló feladatnál is használható, hiszen ha metszetet tudunk képezni, akkor olyan kérdésekre is választ kaphatunk ennek segítségével, hogy van-e két tömbnek azonos eleme, hány közös eleme van két tömbnek, stb.
Komplex feladat
Lássunk egy komplexebb feladatot. Adott egy 10 elemű tömb melyet véletlen számokkal töltöttünk fel a [-9;9] intervallumból. Írjuk ki növekvő sorrendben a tömbben szereplő páros számokat.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
*
* @author http://webotlet.hu
*/
package webotlet_alapalg_komplex;
public class Webotlet_alapalg_komplex
{
public static void main(String[] args)
{
int[] tomb = new int[10];
for (int i = 0; i < tomb.length; i++)
{
tomb[i] = (int) (Math.random() * 19) - 9;
}
for (int i = 0; i < tomb.length; i++)
{
System.out.print(tomb[i] + " ");
}
System.out.println();
int db = 0;
for (int i = 0; i < tomb.length; i++)
{
if (tomb[i] % 2 == 0)
{
db++;
}
}
int[] paros = new int[db];
db = 0;
for (int i = 0; i < tomb.length; i++)
{
if (tomb[i] % 2 == 0)
{
paros[db] = tomb[i];
db++;
}
}
int csere;
for (int i = 0; i < db - 1; i++)
{
for (int j = i + 1; j < db; j++)
{
if (paros[i] > paros[j])
{
csere = paros[i];
paros[i] = paros[j];
paros[j] = csere;
}
}
}
for (int i = 0; i < db; i++)
{
System.out.print(paros[i] + " ");
}
System.out.println();
}
}
Ez egy tökéletes feladat arra, hogy az eddig tanultakat összefoglalja. Sok ismerős részletet láthatunk benne, de lássuk akkor részenként:
12-17 – Adott méretű tömb létrehozása, majd feltöltése véletlen számokkal.
19-22 – A kisorsolt tömb kiíratása.
24 – Sordobás a sorsolt tömb kiíratása után, hogy ne folyjon egybe majd a rendezett tömb kiíratásával.
26-33 – A kiválogatáshoz megszámoljuk, hány elemet kell majd átrakni az új tömbbe.
35 – Létrehozzuk az új tömböt.
37-45 – Kiválogatjuki (átmásoljuk) a páros számokat az új tömbbe.
47-59 – Rendezzük az új tömböt.
61-64 – Kiírjuk a kiválogatott és rendezett új tömböt.
66 – Egy bónusz sordobás a végére, hogy ha bővíteném a programot, akkor az új kiíratás új sorban kezdődjön.
Adott tehát egy elsőre bonyolultnak tűnő feladat, amit szétbontottuk olyan részekre, melyeket már külön-külön meg tudunk oldani. Ezeket a kész megoldásokat (tömb feltöltés, kiíratás, megszámlálás, kiválogatás, rendezés, stb) megfelelő sorrendben hibátlanul összerakjuk, és kész a feladat teljes megoldása. Ugye így jobban belegondolva nem is olyan nehéz? Feltéve hogy az eddigi tananyagokat már készségszinten alkalmazni tudod. Sokszor az a legnehezebb feladat, hogy felismerjük azt, hogy az aktuális feladat milyen kisebb alkotóelemekre bontható, melyekre már kész megoldásaink vannak. Ha ez a részekre bontás megy, akkor gyakorlatilag sokszor gépelési feladattá tudjuk egyszerűsíteni a feladatok nagy részének megoldását.
A feladat így szol: a program beker egesz szamokat, mig -1-et nem olvas, es kiirja a -1 elotti szamok atlagat! Az eredmenyt ket tizedesjegyre kerekiti. (A bemenet mindig egesz szam.)
Scanner sc = new Scanner(System.in);
double n = 0;
double bekert;
double atlag;
System.out.println(“Kérem a számokat (-1-re kilép):”);
bekert = sc.nextInt();
while (bekert != -1) {
n += bekert;
bekert = sc.nextInt();
}
if (bekert == -1) {
// atlag = na ez az a resz, ahol nem jovok ra a helyes kepletre, noha tudom hogy kell atlagot szamolni
System.out.print(“Az összeg: “+atlag+”.”);
} else {
System. out.print(“Az összeg: 0.0”);
}
}
}
Ez nagyon hasonlo a te atlagolos feladatodhoz, de valahogy megsem jovok ra, hogyan kellene megoldani. Nagyon megkoszonom, ha segitesz benne egy kis extra magyarazattal.
Megoldás;
int szam;
int osszeg = 0;
int db = 0;
Scanner sc = new Scanner(System.in);
do
{
szam = sc.nextInt();
if( szam != -1 )
{
osszeg += szam;
db++;
}
}
while( szam != -1);
if( db == 0 )
{
System.out.println(“Nem adtal meg szamot.”);
}
else
{
System.out.println((double)osszeg/db);
}
Fontos!
A lényeg, hogy ha a ciklusban nem -1 számot olvasol be, akkor gyűjteni kell a bekért számokat egy összegváltozóba, a darabszámukat meg egy darabba. Ebből tudsz összeget számolni, ha szükséges.
Az összegváltozód megvan, de nem számolod a beolvasásokat, ezért nem tudsz átlagot számolni.
A típusok könnyebb megtalálásához és használatához, névütközések elkerüléséhez és az elérés szabályozásához a programozók egybe csomagolhatják az összetartozó típusaikat csomagokká.
Definíció: A csomag összetartozó típusok gyűjteménye.
A Java platform típusai funkciók szerint különböző csomagokba vannak szervezve: az alapvető osztályok a java.lang csomagban, az I/O osztályok a java.io-ban, és így tovább. Ezen kívül a saját típusainkat is tehetjük csomagokba.
A következő osztályokat megvizsgálva látszik, hogy közös csomagba érdemes őket sorolni, mivel grafikus objektumok csoportjába tartoznak a körök, téglalapok, vonalak és pontok. Ha írunk egy Draggable interfészt, az azt megvalósító osztályok lehetővé teszik a vonszolást is.
//in the Graphic.java file
public abstract class Graphic {
. . .
}
//in the Circle.java file
public class Circle extends Graphic implements Draggable {
. . .
}
//in the Rectangle.java file
public class Rectangle extends Graphic implements Draggable {
. . .
}
//in the Draggable.java file
public interface Draggable {
. . .
}
A következő okok miatt érdemes az osztályokat és interfészeket közös csomagba helyezni:
Más programozók számára is látszik, hogy kapcsolódó típusokról van szó.
Más programozók is láthatják, hol kell keresni a grafikához kapcsolódó osztályokat.
A típusaink nevei nem kerülnek összeütközésbe más csomagok neveivel, mert a csomagok önálló névtereket hoznak létre.
A típusaink korlátlanul láthatják egymást, de egyéb típusok csak korlátozottan férhetnek a
típusokhoz.
Importálásról egy kicsit; Egy csomag tag importálása
Ahhoz hogy importálhassuk a megadott tagot az aktuális fájlban, a fájl elején ki kell adni az import utasítást az osztály vagy interfész definiálása előtt, de a package utasítás után, ha van olyan. Úgy tudjuk importálni a Circle osztályt a graphics csomagból, hogy:
import graphics.Circle;
Most már tudunk hivatkozni a Circle osztályra az egyszerű nevével:
Circle myCircle = new Circle();
Ez a szemlélet akkor működik jól, ha csak néhány tagot használunk a graphics csomagból. De ha sok típusát használjuk egy csomagnak, akkor inkább importáljuk az egész csomagot.Egy teljes csomag importálása
Ahhoz hogy egy csomagnak az összes típusát importáljuk, az import utasítást a csillag (*) helyettesítő karakterrel kell használnunk:
import graphics.*;
Most már hivatkozhatunk bármelyik osztályra vagy interfészre a graphics csomagból az egyszerű rövid nevével:
Circle myCircle = new Circle();
Rectangle myRectangle = new Rectangle();
Az import utasításban a csillag karakterrel az összes osztályát megadjuk a csomagnak. Nem használhatunk olyan megfeleltetést, amely egy csomagban egy osztály részhalmazára utal. Például helytelen megfeleltetés az, hogy a graphics csomagból az ’A’ betűvel kezdődő összes osztály importáljuk:
import graphics.A*;
Ez az utasítás fordítási hibát generál. Az import utasítással, egy csomagnak egyetlen tagját vagy egész csomagot importálhatunk.
Ugyanígy nem megengedett, hogy egyszerre több csomagot importáljunk, pl.:
import graphics.*.*;
Megjegyzés: Ha kevesebb tagot akarunk importálni, akkor megengedett, hogy csak egy osztályt, és annak a belső osztályait importáljuk. Például, ha a graphics.Rectangle osztálynak a belső osztályait akarjuk használni, mint Rectangle.DoubleWide és Rectangle.Square, a következőképpen importálhatjuk:
import graphics.Rectangle.*;
Könnyítésül a Java fordító automatikusan importál három teljes csomagot:
A névtelen csomagot (ha nem hozunk létre csomagot, vagyis nem használjuk a package utasítást)
Az alapértelmezés szerinti aktuális csomagot (ha létrehozunk csomagot)
A java.lang csomagot
Megjegyzés: A csomagok nem hierarchikusak. Ha például importáljuk a java.util.*-ot, nem hivatkozhatunk a Pattern osztályra. Minden esetben úgy kell hivatkoznunk, hogy java.util.regex.Pattern, vagy ha importáljuk a java.util.regex.*-ot, akkor csak egyszerűen Pattern.
Mik a csomagok?
A típusok könnyebb megtalálásához és használatához, névütközések elkerüléséhez és az elérés szabályozásához a programozók egybe csomagolhatják az összetartozó típusaikat csomagokká.
Definíció: A csomag összetartozó típusok gyűjteménye.
A Java platform típusai funkciók szerint különböző csomagokba vannak szervezve: az alapvető osztályok a java.lang csomagban, az I/O osztályok a java.io-ban, és így tovább. Ezen kívül a saját típusainkat is tehetjük csomagokba.
A következő osztályokat megvizsgálva látszik, hogy közös csomagba érdemes őket sorolni, mivel grafikus objektumok csoportjába tartoznak a körök, téglalapok, vonalak és pontok. Ha írunk egy Draggable interfészt, az azt megvalósító osztályok lehetővé teszik a vonszolást is.
//in the Graphic.java file
public abstract class Graphic {
. . .
}
//in the Circle.java file
public class Circle extends Graphic implements Draggable {
. . .
}
//in the Rectangle.java file
public class Rectangle extends Graphic implements Draggable {
. . .
}
//in the Draggable.java file
public interface Draggable {
. . .
}
A következő okok miatt érdemes az osztályokat és interfészeket közös csomagba helyezni:
Más programozók számára is látszik, hogy kapcsolódó típusokról van szó.
Más programozók is láthatják, hol kell keresni a grafikához kapcsolódó osztályokat.
A típusaink nevei nem kerülnek összeütközésbe más csomagok neveivel, mert a csomagok önálló névtereket hoznak létre.
A típusaink korlátlanul láthatják egymást, de egyéb típusok csak korlátozottan férhetnek a
típusokhoz.
Csomag létrehozása
A csomag létrehozásához mindössze bele kell tenni egy típust (osztály, interfész). A csomag megnevezést a forrásállomány elején, a típusdefiníciók előtt kell megtenni.
package graphics;
public class Circle extends Graphic implements Draggable {
. . .
}
Ez után a graphics csomag összes forráskódja elején ugyanezt a csomagmegjelölést kell alkalmaznunk, hogy közös csomagba kerüljenek:
package graphics;
public class Rectangle extends Graphic implements Draggable {
. . .
}
Ha nem alkalmazunk csomagmegjelölést, akkor az osztály(ok) egy úgynevezett alapértelmezett név nélküli csomagba kerülnek.
Egy csomag elnevezése
Az egész világon írnak a programozók a Java programnyelvhez osztályokat, interfészeket, kulcsszavakat és megjegyzéseket, és valószínűleg két programozó ugyanazt a nevet két különböző feladatú osztálynál fogja használni. Valójában, az előző példa esetén, amikor definiálunk egy Rectangle osztályt, akkor a Rectangle osztály már benne van a java.awt csomagban. A fordító mégis engedélyezi két osztálynak ugyanazt a nevet. Miért? Mert azok különböző csomagokban vannak, és mindegyik osztálynak a teljes neve magába foglalja a csomag nevét. Tehát a graphics csomagban levő Rectangle osztály teljes neve graphics.Rectangle, és a java.awt csomagban levő Rectangle osztály teljes neve java.awt.Rectangle. Ez rendszerint csak akkor működik jól, hogyha két egymástól független programozó nem ugyanazt a nevet adja a csomagoknak. Mivel hárítható el ez a probléma? Megállapodással.
Megállapodás: Fordított domain (tartomány) nevet használnak a csomagok nevének, ilyen módon: com.company.package. Névütközés előfordulhat egyetlen cégen belül is, amit a cégnek le kell kezelni egy belső megállapodással. Lehet, hogy emiatt tartalmazni fog tartomány vagy projekt neveket a társaság neve után, mint például com.company.region.package.
Csomag tagok használata
Csak a publikus csomag tagok érhetőek el a csomagon kívül. Ahhoz hogy használjunk egy publikus csomag tagot a csomagján kívülről, a következők valamelyikét kell tennünk (vagy akár többet):
A teljes (vagy más néven minősített) nevén keresztül kell hivatkoznunk rá
Importáljuk a csomag tagot
Importáljuk a tag teljes csomagját
Mindegyiket különböző szituációkban alkalmazhatjuk, amelyeket a következő részekben tisztázunk.
Név szerinti hivatkozás egy csomag tagra
Eddig a példákban a típusokra az egyszerű nevükön keresztül hivatkoztunk, mint például Rectangle. Akkor használhatjuk egy csomag tagjának az egyszerű nevét, ha az osztály ugyanabban a csomagban van, mint a tag, vagy ha a tag importálva van.
Ha megpróbálunk használni egy tagot egy másik csomagból, és a csomagot nem importáltuk, akkor a tag teljes nevét használnunk kell. A Rectangle osztály teljes neve:
graphics.Rectangle
A következőképpen használhatjuk a minősített nevet, hogy létrehozzuk a graphics.Rectangle osztály egy példányát:
graphics.Rectangle myRect = new graphics.Rectangle();
Ha minősített neveket használunk, valószínűleg bosszantó lesz, hogy újra és újra be kell gépelni a graphics.Rectangle-t. Ezen kívül rendezetlen és nehezen olvasható programot kapunk. Ilyen esetekben inkább importáljuk a tagot.
Egy csomag tag importálása
Ahhoz hogy importálhassuk a megadott tagot az aktuális fájlban, a fájl elején ki kell adni az import utasítást az osztály vagy interfész definiálása előtt, de a package utasítás után, ha van olyan. Úgy tudjuk importálni a Circle osztályt a graphics csomagból, hogy:
import graphics.Circle;
Most már tudunk hivatkozni a Circle osztályra az egyszerű nevével:
Circle myCircle = new Circle();
Ez a szemlélet akkor működik jól, ha csak néhány tagot használunk a graphics csomagból. De ha sok típusát használjuk egy csomagnak, akkor inkább importáljuk az egész csomagot.
Egy teljes csomag importálása
Ahhoz hogy egy csomagnak az összes típusát importáljuk, az import utasítást a csillag (*) helyettesítő karakterrel kell használnunk:
import graphics.*;
Most már hivatkozhatunk bármelyik osztályra vagy interfészre a graphics csomagból az egyszerű rövid nevével:
Circle myCircle = new Circle();
Rectangle myRectangle = new Rectangle();
Az import utasításban a csillag karakterrel az összes osztályát megadjuk a csomagnak. Nem használhatunk olyan megfeleltetést, amely egy csomagban egy osztály részhalmazára utal. Például helytelen megfeleltetés az, hogy a graphics csomagból az ’A’ betűvel kezdődő összes osztály importáljuk:
import graphics.A*;
Ez az utasítás fordítási hibát generál. Az import utasítással, egy csomagnak egyetlen tagját vagy egész csomagot importálhatunk.
Ugyanígy nem megengedett, hogy egyszerre több csomagot importáljunk, pl.:
import graphics.*.*;
Tehát!
A Java programozási nyelv támogatja az alapvető aritmetikai számításokat az aritmetikai operátorokkal együtt: +, -, *, /, és %.
A java.lang csomagban a Java platform biztosítja a Math osztályt.
Ez olyan metódusokat és változókat biztosít, amik segítségével már magasabb rendű matematikai számítások is elvégezhetők, mit például egy szög szinuszának kiszámítása, vagy egy szám bizonyos hatványra emelése.
A Math osztály metódusai osztálymetódusok, tehát közvetlenül az osztály nevével kell őket meghívni, például így:
Math.round(34.87);
A Math osztály metódusai közül elsőként különböző alapvető matematikai függvényeket nézzük meg, mint például egy szám abszolút értékének kiszámítása vagy egy szám kerekítése valamelyik irányban. A következő lista ezeket a metódusokat tartalmazza:
double abs(double) float abs(float) int abs(int) long abs(long) A paraméterként kapott paraméter abszolút értékével tér vissza.
double ceil(double) A legkisebb double értékkel tér vissza, ami nagyobb vagy egyenlő a paraméterrel, és egyenlő egy egész számmal. (felfelé kerekít)
double floor(double) A legnagyobb double értékkel tér vissza, ami kisebb vagy egyenlő a paraméterrel, és azonos egy egész számmal. (lefelé kerekít)
double rint(double) A paraméterhez legközelebb álló double értékkel tér vissza, és azonos egy egész számmal. (a legközelebbi egészhez kerekít)
long round(double) int round(float) A legközelebbi long vagy int értéket adja vissza, ahogy azt a metódus visszatérési értéke jelzi.
A következő BasicMathDemo program néhány alkalmazási módot illusztrál a fentiekre:
public class BasicMathDemo {
public static void main(String[] args) {
double aNumber = -191.635;
System.out.println("The absolute value of " + aNumber + " is " + Math.abs(aNumber));
System.out.println("The ceiling of " + aNumber +" is "+ Math.ceil(aNumber));
System.out.println("The floor of " + aNumber + " is " + Math.floor(aNumber));
System.out.println("The rint of " + aNumber + " is " + Math.rint(aNumber));
}
}
A program kimenetei:
The absolute value of -191.635 is 191.635
The ceiling of -191.635 is -191
The floor of -191.635 is -192
The rint of -191.635 is -192
További két alapvető metódus található a Math osztályban. Ezek a min és a max. Az alábbi táblázat mutatja be a min és max metódusok különböző formáit, amik két számot hasonlítanak össze, és a megfelelő típusú értékkel térnek vissza.
double min(double, double) float min(float, float) int min(int, int) long min(long, long) A két paraméterből a kisebbel térnek vissza.
double max(double, double) float max(float, float) int max(int, int) long max(long, long) A két paraméterből a nagyobbal térnek vissza.
A MinDemo program mutatja be a min alkalmazását két érték közül a kisebb kiszámítására:
public class MinDemo {
public static void main(String[] args) {
double enrollmentPrice = 45.875;
double closingPrice = 54.375;
System.out.println("A vételár: $" + Math.min(enrollmentPrice, closingPrice));
}
}
A program valóban az alacsonyabb árat adta vissza:
A vételár: $45.875
A Math osztály következő metódusai a hatványozással kapcsolatosak. Ezen kívül megkaphatjuk az e értékét a Math.E használatával.
double exp(double) A szám exponenciális értékével tér vissza.
double log(double) A szám természetes alapú logaritmusával tér vissza.
double pow(double, double) Az első paramétert a második paraméternek megfelelő hatványra emeli.
double sqrt(double) A paraméter négyzetgyökével tér vissza.
A következő ExponentialDemo program kiírja az e értékét, majd meghívja egyenként a fenti táblázatban látható metódusokat egy számra:
public class ExponentialDemo {
public static void main(String[] args) {
double x = 11.635;
double y = 2.76;
System.out.println("Az e értéke: " + Math.E);
System.out.println("exp(" + x + ") is " + Math.exp(x));
System.out.println("log(" + x + ") is " + Math.log(x));
System.out.println("pow(" + x + ", " + y + ") is " + Math.pow(x, y));
System.out.println("sqrt(" + x + ") is " + Math.sqrt(x));
}
}
Az ExponentialDemo kimenete:
Az e értéke: 2.71828
exp(11.635) is 112984
log(11.635) is 2.45402
pow(11.635, 2.76) is 874.008
sqrt(11.635) is 3.41101
A Math osztály egy sor trigonometrikus függvényt is kínál, ezek a következő táblázatban vannak összefoglalva. A metóduson áthaladó szögek radiánban értendők. Radiánból fokká, és onnan visszakonvertálásra két függvény áll rendelkezésünkre: toDegrees és toRadians. Előbbi fokká, utóbbi radiánná konvertál. A Math.PI függvény meghívásával a PI értékét kapjuk meg a lehető legpontosabban.
double sin(double) Egy double szám szinuszával tér vissza.
double cos(double) Egy double szám koszinuszával tér vissza.
double tan(double) Egy double szám tangensével tér vissza.
double asin(double) Egy double szám arc szinuszával tér vissza.
double acos(double) Egy double szám arc koszinuszával tér vissza.
double atan(double) Egy double szám arc tangensével tér vissza.
double atan2(double) Derékszögű koordinátákat konvertál (b, a) polárissá (r, théta).
double toDegrees(double) double toRadians(double) A paramétert radiánná vagy fokká konvertálják, a függvények adják magukat.
A következő TrigonometricDemo program használja a fenti táblázatban bemutatott összes metódust, hogy különböző trigonometrikus értékeket számoljon ki a 45 fokos szögre:
public class TrigonometricDemo {
public static void main(String[] args) {
double degrees = 45.0;
double radians = Math.toRadians(degrees);
System.out.println("The value of pi is " + Math.PI);
System.out.println("The sine of " + degrees + " is " + Math.sin(radians));
System.out.println("The cosine of " + degrees + " is " + Math.cos(radians));
System.out.println("The tangent of " + degrees + " is " + Math.tan(radians));
}
}
A program kimenetei:
The value of pi is 3.141592653589793
The sine of 45.0 is 0.8060754911159176
The cosine of 45.0 is -0.5918127259718502
The tangent of 45.0 is -1.3620448762608377
Megjegyezzük, hogy a NaN akkor jelenik meg, amikor az eredmény matematikailag nem definiált. A Double és a Float osztályok is tartalmazzák a NaN konstanst. Összehasonlítva a visszatérési értéket az egyik ilyen konstanssal, a programunk el tudja dönteni, hogy a visszaadott érték érvényes-e. Ilyen módon a programunk elfogadhatóan tud reagálni, ha egy metódus nem definiált értéket kap.
Az utolsó Math metódus, amiről szót ejtünk, a random. A metódus egy kvázi-véletlen 0.0 és 1.0 közé eső számmal tér vissza. Pontosabban leírva:
0.0 ≤ Math.random() < 1.0
Hogy más intervallumban kapjunk meg számokat, műveleteket hajthatunk végre a függvény által visszaadott értéken. Például, ha egy egész számot szeretnénk kapni 1 és 10 között, akkor a következőt kell begépelnünk:
int number = (int)(Math.random() * 10 + 1);
Megszorozva ezt az értéket 10-el a lehetséges értékek intervalluma megváltozik:
0.0 ≤ szám < 10.0.
1-et hozzáadva az intervallum ismét megváltozik:
1.0 ≤ szám < 11.0.
Végül, az érték egésszé konvertálásával egy konkrét számot (int) kapunk 1 és 10 között.
A Math.random használata tökéletes, ha egy egyszerű számot kell generálni. Ha egy véletlen számsorozatot kell generálni, akkor egy hivatkozást kell létrehozni a java.util.Random–ra, és meghívni ennek az objektumnak a különböző metódusait.
Osztály és csomag
Tartalom:
12.1. Osztály létrehozása
12.2. Adattagok
12.3. Inicializáló blokkok
12.4. Konstruktorok, példányosítás
12.5. Metódusok
12.6. Csomag
12.7. Tesztkérdések
12.8. Feladatok
12.1. Osztály létrehozása
A Java nyelven való programozás az adattagokkal és metódusokkal rendelkező objektumok programozását jelenti. Nem beszélhetünk klasszikus értelemben vett eljárásokról és függvényekről, csak objektumok együttműködéséről, amely a közöttük lévő kommunikációval valósul meg.
Objektumot egy osztály példányosításával hozhatunk létre. Ha nem áll rendelkezésünkre megfelelő osztály, akkor nekünk kell definiálni egyet. Azaz először a "tervrajzot" kell elkészíteni, majd az alapján lehet objektumokat létrehozni.
Az osztálydefiníció általános szintaxisa a következő:
Osztály fej:
[módosítók] class <osztály_neve> [extends <szülő_osztály_neve>] [implements <interfészek_neve>]
Osztály törzs:
{
[adattag deklarációk];
[inicializáló blokkok];
[konstruktor deklarációk];
[metódus deklarációk];
}
Az osztály fejrészének módosítói nemcsak hozzáférési szinteket takarhatnak, hanem opcionálisan egyéb attribútumokat is:
Osztály-fejrész módosítók:
[hozzáférési szint]: public | üres (csomagszintű)
[abstract]: nem példányosítható osztály, amely öröklődés kiindulópontjaként használható;
legalább egy absztrakt metódust tartalmazó osztály kötelező minősítője
[final]: végleges osztály, metódusai nem módosíthatók, az öröklődés okafogyott
Az extends (leszármazott osztály létrehozása) és az implements (interfészek osztályhoz fűzése) kulcsszavak a későbbi fejezetek témáját képezik.
12.2. Adattagok
Egy objektum tulajdonságait (aktuális állapotát) az adattagjainak értékei reprezentálják. Egy adattagnak mindig van azonosítója (neve), valamint típusa, amely lehet primitív típus (pl. egész szám, string, logikai), vagy akár osztálytípus is. Az adattagok a típusuknak megfelelő értékek tárolására szolgálnak, de értéküket az objektum életciklusa során megváltoztathatják (kivéve a konstansokat).
Az adattagok lehetnek példányszintűek, azaz minden objektumpéldányban egyedileg létezők, valamint osztályszintűek, amelyek egy osztályon belül csak egyszer léteznek, és magához az osztályhoz kapcsolódnak. Utóbbi az adattag-definíciót bevezető static kulcsszóval deklarálható.
Egy példányszintű adattag mindig egy objektumhoz tartozik. Ha a deklarációs részben nem adunk kezdőértéket egy adattagnak, a Java automatikusan feltölti a típusának megfelelő "nullaszerű" kezdőértékkel: pl. boolean - false, számok - 0, char - nullás kódú karakter, osztály típusú adattagok - null referencia.
Az adattag neve lehet minden megengedett azonosító, amelyet szokás szerint kisbetűvel kezdünk. Két adattagnak nem lehet azonos neve egy osztályon belül.
Adattagok deklarációja:
[módosítók] <típus> <adattag_neve> [=<kezdőérték>][, ...];
Az adattagok deklarációja az osztálytörzsben, bármilyen konstruktor- ill. metódusdeklaráción kívül történik. A módosítók itt sem kizárólag hozzáférési szinteket takarhatnak, hanem más eszközöket is:
Adattag-deklarációs módosítók:
[hozzáférési szint]: public | protected | üres (csomagszintű) | private
[static]: osztályváltozó deklarálása
[final]: az adattag értéke végleges, konstans
Az alábbi példában definiálunk egy kezdőérték nélküli adattagokkal rendelkező Bankbetét nevű osztályt:
Lássuk ugyanezt az osztályt két kezdőértékadással rendelkező adattaggal definiálva:
A tömörebb kódok elérése miatt megengedett, hogy egy adattag-deklaráción belül több azonos típusú adattagot is megadjunk, megjelölve a típust, majd az egymástól vesszővel elválasztott neveket felsorolva:
A példaprogram forráskódja: Bankbetet.rar.
12.3. Inicializáló blokkok
Az osztály adattagjainak kezdőértékét osztály- ill. példány-inicializáló blokkban is beállíthatjuk. Az inicializáló blokkok speciális, fej nélküli metódusok, melyeket csak a blokk-képző kapcsos zárójelpárok határolnak, és return utasítást sem tartalmaznak. Az osztály-inicializáló blokkot a blokk előtti static kulcsszóval kell jelölni. Fontos tudni, hogy az inicializáló blokk csak egyszer fut le: típusától függően az osztály létrehozásakor, ill. a példányosítások alkalmával egyszer-egyszer példányonként.
12.4. Konstruktorok, példányosítás
Egy osztály példányosítása mindig valamelyik konstruktorának meghívásával történik. A konstruktor egy konkrét objektum életciklusa alatt pontosan egyszer fut le, létrehozva ezzel az objektumot, s beállítva az adattagjainak kezdeti értékét. A konstruktor lefutása után az objektum kész az üzenetek fogadására, feladatának elvégzésére.
A konstruktor neve kötött (mindig megegyezik az őt hordozó osztály nevével), így egy osztálynak csak akkor lehet több konstruktora (konstruktor túlterhelés), ha azok eltérő formális paraméterlistával rendelkeznek. A konstruktor egy speciális, típus nélküli metódusként fogható fel, amelynek nincs visszatérési értéke. Más megfogalmazásban a konstruktor egy - az osztály típusával visszatérő - névtelen metódus.
Egy osztályhoz mindig tartoznia kell legalább egy konstruktornak, hiszen nélküle az osztály nem példányosítható, vagyis nem hozhatók létre az osztály típusának megfelelő objektumpéldányok. Ha nem adunk meg konstruktort, akkor a Java fordító mindig létrehoz egy alapértelmezett, paraméter nélküli konstruktort. Ennek meghívása olyan példányt hoz létre, amelynek adattagjai "nullaszerű" értékekkel rendelkeznek: a numerikus típusok nulla, a karakteres típusok "null", a logikai típusok false értéket vesznek fel. Ha azonban készítünk valamilyen konstruktort, akkor a paraméter nélküli konstruktor "elvész". Így ha mégis szükségünk van rá, definiálnunk kell!
Csak olyan paraméterlistát adhatunk át egy konstruktornak, amelynek megfelelő konstruktort készítettünk, egyébként a fordító hibát jelez.
Konstruktor deklarációja:
[módosítók] <osztály_neve>([<típus> <adattag_neve>[, ...]]) {
[this.]<adattag_neve> = <adattag_neve>[, ...];
}
A metódusokhoz hasonlóan ha egy konstruktorban olyan változó- vagy paraméternevet alkalmazunk, amely egyben az osztály egy adattagjának is az azonosítója, akkor a this kulcsszóval minősítve hivatkozhatunk az adattagra, míg minősítés nélkül a változóra ill. a paraméterre. Figyelem! A this minősítő ezen alkalmazása nem tévesztendő össze a this() alakú konstruktorhívással!
Nézzük az alábbi konstruktorfajtákat!
Az első konstruktor a paraméterek alapján hozza létre az objektumpéldányt, a második esetben nincs paraméterátadás, mégis minden adattag kezdőértéket kap. Az ilyen üres paraméterlistájú konstruktorban a this minősítő felesleges az adattagok elé, mivel ilyenkor nincsenek őket eltakaró lokális nevek vagy paraméterek. A harmadik esetben csak egy paraméterrel hívunk meg egy újabb konstruktorfajtát, a többi paramétert maga a konstruktor állítja be a this([<aktuális paraméterlista>]) - osztályon belüli konstruktorhívást kezdeményező - kulcsszó használatával.
Egy konstruktor meghívása a new kulcsszóval történhet:
Példányosítás:
<osztály_neve> <objektumpéldány_neve>;
<objektumpéldány_neve> = new <osztály_neve>([aktuális paraméterlista]);
vagy
<osztály_neve> <objektumpéldány_neve> = new <osztály_neve>([aktuális paraméterlista]);
A háromféle konstruktor meghívásának módja:
Lássuk a konstruktorhívások eredményeképpen létrejövő objektumok adattagjainak tartalmát is (az osztály toString() metódusának megfelelő módosítása után):
Egy konstruktorból az osztály egy másik konstruktorát, ill. a közvetlen ősosztály egy konstruktorát a this() ill. a super() kulcsszó alkalmazásával érhetjük el.
12.5. Metódusok
Az osztályokhoz tartozó objektumok viselkedését (vagyis az objektumokhoz küldhető üzeneteket) az osztály definíciójában felsorolt metódusok határozzák meg. A metódus egy olyan programrutin, amely egy objektum egy konkrét feladatának algoritmusát valósítja meg.
A Java nyelvben a metódusoknak két nagy csoportját különböztethetjük meg a visszatérési értéküknek megfelelően. Az egyik a visszatérési értékkel nem rendelkező eljárások, míg a másik az ezzel rendelkező függvények csoportja. Függvények esetén meg kell adni a visszatérési érték típusát, míg a másik csoport esetén a void kulcsszó helyettesíti azt.
A metódusdefiníció általános szintaxisa a következő:
Metódus fej:
[módosítók] <típus> <metódus_neve>([formális paraméterlista]) [throws <kivételnévlista>]
Metódus törzs:
{
[lokális változó-deklarációk];
[utasítások];
[return[<kifejezés>]];
}
A metódus fejrészének módosítói nemcsak hozzáférési szinteket takarhatnak, hanem opcionálisan egyéb attribútumokat is:
Metódus-fejrész módosítók:
[hozzáférési szint]: public | protected | üres (csomagszintű) | private
[abstract]: öröklődés céljából készült, üres metódus: nincs metódusblokk (kapcsos zárójelpár),
kifejtésére egy leszármazott osztályban kerül sor, a metódusfejet pontosvessző zárja
[final]: végleges metódus, a leszármazott osztályokban a metódus nem módosítható
[static]: osztálymetódus, csak statikus osztályszintű adattagra és metódusra hivatkozhat
Ha a static kulcsszó nem szerepel a fejrész módosítói között, akkor példánymetódusról van szó, amely példánymetódus példányszintű adattagokra és más példánymetódusokra (összefoglaló néven példánytagokra), valamint nyilvános (public) osztálytagokra (azaz osztályszintű adattagokra és metódusokra) hivatkozhat.
A <típus> a metódus visszatérési értékének típusát határozza meg. Az eljárások visszatérési típusa void, a függvényeké pedig bármilyen primitív típus, vagy hivatkozási típus lehet.
A formális paraméterlistát egy típusokból és szintaktikailag lokális változónak minősülő adattagokból álló párosok alkotják. Egy metódushíváskor az aktuális- és a formális paraméterlisták elemeinek páronként meg kell egyezniük, azaz értékadás szerint kompatibilisnek és páronként megfelelő sorrendűeknek kell lenniük. A Java-ban csak érték szerinti paraméterátadás létezik.
A throws (kivételek továbbküldése) kulcsszó egy későbbi fejezet témája lesz.
Egy metódust a neve és a paraméterlistája azonosít egyértelműen, tehát egy osztályon belül megadható két azonos nevű metódus, ha azok paraméterlistája (szignatúrája) vagy a listában szereplő paraméterek típusaiban, vagy azok sorrendjében, esetleg mindkettőben eltérnek. Hivatkozáskor a futtató környezet a megadott paraméterek típusából és sorrendjéből el tudja dönteni, hogy a két azonos nevű metódus körül melyiket kell végrehajtania. Az így létrehozott szerkezetet a polimorfizmus egyik formájának tekinthetjük (metódusnevek túlterhelése - overload).
Ha egy metódusban olyan változó-, vagy paraméternevet alkalmazunk, amely egyben az osztály egy adattagjának is az azonosítója, akkor a this kulcsszóval minősítve hivatkozhatunk az adattagra, míg minősítés nélkül a változóra ill. a paraméterre.
A metódusok visszatérési értékének típusa a metódus deklarációjakor adható meg. A metóduson belül a return - feltétel nélküli vezérlésátadó - utasítással lehet a visszaadott értéket előállítani. A void-ként deklarált metódusok nem adnak vissza értéket, ezért return utasítást sem szükséges tartalmazniuk. Viszont minden olyan metódusnak, amely nem void-ként lett deklarálva, kötelezően tartalmaznia kell a return utasítást. Sőt, a Java fordító azt is kikényszeríti, hogy return utasítással végződjön minden lehetséges végrehajtási ág. A visszaadott érték adattípusának meg kell egyeznie a metódus deklarált visszatérési értékével. Ezért nem lehetséges pl. egész számot visszaadni olyan metódusból, amelynek visszatérési értéke logikai típusú.
Az alábbi két metódus egyike eljárás, amely eldönti, hogy pozitív összeg-e a bankbetét, a másik pedig egy függvény (a paraméterként kapott egész számmal megnöveli az adó mértékét):
A két metódus meghívása és futásuk eredménye:
Speciális metódus a main metódus, amelyet célszerű az osztályon belül utolsóként deklarálni. Egy alkalmazás végrehajtása során a Java futtatórendszere először mindig meghívja az alkalmazás valamelyik osztályának main metódusát, és ez a metódus fogja az összes többit meghívni.
public static void main(String[] args) {
}
A public módosító biztosítja, hogy a metódus a programon belül bárhonnan elérhető legyen, a static jelzi, hogy osztálymetódusról van szó, és a void kulcsszóból láthatjuk, hogy a metódusnak nincs visszatérési értéke. A main metódusnak egy string-tömb típusú paramétere van, amely a parancssori paramétereket tartalmazza.
12.6. Csomag
A csomag logikailag összefüggő osztály- és interfészdefiníciók gyűjteménye. Hierarchikus felépítésével rendszerezhetjük típusainknak, külön névtereket létrehozva számukra. A csomag elnevezése a package <csomagnév> utasítás segítségével történhet, amelyet a fordítási egység legelső sora kell, hogy legyen.
Ha olyan osztályokat is szeretnénk sokszor használni, amelyek más csomagokban vannak, akkor azokat (az állandó csomagnév hivatkozást elkerülendő) importálni érdemes. Formái:
teljes csomag: import <csomagnév>.*;
csomagon belüli csomag: import <csomagnév>.<belső_csomagnév>.*;
csomag egy osztálya: import <csomagnév>.<Osztálynév>;
Az importáló utasítások kötelezően a csomagdeklarációs sor után következnek. Egy utasításban csak egy osztály (vagy a .*-gal egy teljes csomag) importálható. A Java fordító minden csomaghoz automatikusan hozzáfordítja az alapvető osztályokat (pl. System, String) tartalmazó java.lang csomagot, így ezt nem szükséges külön importálni. Az importálás művelete nem rekurzív, tehát egy teljes csomag importálásakor nem lesznek elérhetők az alcsomagok osztályainak definíciói.
Megadhatunk egy osztályt egy másik osztály tagjaként. Egy ilyen osztályt beágyazott osztálynak hívunk, és a következőképpen néz ki:
class EnclosingClass {
...
class ANestedClass {
...
}
}
A beágyazott osztályokat arra használjuk, hogy kifejezzük és érvényesítsük két osztály között a kapcsolatot. Megadhatunk egy osztályt egy másik osztályon belül, hogyha a beágyazott osztálynak a magába foglaló osztályon belüli környezetben van értelme. Pl. a szövegkurzornak csak a szövegkomponensen belüli környezetben van értelme.
A beágyazó osztály tagjaként a beágyazott osztály kiváltságos helyzetben van. Korlátlan hozzáféréssel rendelkezik a beágyazó osztályok tagjaihoz még akkor is, hogy ha azok privátként vannak deklarálva. Azonban ez a speciális kiváltság nem mindig speciális. A hozzáférést biztosító tagok korlátozzák a hozzáféréseket az olyan osztálytagokhoz, amelyek a beágyazó osztályon kívül esnek. A beágyazott osztály a beágyazó osztályon belül található, ebből kifolyólag hozzáférhet a beágyazó osztály tagjaihoz.
Mint ahogyan más tagokat is, a beágyazott osztályokat is statikusként, avagy nem statikusként lehet deklarálni, ezért ezeket pontosan így is hívják: statikus beágyazott osztály. A nem statikus beágyazott osztályokat belső osztályoknak hívjuk.
class EnclosingClass {
...
static class StaticNestedClass {
...
}
class InnerClass {
...
}
}
Ahogy a statikus metódusok és változók esetén, amelyeket mi osztálymetódusoknak és változóknak hívunk, a statikus beágyazott osztályt a beágyazó osztályával kapcsoljuk össze. Ahogy az osztálymetódusok, a statikus beágyazott osztályok sem hivatkozhatnak közvetlenül olyan példányváltozókra vagy metódusokra, amely az ő beágyazó osztályában van megadva. A példánymetódusok és változók esetén egy belső osztály az ő beágyazó osztályának a példányával kapcsolódik össze, és közvetlen hozzáférése van annak az objektumnak a példányváltozóihoz és metódusaihoz. Mivel egy belső osztályt egy példánnyal társítanak, ezért önmaga nem definiálhat akármilyen statikus tagot.
Hogy a továbbiakban könnyebb legyen megkülönböztetni a beágyazott osztály és a belső osztály fogalmát, érdemes ezekre a következőféleképpen tekinteni: a beágyazott osztály két osztály közötti szintaktikus kapcsolatot fejez ki, azaz szintaktikailag az egyik osztályban levő kód megtalálható a másikon belül. Ezzel ellentétben a belső osztály olyan objektumok közötti kapcsolatot fejez ki, amelyek két osztálynak a példányai. Tekintsük a következő osztályokat:
class EnclosingClass {
...
class InnerClass {
...
}
}
Az e két osztály közötti kapcsolatnál nem az az érdekes, hogy az InnerClass szintaktikusan definiálva van az EnclosingClass-on belül, hanem az, hogy az InnerClass-nak a példánya csak az EnclosingClass-nak a példáján belül létezhet, és közvetlen hozzáférése van a példányváltozók és a beágyazó osztály példánymetódusaihoz.
A beágyazott osztályok mindkét fajtájával találkozhatunk a Java API-n belül, és kell is használni őket. Azonban a legtöbb beágyazott osztály, amelyeket használunk, valószínűleg belső osztály lesz.
Lássunk egy példát
Készítsünk saját osztályt
Ember osztály az adattárolásra és rövidítésre:
package tarsalgo;
public class Ember
{
private int ora;
private int perc;
private int azon;
private String irany;
private boolean be;
public Ember( String[] tomb )
{
ora = Integer.parseInt(tomb[0]);
perc = Integer.parseInt(tomb[1]);
azon = Integer.parseInt(tomb[2]);
irany = tomb[3];
be = tomb[3].equals("be");
}
public int getOra()
{
return ora;
}
public int getPerc()
{
return perc;
}
public int getAzon()
{
return azon;
}
public String getIrany()
{
return irany;
}
public boolean isBe()
{
return be;
}
@Override
public String toString()
{
return "Ember{" + "ora=" + ora + ", perc=" + perc +
", azon=" + azon + ", irany=" + irany + ", be=" + be + '}';
}
}
A main()-t tartalmazó osztály, mely a fájlkezelést és a feladatokat tartalmazza:
package tarsalgo;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Scanner;
public class Tarsalgo
{
public static void main(String[] args)
{
// 1. feladat
Ember[] emberek = null;
try
{
RandomAccessFile raf = new RandomAccessFile("ajto.txt","r");
String sor;
int db = 0;
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
db++;
}
emberek = new Ember[db];
raf.seek(0);
db = 0;
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
emberek[db] = new Ember(sor.split(" "));
db++;
}
raf.close();
}
catch( IOException e )
{
System.out.println("HIBA");
}
// for( Ember e : emberek )
// {
// System.out.println(e);
// }
// 2. feladat
System.out.println("2. feladat");
System.out.println("Az elso belepo: "+emberek[0].getAzon());
int hely = -1;
for( int i = emberek.length-1; i >= 0; i-- )
{
if( !emberek[i].isBe() )
{
hely = i;
}
}
if( hely != -1 )
{
System.out.println("Az utolso kilepo: "+emberek[hely].getAzon());
}
else
{
System.out.println("Senki nem ment ki a tarsalgobol.");
}
// 3. feladat
int max = 0;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() > max )
{
max = emberek[i].getAzon();
}
}
int[] darabok = new int[max+1];
for( int i = 0; i < emberek.length; i++ )
{
darabok[emberek[i].getAzon()]++;
}
try
{
RandomAccessFile ki = new RandomAccessFile("athaladas.txt","rw");
for( int i = 1; i < darabok.length; i++ )
{
ki.writeBytes(i+" "+darabok[i]+"\n");
}
ki.close();
}
catch( IOException e )
{
System.out.println("HIBA");
}
// 4. feladat
System.out.println("4. feladat");
int[] bent = new int[max+1];
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].isBe() )
{
bent[emberek[i].getAzon()]++;
}
else
{
bent[emberek[i].getAzon()]--;
}
}
System.out.print("A vegen a tarsalgoban voltak: ");
for( int i = 1; i < bent.length; i++ )
{
if( bent[i] > 0 )
{
System.out.print(i+" ");
}
}
System.out.println();
// 5. feladat
System.out.println("5. feladat");
int[] bentvannak = new int[emberek.length];
int elozo = 0;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].isBe() )
{
bentvannak[i] = elozo + 1;
}
else
{
bentvannak[i] = elozo - 1;
}
elozo = bentvannak[i];
}
max = 0;
for( int i = 1; i < bentvannak.length; i++ )
{
if( bentvannak[i] > bentvannak[max] )
{
max = i;
}
}
System.out.println("Peldaul: "+emberek[max].getOra()+":"+
emberek[max].getPerc()+"-kor voltak a legtobben a tarsalgoban.");
// 6. feladat
System.out.println("6. feladat");
System.out.print("Adja meg egy szemely azonositojat: ");
Scanner sc = new Scanner(System.in);
int azon = Integer.parseInt(sc.nextLine());
// 7. feladat
System.out.println("7. feladat");
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() == azon )
{
if( emberek[i].isBe() )
{
System.out.print(emberek[i].getOra()+":"+
emberek[i].getPerc()+"-");
}
else
{
System.out.println(emberek[i].getOra()+":"+
emberek[i].getPerc());
}
}
}
System.out.println();
// 8. feladat
System.out.println("8. feladat");
int osszeg = 0;
int be = 0;
int ki = 0;
boolean bentvan = false;
for( int i = 0; i < emberek.length; i++ )
{
if( emberek[i].getAzon() == azon )
{
if( emberek[i].isBe() )
{
be = emberek[i].getOra()*60+emberek[i].getPerc();
bentvan = true;
}
else
{
osszeg += (emberek[i].getOra()*60+emberek[i].getPerc()) - be;
bentvan = false;
}
}
}
// ha a legvegen nem jott ki, akkor az utolso bemenetel
// es a 15:00 kozotti idot hozzaadjuk az ossz idejehez
if( bentvan )
{
osszeg += (15*60)-be;
}
System.out.print("A(z) "+azon+". szemely osszesen "+osszeg+
" percet volt bent");
if( bentvan )
{
System.out.println(", a megfigyeles vegen a tarsalgoban volt.");
}
else
{
System.out.println(".");
}
}
}
Megszámlálásra példa
Az alap feladatot a fenti linken megtalálod, az ott bemeneti adatokat fogom használni.
A feladatot két osztály írásával oldom meg. Először kell egy Hivas osztály, amely a beolvasott adatokat tárolja, és azokból különféle tulajdonságokat számít ki. A tulajdonságokból az óra és másodperc tárolását kihagytam, ennek a feladatnak nincs rá szüksége. Természetesen ha híváshossz vagy valami más számított adatra lenne szükség, akkor azokat is tárolnám a megfelelő helyen.
/**
*
* @author http://webotlet.hu
*/
package webotlet_kombinaltmegszamlalas;
public class Hivas
{
private String szam;
private String ido;
private int ora;
private boolean csucs;
private boolean mobil;
public Hivas(String[] tomb)
{
szam = tomb[0].substring(3);
ido = tomb[1];
ora = Integer.parseInt(ido.split(":")[0]);
csucs = ora >= 8 && ora < 18;
mobil = szam.startsWith("21") || szam.startsWith("31") ||
szam.startsWith("71");
}
public int getOra()
{
return ora;
}
public boolean isCsucs()
{
return csucs;
}
public boolean isMobil()
{
return mobil;
}
}
Akkor jöjjön az osztály, mely a fájlkezelést végzi, megszámolja a megfelelő tulajdonságú objektumokat és kiírja a végeredményt:
/**
*
* @author http://webotlet.hu
*/
package webotlet_kombinaltmegszamlalas;
import java.io.*;
import java.util.ArrayList;
public class Webotlet_KombinaltMegszamlalas
{
public static void main(String[] args)
{
ArrayList<Hivas> hivasok = new ArrayList<>();
String sor;
RandomAccessFile raf;
try
{
raf = new RandomAccessFile( "kombihivasok.csv","r");
raf.readLine();
for( sor = raf.readLine(); sor != null; sor = raf.readLine() )
{
hivasok.add( new Hivas( sor.split(";") ) );
}
raf.close();
// ora: cs, ncs, m, v
// cs - csucsido, ncs - nem csucsido, m - mobil, v - vezetekes
int[][] db = new int[24][4];
int ora;
for( Hivas h : hivasok )
{
ora = h.getOra();
// csucsideju, nem csucsideju
if( h.isCsucs() ) db[ora][0]++;
else db[ora][1]++;
// mobil, vezetekes
if( h.isMobil() ) db[ora][2]++;
else db[ora][3]++;
}
for( int i = 0; i < db.length; i++ )
{
System.out.println( i+". ora: "+db[i][0]+", "+db[i][1]+
", "+db[i][2]+", "+db[i][3] );
}
}
catch( IOException e )
{
System.err.println("HIBA");
}
}
}
----------------
Alap algoritmusok, avagy mindenki tud programozni
A programozással sokszor az a baj – főleg ha kötelező tantárgy és nem szeretjük – hogy gondolkodni kell. Igaz, mondhatnám ezt a matematikára, fizikára is, de egyik tantárgy sem annyira szerteágazó a helyes megoldások tekintetében, mint a programozás. Itt ugyanazt a problémát sokféleképp meg lehet oldani, és minden megoldás helyes. Mégis, a megoldások között az árnyalatnyi különbségek azok, amelyek eldöntik azt, hogy helyes-e a megoldás, vagy sem.
Bármilyen bonyolult programot veszünk szemügyre és bontunk részekre, a végén ugyanaz a 4 építőelem marad:
szekvencia (utasítások egymás utáni sorozatának végrehajtása)
változóhasználat
elágazások
ciklusok
A sorrend nem véletlen, ebben a sorrendben kell ezeket megtanulni használni, mert ezek egymásra épülő darabok a programozásnak nevezett kirakó játékban. Ha nem az építőelemeit nézzük a programoknak, akkor is találhatunk olyan sablonokat, olyan már tanult megoldásokat, amelyek újra és újra előfordulnak a programjainkban. Ezeket a sablonokat, kész megoldásokat nevezzük programozási tételeknek.
Ezek valójában betanulható kész algoritmusok, melyek egy adott problémára kész megoldást adnak. Nem mindig fordulnak elő tiszta formában, vagyis néha apró változtatásokra szükség van, hogy ezeket az algoritmusokat egy adott feladathoz igazítsuk, de ha ezeket ismerjük és biztosan használjuk, akkor sokféle programozási feladatot meg tudunk oldani.
Ezek az alap algoritmusok tömbökhöz kapcsolódnak, vagyis sok egyforma adattal végeznek valamit. Megkeresik egy tömbből a legnagyobb értéket, sorba rendezik a számokat, eldöntik, hogy benne van-e egy adott érték a tömbben, megadják két halmaz metszetét, stb. Lássunk akkor néhány alap algoritmust:
Megszámlálás
Összegzés
Eldöntés
Kiválasztás
Keresés
Minimum/maximum keresés
Rendezés
Kiválogatás
Szétválogatás
Metszet
Unió (hiányzik)
Ezen algoritmusok mindegyikére igaz, hogy ciklusokhoz kapcsolódnak, hiszen ha tömbökkel dolgozunk, akkor mindenképpen ciklusra van szükség, hogy az elemeket egyenként megvizsgálhassuk, összehasonlíthassuk, stb. Ezek az algoritmusok kicsit leegyszerűsítik a programozást, hiszen ezekkel a megtanulható kész receptekkel sokféle feladatot megoldhatunk. A probléma az, hogy a feladatban fel kell ismerni, hogy valójában mit is akarunk eredményként megkapni, és az melyik algoritmusnak felel meg. Ha ez megvan, onnantól szinte csak gépelési feladattá sikerült egyszerűsíteni a programozási feladatot.
Az alap algoritmusok valamennyi fajtájához létezik pszeudokód, olyan általános leírás, amely programozási nyelvtől független. Ráadásul, mivel 3 fajta ciklus létezik, ezért alapból szerteágazó megoldásokat adhatunk ugyanarra a feladatra. Az alap algoritmusokat nagyon sok helyen ugyanazzal a megoldási formával adják meg, és biztos vagyok benne, hogy több tanár csak így fogadja el megoldásként. Én azt vallom, hogy bármilyen jó megoldás elfogadható, a lényeg, hogy a diák alkalmazni tudja azt, amit tanult. Léteznek lecsupaszított, hatékony és egyszerű megoldások, de sokszor én sem azt alkalmazom, mert nem írunk olyan szintű programokat, hogy ennyire optimalizált és gyors algoritmusra lenne szükség. Aki esetleg az alap algoritmusaimban hibát talál, mondván, hogy ő ezt nem így tanulta, az nem feltétlenül hiba, egyszerűen más a megoldás. Az példáknál sok helyen kész ténynek veszem azt, hogy rendelkezésre áll az a tömb a megfelelő adatokkal, amelyekkel dolgozni kell. Ezeknek a tömböknek a feltöltésével, ellenőrzésével nem foglalkozok. Vegyük akkor sorra ezeket az algoritmusokat:
Megszámlálás
Kezdjük valami egyszerűvel. Az alapfeladat az, hogy számoljuk meg, hogy egy adott tömbben hány darab adott tulajdonságú elem van. Ez jelentheti azt is, hogy nincs ilyen tulajdonságú elem a tömbben, akkor a darabszám nyilván 0. Ennél a feladatnál minden esetben végig kell menni a tömbön, hiszen minden elemről meg kell állapítanom, hogy rendelkezik-e a tulajdonsággal, vagy sem. Mivel megszámolunk, ezért valahol tárolnom kell, hogy éppen hol járok a számolásban, hány olyat találtam, ami megfelelt a feltételemnek. Ehhez szükség van egy úgynevezett gyűjtőváltozóra. Az adott algoritmus egy darabszámot ad eredményül minden esetben, ami a [0;méret] intervallumban lesz, vagyis lehet, hogy egy elem sem felel meg a feltételnek, de az is előfordulhat, hogy mindegyik. Nézzünk pár példát, hogy mikor alkalmazható ez az algoritmus:
Hány 180 cm-nél magasabb diák jár az osztályba?
Hány napon esett az eső tavaly?
Hány férfi tanár tanít az iskolában?
Láthatjuk, hogy minden esetben egy darabszámra kíváncsi minden kérdés. Lássuk akkor azt az algoritmust, ami ezekre a kérdésekre választ ad. A példában az első kérdésre keressük a választ.
int szamlalo = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] > 180 )
{
szamlalo = szamlalo + 1;
}
}
System.out.println("Az osztalyba "+szamlalo+" db 180 cm-nel "
"magasabb diak jar.");
Nézzük akkor részletesebben, mi történik.
Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek darabszámát tároljuk.
A gyűjtőváltozót 0 kezdőértékre állítjuk be. Ez egyébként általános szabály, hogy minden gyűjtőváltozót legkésőbb a használata előtt (a ciklus előtt) nullázni kell!
Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
Ha megfelel, a számlálót eggyel megnöveljük.
A ciklus után kiírjuk az eredményt.
A kiemelt sorban a változó növelését kicserélhetjük a már tanult inkrementáló operátorra. Azért, mert lusták vagyunk, és nem akarunk sokat gépelni 🙂
szamlalo = szamlalo + 1;
helyett
szamlalo++;
A többi feladatnál gyakorlatilag ugyanezt kell begépelni, igazából az egyetlen dolog ami változik az maga a feltétel, ami alapján megszámolunk.
Összegzés
Az összegzés tétele kísértetiesen hasonlít a megszámlálásra. Egyetlen különbség van csak, a gyűjtőváltozó növelése. A feladatok is hasonlóak, de az összegzés csak számszerű adatokra vonatkozik. Néhány példa ilyen kérdésekre:
Mennyi a tömbben található páros számok összege?
Mennyi a negatív számok összege?
Mennyi a páratlan számok átlaga?
Lássuk akkor mondjuk az első megoldását:
int osszeg = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
osszeg = osszeg + tomb[i];
}
}
System.out.println("A tombben levo paros szamok osszege: "+osszeg);
Láthatjuk, hogy az összegzés algoritmusa szinte ugyanaz, mint a megszámlálásé.
Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek összegét tároljuk.
A gyűjtőváltozót 0 kezdőértékre állítjuk be.
Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
Ha megfelel, az összeghez hozzáadjuk az aktuális elemet.
A ciklus után kiírjuk az eredményt.
A lényegi különbséget kiemeltem. Látható, hogy szinte ugyanaz. Ettől függetlenül ne keverjük a két algoritmust, mert teljesen más a feladatuk!
A kiemelt sorban a változó növelését kicserélhetjük már tanult összeadással kombinált értékadó operátorra. Ismét csak azért, mert lusták vagyunk, és nem akarunk sokat gépelni.
osszeg = osszeg + tomb[i];
helyett
osszeg += tomb[i];
A harmadik feladat kilóg a többi közül, ez nem csak tiszta összegzés. Itt egyszerre kell az előzőleg ismertetett megszámlálást és összegzést elvégezni. Szükségünk van a páratlan számok összegére, valamint a darabszámára is az átlagoláshoz:
int osszeg = 0;
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
osszeg = osszeg + tomb[i];
db++;
}
}
double atlag = (double)osszeg/db;
System.out.println("A tomb paratlan szamainak atlaga: "+atlag );
Láthatjuk, hogy a ciklussal ugyanúgy végigmegyünk az egész tömbön. Ha találunk egy megfelelő számot, akkor hozzáadjuk az összeghez és növeljük a darabszámot is. Az átlag már csak egy osztás. De nem egyszerű osztás. Az osszeg és db változók egész típusok. Mi lenne az eredménye annak, ha mondjuk az összeg 11 a darabszám pedig 5? 11/5 = ?
Ne felejtsd el! Ha két egész számot osztunk egymással, az egész osztás! Az eredmény nem a sokszor várt 2,2 lenne, hanem 2,0. Az osztás akkor nem egész osztás, ha legalább az egyik műveletben részt vevő szám nem egész. Előzőleg már mutattam egy trükköt, írhatnánk így is:
osszeg/(db+0.0)
Helyette azonban legyünk elegánsabbak, használjunk típuskényszerítést, amit a véletlen számok témakörben már bemutattam:
(double)osszeg/db
A típuskényszerítés során az összeg változóból kiolvasott értéket lebegőpontos számmá alakítjuk, majd osztjuk egy egésszel. Ennek eredménye már megfelelő: 2,2.
Fontos, hogy ez a típuskényszerítés nem az eredeti összegváltozóban tárolt értéket változtatja meg, nincs értékadás! Nem is változtathatja meg az összegváltozó tartalmát, mivel annak típusa egész. Csak a változóból felhasznált értéket alakítja át a megadott típusra.
Eldöntés
Ennél a feladattípusnál azt vizsgáljuk, hogy egy tömbben található-e egy bizonyos tulajdonságú elem. Nem érdekel, hogy hány ilyen elem van, csak az a fontos, hogy van-e benne ilyen. Itt logikai eredményt kapunk, vagyis a válasz igaz vagy hamis lehet. Lássunk pár példát olyan kérdésekre, amelyekre ezzel az algoritmussal kaphatunk választ:
Van-e az osztályban lány?
Van-e az osztályban 190 cm-nél magasabb diák?
Volt-e melegebb 38 foknál tavaly nyáron?
Van-e 30 évnél fiatalabb tanár az iskolában?
Ezekhez a feladatokhoz természetesen szükség van tömbökre, melyek azokat az adatokat tárolják, amelyek között keressük azt a bizonyos tulajdonságú elemet, azok közül is a legelsőt. Emlékezz, nem érdekel hány ilyen elem van, csak az számít, hogy van-e ilyen, és ez nyilván a legelső megtalált elem lesz. Az első példához szükség van egy tömbre, amely a tanulók nemét tárolja, akár logikai típusként (lány – true, fiú – false). A második esetben kell egy tömb, ami az osztályba járó diákok magasságait tartalmazza, a harmadikban egy tömb, ami a nyári napok maximum hőmérsékletét tartalmazza, a negyediknél egy tömb, amiben benne van az iskolában tanító tanárok életkora. Maradjunk a második példánál, és vegyük úgy, hogy rendelkezésre áll egy „tomb” nevű tömb, ami az osztályba járó diákok magasságait rögzíti.
int i = 0;
while( i < tomb.length && tomb[i] <= 190 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("Van az osztalyban 190 cm-nel magasabb diak.");
}
Na de mit is csinál ez pontosan?
Először deklarálunk egy ciklusváltozót, amit arra fogunk használni, hogy indexelhessük (hivatkozhassunk) az egyes tömbelemekre, jelen esetben a diákok magassági adataira. Ez a sorszám természetesen 0-tól indul, mert a Java nyelvben a tömbök indexei 0 számmal kezdődnek.
Aztán indítunk egy ciklust, melynek az a feladata, hogy végigmehessünk egyenként a tömb elemein. A ciklus feje viszont egy összetett feltételt tartalmaz. Ennek első fele azt vizsgálja, hogy végigértünk-e már a tömbön – vagyis, hogy az index kisebb-e, mint a tömb mérete. Ha az i egyenlő lenne a tömbmérettel, az már azt jelentené, hogy túljutottunk az utolsó elemen, tehát a ciklus megáll. Mivel a tömbök indexe 0-val kezdődik, ebből következik, hogy az utolsó elem indexe tömbméret-1. A feltétel másik része a tulajdonság vizsgálat, amelyre csak akkor kerül sor, ha még nem értünk a tömb végére. Itt azt vizsgáljuk, hogy a tomb[i] – vagyis az aktuális diák magassága – NEM RENDELKEZIK a keresett tulajdonsággal. Ez fura, mert nem pont ennek a fordítottját keressük? De igen, ez az algoritmus lényege. Addig kell keresni, amíg NEM találtuk meg, amit kerestünk, hiszen ha megvan, akkor megállhatunk. Ha ez a két feltétel egyszerre igaz (nem értünk még a tömb végére ÉS nem rendelkezik az aktuális diák a keresett tulajdonsággal), akkor lépünk be a ciklusba, ami semmi mást nem csinál, csak lépteti a számlálót, vagyis jöhet a következő vizsgálandó diák. Az algoritmus nagyon fontos része az, hogy a ciklus két feltételének sorrendje kötött! Először kell azt vizsgálni, hogy nem értünk-e a végére, és ha nem, csak akkor szabad megvizsgálni, hogy az aktuális elem nem rendelkezik-e a keresett tulajdonsággal. Hiszen ha már végignéztük a tömböt, akkor már nincs mit vizsgálni.
A ciklus befejeződése után már csak értelmeznünk kell a kapott eredményt. Az i változó értéke az, ami a megoldást tartalmazza. Ha találtunk olyan diákot, aki rendelkezett a keresett tulajdonsággal, akkor a ciklus idő előtt megállt, vagyis az i értéke kisebb, mint a tömb mérete. Ha egyetlen diák sem volt 190 cm-nél magasabb, akkor a ciklus azért állt meg, mert az i változó már nem kisebb a tömb méreténél (vagyis egyenlő), tehát nem találtunk olyat, aki a feltételnek megfelelt volna
Természetesen a többi feladatra is hasonló a megoldás, lássuk mondjuk a negyedik feladatot:
int i = 0;
while( i < tomb.length && tomb[i] >= 30 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("Van az iskolaban 30 evnel fiatalabb tanar.");
}
Nagyon fontos eleme tehát az eldöntésnek, hogy második részfeltételnek azt adjuk meg, hogy az aktuális elem a keresett tulajdonsággal nem rendelkezik! Mivel a feltételek többsége relációt tartalmaz, itt a relációk ellentettjét kell használni!
// 30 évnél fiatalabbat keresünk
while( ... && tomb[i] < 30 )
helyett
// 30 évnél nem fiatalabb kell a feltételbe
while( ... && tomb[i] >= 30 )
Írhatnám úgy is, hogy valóban tagadom az eredeti állítást:
// 30 évnél nem fiatalabb
while( ... && !(tomb[i] < 30)
Az eredeti állítás valódi tagadását tomb[i] < 30 -> !( tomb[i] < 30) én inkább a reláció ellentettjével helyettesíteném, mivel ott egy reláció marad csak, így csak egy műveletet kell végrehajtani. Valódi tagadás esetén ott marad az eredeti reláció, majd a reláció logikai értékének tagadása is kell, ami két művelet, de ezekből az egyik megspórolható. Itt visszautalnék a relációs operátoroknál arra a táblázatra, ahol ismertettem a relációk tagadásait. Ne feledd: a kisebb tagadása nem a nagyobb!
Mi az, amit még észrevehettél ebben az algoritmusban? Ezzel vissza is kanyarodtunk egy nagyon fontos részhez, a logikai kifejezéseknél. Láthatod, hogy a while ciklus fejében egy összetett kifejezés szerepel. Ennek az első fele az, hogy elértünk-e már a tömb végéig, a második pedig az, hogy az aktuális elem nem rendelkezik a keresett tulajdonsággal. Látható, hogy a második feltétel kész tényként veszi azt, hogy ott csak valódi elemet vizsgálhatok. Egy tömbnek, ha emlékszel, fix tulajdonsága a mérete. Vagyis csak akkora indexet lehet használni, amilyen elem még szerepel a tömbben. Egy 10 elemű tömbben nem lehet pl a tomb[12] elemre hivatkozni, mert ilyen elem nem létezik.
Ez futási hibát eredményez. Na de itt hol ellenőrzöm azt, hogy nehogy túl nagy indexet használjak? Az első feltételben. Ez egy logikai rövidzár. Ha az első részfeltétel, hogy az i számláló kisebb, mint a tömbméret (vagyis az i lehet a tömb egy indexe) teljesül, csak akkor vizsgálja meg a második részfeltételt, az adott elem keresett tulajdonságának hiányát. Ha az i elérte a tömbméretet (vagyis nem kisebb), akkor a logikai rövidzár miatt a második feltételt logikai és esetén már meg sem vizsgálja. Nem fog olyan elemet vizsgálni, ami nem létezik! Nagyon fontos eleme az algoritmusnak az, hogy a két részfeltételnek pontosan ilyen sorrendben kell szerepelnie, mert így oldja meg a rövidzár azt az ellenőrzést is, hogy csak valódi emelet vizsgáljunk meg, és ne kapjunk futási hibát.
Kiválasztás
Ezzel az algoritmussal azt adhatjuk meg, hogy egy adott elem pontosan hol szerepel a tömbben. Ez természetesen az adott elem indexét jelenti, amellyel a tömbben hivatkozunk rá. Ez az algoritmus feltételezi azt, hogy az elem tényleg benne van a tömbben, ez ugyanis nem keverendő össze a keresés algoritmusával, amit következőként fogok ismertetni. Lássunk erre egy pár kérdést.
Válasszuk ki a tömbből az 50-es számot (nem index, hanem érték!).
Hányadik a sorban az a diák, akinek a magassága 190 cm-nél nagyobb.
Lássuk az első példa megoldását:
int i = 0;
while( tomb[i] != 50 )
{
i++;
}
System.out.println("Az 50-es szám indexe: "+i);
Ha megnézzük, ez egy lecsupaszított eldöntés algoritmusnak tűnik, amikor ciklusban működési feltételként furcsa módon azt adjuk meg, hogy a ciklus addig menjen, amíg az aktuális elem NEM rendelkezik a tulajdonsággal. Vagyis addig megyünk, amíg meg nem találjuk. Hiányzik viszont a eldöntéses algoritmus összetett feltételének első része, ami azt vizsgálja, hogy túlszaladtunk-e a tömb végén. Itt erre nincs is szükség, mivel abból indultunk ki, hogy a kiválasztandó elem biztosan benne van a tömbben.
Kiválasztásnál lehetséges, hogy több elem is megfelel a feltételnek, ez az algoritmus a legelső olyan elemet választja ki, akire a feltételünk igaz lesz. Viszonylag könnyen megoldható az is, hogy a legutolsó olyat válasszuk ki, ez csak a ciklus haladási irányától és az i kezdőértékétől függ.
Keresés
A keresés algoritmusa gyakorlatilag szinte ugyanaz, mint az eldöntés algoritmusa, mindössze az i változó ciklus utáni értelmezésénél van különbség. Azért szerepeljen itt újra az algoritmus egy konkrét példával. A feladatban azt keressük, hogy van-e 190 cm-nél magasabb diák és hogy ő hányadik a tömbben:
int i = 0;
while( i < tomb.length && tomb[i] <= 190 )
{
i++;
}
if( i < tomb.length )
{
System.out.println("A 190 cm-nél magasabb diák helye: "+i);
}
else
{
System.out.println("Nincs ilyen diák.");
}
Látható az, hogy ez biztonságosabb algoritmus az előzőnél. Ez akkor is használható, ha nem tudjuk, hogy egyáltalán létezik-e ilyen diák, ezért eggyel több a feltétel is, mert azt is figyelni kell, hogy a tömb végén ne szaladjunk túl. A ciklus után pedig az i értékéből határozhatjuk meg a keresett elem helyét, ha ugyanis az i kisebb a tömb méreténél (vagyis nem szaladtunk túl rajta, tehát benne van), akkor az i már a keresett elem helyét jelenti. Ha nem így van, akkor nincs benne. Itt is logikai rövidzárat használunk, tehát a két feltétel sorrendje nagyon fontos. Az első feltétel biztosítja azt, hogy a második nem lehet hibás. Keresési algoritmusból többféle létezik, ez csak a legegyszerűbb lineáris keresés algoritmusa.
Minimum/maximum keresés
Nagyon gyakori feladat az, amikor egy tömbből meg kell határozni a legkisebb/legnagyobb elemet. Ez nem csak egyszerű típusoknál használható, akár objektumok (több tulajdonsággal rendelkező adattárolók) közül is kiválaszthatjuk a legkisebb/legnagyobb tulajdonságút. Technikailag az, hogy a minimum vagy maximum értéket keressük csak egy reláció megfordítását jelenti. Nézzük akkor hogy néz ki ez az algoritmus. Keressük meg a tomb nevű tömbben a legnagyobb értéket!
int max = 0;
for( int i = 1; i < tomb.length; i++ )
{
if( tomb[i] > tomb[max] ) max = i;
}
System.out.println("A tombben levo legnagyobb szam: "+tomb[max]);
Nézzük akkor részenként a programot. Először is deklarálunk egy max nevű változót, amelynek azonnal adunk is egy 0 kezdőértéket. Fontos, hogy ez nem egy változó nullázás, mint a megszámlálás vagy összegzés algoritmusánál tettük. Ennek a 0 értéknek jelentése van. Azt jelenti, hogy a legnagyobb elem a legelső, vagyis a 0 indexű! A max változóban tehát nem a legnagyobb elem értékét, hanem a helyét (indexét) tároljuk. Mindjárt világos lesz, miért. Azt mondjuk tehát, hogy a legnagyobb elem a 0. helyen van, vagyis ez az első elem. Ez teljesen egyértelmű, hiszen amíg meg nem vizsgálom a tömböt, az első elem tekinthető a legnagyobbnak, mivel a többit még nem ismerem. A ciklust, amivel végigmegyek az egész tömbön természetesen a 2. elemtől indul (indexe 1) és a tömbméret-1 indexű az utolsó, amit vizsgálnom kell. Ha az éppen vizsgált elem (tomb[i]) nagyobb, mint az eddigi legnagyobb tomb[max], akkor az új maximum helye megváltozik az aktuálisra -> max = i.
Fura lehet, hogy miért a legnagyobb elem helyét tároljuk és nem az értékét. Mi van akkor, ha ez a kérdés: Hányadik elem a legnagyobb a tömbben? Ha a maximumban a legnagyobb elem értékét tárolnánk, azzal a helyét nem tudjuk megmondani, csak az értékét. A helyéből viszont meghatározhatjuk mindkettőt.
Ha a legkisebb elemet keressük, akkor a kiemelt sorban fordul meg a relációs jel, és máris a legkisebb elemet kapjuk meg a végén. Természetesen minimum keresésnél célszerű a max változó nevét min-re változtatni, hogy utaljon arra, mit is keresek.
Ne felejtsd el tehát, minimum és maximum keresésnél a helyet tároló változó kezdőértéke 0, mivel az első elem lesz először a legkisebb vagy legnagyobb, ha elkezdem a keresést.
Más oka is van annak, hogy a helyet és nem az értéket tároljuk. Tételezzük fel, hogy csak negatív számokat tartalmaz a tömbünk és a legnagyobbat keressük közülük. Létrehozunk egy max változót, azt nullázzuk, de ez most a legnagyobb elem értékét jelentené. Találhatunk negatív számok között olyat, ami nagyobb, mint 0? Könnyen belátható, hogy csak pozitív számokat tartalmaz a tömb és a legkisebbet keressük, akkor sem állja meg a helyét a nullázás. A nulla nem pozitív, tehát nem találsz ettől kisebb pozitív számot, vagyis a tömb egyik eleme sem kerülhet a helyére.
Rendezés
Nagyon gyakori a programjainkban az a típusfeladat, hogy sorba kell rendezni egy tömb elemeit. A Java nyelvben az egyszerű típusokra, és a Stringekre is létezik beépített rendezés, mégis ritkán használjuk őket, mert javarészt objektumokkal fogunk dolgozni, azokra pedig ezek nem működnek. Rendezési algoritmusból nagyon sokféle létezik, vannak egyszerűbb, de lassabb típusok, és vannak nagyon hatékonyak. A valódi helyzet az, hogy a rendezendő adatoktól mennyiségétől is függ az, hogy melyik rendezési algoritmus a hatékony, de középiskolai szinten mindegy hogyan rendezünk, csak oldjuk meg a feladatot. Két rendezési algoritmust fogok megmutatni, amelyeket használni/tanítani szoktam, ha ezeket tudod, akkor bármilyen típusú tömböt rendezni tudsz.
A rendezések legtöbbje összehasonlításokon és cseréken alapul. Összehasonlítunk két elemet, és ha azok sorrendje nem megfelelő, akkor megcseréljük őket. Az algoritmusok sokszor abban különböznek, hogy melyik kettőt hasonlítjuk össze és utána melyik kettőt, stb. Létezik olyan speciális rendezés is, amelyik nem használ összehasonlításokat és cseréket, de ezek csak bizonyos esetekben használhatóak, akkor viszont hihetetlen gyorsak.
A rendezés esetén már összetettebb módon kell bejárni a tömböt, amelynek elemeit rendezni szeretnénk. Itt is igaz az, hogy nem csak egyszerű típusú értékeket tartalmazó tömböket lehet rendezni, az elemek lehetnek összetett objektumok is, melyek többféle típusú értéket tartalmazhatnak.
A tömbök kezelésekor, és az alap algoritmusok használatakor minden esetben ciklusokat használunk arra, hogy bejárjuk az adott tömböt, és annak értékeihez egymás után hozzáférjünk. Abban vannak csak különbségek, hogy ténylegesen bejárjuk-e az egészet, vagy sem, esetleg a bejárás iránya változik. Itt azonban másról lesz szó. Itt találkozunk először az egymásba ágyazott ciklusokkal.
A rendezések, melyeket jellemzően használunk minden esetben azt az elvet követik, hogy a tömb bizonyos elemeit hasonlítják össze, hogy azok egymáshoz képest a kívánt sorrendben helyezkednek-e el. Ha ez nem így van, akkor ezt a két elemet meg kell cserélni. Itt azonban nem csak az egymás melletti szomszédokat vizsgáljuk,
Egyszerű cserés rendezés
Ezt a rendezést több néven is megtalálhatjuk az alap algoritmusok között, én ezt a nevet használom. Az elv, ami alapján dolgozik az az, hogy minden elemet összehasonlít az összes mögötte lévővel, és ha azok sorrendje nem megfelelő, akkor megcseréli őket. Két egymásba ágyazott ciklust igényel, ezeket tradicionálisan i és j ciklusváltozókkal használjuk. Lássuk akkor magát az algoritmust, ahol feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve és a meret nevű változóban a tömb méretét találjuk meg:
1
2
3
4
5
6
7
8
9
10
11
12
13
int csere;
for( int i = 0; i < tomb.length-1; i++ )
{
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[i] > tomb[j] )
{
csere = tomb[i];
tomb[i] = tomb[j];
tomb[j] = csere;
}
}
}
A ciklus úgy dolgozik, hogy a j változó mindig az i utáni helyet jelöl, mivel a j kezdőértéke minden esetben i+1-ről indul. Éppen ezért az i soha nem mehet el a tömb végéig, mert akkor az utolsó elem utáni összehasonlítást is elvégezne, ami mindenképp hibás.
Tehát még egyszer a lényeg: az i van elöl, a j van hátul!
Lássuk a kiemelt részek magyarázatát:
1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
2 – Az i változó soha nem mehet el a tömb végéig, vagyis i < tomb.length-1;
4 – A j mindig az i után áll, ezért int j = i+1;
6 – Mindig összehasonlítjuk az elöl és hátul lévő elemeket, és ha ezek sorrendje nem megfelelő…
8-10 – Akkor jön az elemek cseréje.
A rendezés iránya csak és kizárólag a 6. sorban megadott relációs jeltől függ. Ha az elöl lévő nagyobb és akkor cserélünk, akkor a nagyok kerülnek hátra, vagyis növekvő rendezést alkalmazunk. Ha az elől lévő kisebb és akkor cserélünk, akkor a kicsik kerülnek hátra, és csökkenő rendezést írunk. A fenti példa tehát növekvő rendezést valósít meg, mivel az első esetnek megfelelő a relációs jel.
A csökkenő rendezés ehhez képest tehát minimális változtatással jár:
1
2
3
4
5
6
7
8
9
10
11
12
13
int csere;
for( int i = 0; i < tomb.length-1; i++ )
{
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[i] < tomb[j] )
{
csere = tomb[i];
tomb[i] = tomb[j];
tomb[j] = csere;
}
}
}
Minimum/maximum kiválasztásos rendezés
Ez a rendezés az előző továbbfejlesztett változata. Az előző algoritmus úgy dolgozik, hogy minden esetben megcseréli a két elemet, ha az aktuális két elem helyzete nem megfelelő. Ez azt eredményezi, hogy több csere is lesz, mire a legkisebb a tömb elejére kerül növekvő rendezés esetén. De ha már egyszer növekvő rendezést akarunk megvalósítani, akkor nem lenne jobb, hogy ha először megkeresnénk a legkisebb elemet, majd azt helyeznénk a lista elejére, majd utána megkeresnék a második legkisebbet, azt beraknánk az első után, és így tovább? Jóval kevesebb cserével járna, mint az előző. Természetesen megoldható, az előző rendezési algoritmusa tökéletesen kombinálható a már tanult minimum/maximumkeresési algoritmusokkal. Lássuk akkor hogyan:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int csere;
int min;
for( int i = 0; i < tomb.length-1; i++ )
{
min = i;
for( int j = i+1; j < tomb.length; j++ )
{
if( tomb[j] < tomb[min] )
{
min = j;
}
}
if( min != i )
{
csere = tomb[i];
tomb[i] = tomb[min];
tomb[min] = csere;
}
}
Lássuk akkor a magyarázatot:
1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
2 – Kell egy változó, ahol a legkisebb elem helyét tároljuk (mint a minimumkiválasztásnál), de ennek itt még nem adunk kezdőértéket.
5 – Mielőtt elkezdjük a belső ciklust, ami az elöl lévő elem mögöttiek indexén megy végig, az elöl lévő elemet feltételezzük a legkisebbnek. Itt a belső ciklus futását gyakorlatilag egy minimum kiválasztásnak írtuk meg. A tomb[i] az első elem, ezért ennek a helyét feltételezzük a legkisebb elem helyének,
8 – majd, ha az eddigi minimumtól valamelyik mögötte lévő (tomb[j]) tőle kisebb,
10 – akkor a hátul lévő elem helyét (j) jegyezzük meg, mint aktuális legkisebbet.
13 – Ha a belső ciklussal végeztünk, akkor a min változóban benne van a hátul lévő elemek közül a legkisebbnek a helye. Ha ez a hely nem egyenlő az elöl lévővel (vagyis nem önmaga a legkisebb), akkor találtunk az elöl lévő (i) elem mögött tőle kisebbet, melynek helyet a min változóban tároljuk.
15-17 – Ebben az esetben a két elemet (i és min helyen lévőket) megcseréljük.
Ezt az algoritmust inkább csak érdekességképp mutattam meg, érettségire tökéletesen elég, ha az egyszerű cserés rendezést megtanulod, mert csak az a követelmény, hogy rendezni tudj, teljesen mindegy, melyik algoritmussal. Nyilván a legegyszerűbbet célszerű megtanulni, a hatékonyság nem követelmény.
Kiválogatás
Szintén az alap algoritmusok közé tartozik az a feladattípus, amikor bizonyos tulajdonságnak, vagy tulajdonságoknak megfelelő elemeket kell egy tömbből egy másik tömbbe kiválogatni. Tegyük fel, van egy egészeket tartalmazó tömbünk, melyet a [-9;9] intervallumból töltöttünk fel. Hogyan oldhatjuk meg, hogy ebből a tömbből egy másik tömbbe kigyűjtjük a negatív számokat? Minden esetben létre kell hozni egy másik tömböt, amibe a megfelelő elemeket másoljuk. De mekkora legyen ez a tömb? Ez az ami alapvetően meghatározza, hogy milyen megoldási módot alkalmazunk. Kétféle esetet különböztetünk meg:
Létrehozunk egy eredeti tömbnek megfelelő méretű tömböt, azt feltételezve, hogy akár az összes elem lehet negatív, így mindet át kell másolni. Ha azonban nem minden elem negatív, akkor az új tömbben maradnak üres helyek, ahova nem rakunk át semmit. Így nyilván kell tartanunk, hogy hány elemet másoltunk át az új tömbbe, és mennyi maradt “üresen” a végén.
Megoldhatjuk úgy is, hogy először megszámoljuk, hogy hány elem felel meg a feltételnek, ami alapján a kiválogatást el akarjuk végezni, és az új tömböt pontosan akkorának állítjuk be. Így a megoldás végén az új tömbben csak azok az elemek lesznek benne, amelyeket mi helyeztünk el benne.
A két megoldásból a második nyilván picivel több munkával jár, mert kapcsolódik hozzá egy megszámlálás is, viszont utána már nem kell attól tartanunk, hogy az eredmény tömbben olyan elem is előfordul, ami nem felel meg a kiválogatás feltételének.
Lássuk akkor a két különböző megoldást. Mindkét esetben feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve. Az új tömbbe a páratlan számokat szeretnénk kiválogatni:
1
2
3
4
5
6
7
8
9
10
11
int[] paratlan = new int[tomb.length];
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
paratlan[db] = tomb[i];
db++;
}
}
Lássuk akkor a kiemelt sorok magyarázatát:
1 – Létrehozok egy ugyanakkora tömböt, mint az eredeti, lehetőséget adva arra, hogy akár minden elemet kiválogathassak.
3 – Létrehozok egy db nevű változót, ami jelen esetben az első üres helyet fogja tárolni, ahova a következő kiválogatott elemet elhelyezhetem, a kiválogatás végeztével pedig tárolni fogja, hogy az új tömbbe hány elem került bele.
4 – Végigmegyek az eredeti tömbön,
6 – és ha az eredeti tömbben páratlan számot találunk,
8 – akkor az új tömbben a első üres helyre (db) elhelyezem az elemet,
9 – majd megnövelem a db-ot, hogy az esetleges következő átmásolt elem ne írja felül az előzőt.
Látható, hogy nem olyan bonyolult algoritmusról van szó, a kulcs az, hogy mindig tárolom egy változóban, hogy hol van az új tömbben az első üres hely, mert csak oda rakhatok bele a kiválogatás során elemeket. A gond csak annyi, hogy ha van egy 1000 méretű tömböm, amibe 3 elemet kellene csak kiválogatni, akkor is a memóriában foglalja az 1000 elemnyi helyet a 3 kedvéért.
Lássuk akkor a másik megoldást:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
db++;
}
}
int[] paratlan = new int[db];
db = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 != 0 )
{
paratlan[db] = tomb[i];
db++;
}
}
Ha jól megnézed nem sokkal bonyolultabb, picit többet kell gépelni, és ki kellett egészíteni a megszámlálás alap algoritmusával:
1-8 – Megszámoljuk, hány elemet kell majd kiválogatni az új tömbbe.
10 – Létrehozunk egy ugyanakkora tömböt.
12-20 – Ez pedig pontosan az első megoldás.
Az egész algoritmus kulcs momentuma a db változó használata! Ennek több szerepe is van. Először a kiválogatandó elemek darabszámát gyűjtjük bele, utána a következő üres helyet jelöli az új tömbben, végül a kiválogatás végeztével az új tömb méretét jelenti, bár ezt a tömbből úgyis ki lehet nyerni a .length változóból.
Szétválogatás
A szétválogatás algoritmusa a kiválogatás kibővítése. Az alapfeladat az, hogy az eredeti tömb minden elemét két külön tömbbe kell elhelyezni. Feltételezzük, hogy minden elem bekerül valamelyik új tömbbe, vagyis nem hagyunk ki semmit sem. A kiválogatásnál ennek a feladatnak a felét gyakorlatilag megoldottuk. Amit egy kiválogatásnál kiválogatunk, az itt az egyik tömb elemeinek felelne meg. Az összes többi elemet a másik tömbbe pakoljuk. Így már nem is tűnik olyan nehéznek, igaz?
A szétválogatás feltétele minden esetben gyakorlatilag egyetlen feltétel.
Válogassuk szét a tömb elemeit 5-től nagyobb és nem nagyobb elemekre. (emlékezz a relációs jelekre!)
Válogassuk szét a tömb elemeit 5-tel osztható és nem osztható elemekre.
Válogassuk szét az elemeket egyjegyű és nem egyjegyű számokra
Válogassuk szét a tömb elemeit páros és páratlan elemekre.
Ha megfigyelted, a feladatok jó része úgy fogalmazza meg a feltételt, hogy szétválogatjuk valamilyen és NEM valamilyen elemekre. Egy feltétel és annak az ellentettje minden elemet le kell hogy fedjen. Ezért szétválogatás, nem maradhat ki egyetlen elem sem. És az utolsó esetben? Amelyik szám nem páros, az páratlan, tehát ez is lefed minden számot.
A szétválogatásnál is ugyanaz a dilemma lesz először, mint amit a kiválogatásnál írtam:
Nem foglalkozok az új tömbök méreteivel, a legrosszabb esetből indulok ki, hogy minden elemet be kell tennem az egyik tömbbe, a másik pedig üres marad. Ebben az esetben mindkét új tömb méretének az eredeti tömb méretét állítom be, így a két új tömb kétszer annyi helyet foglal majd, amennyire valóban szükség lenne.
Előre megszámolom, hány elem felel meg a szétválogatás feltételének, ezután beállítom a kívánt tömbméreteket, majd utána válogatom szét az elemeket. Ez a legtakarékosabb megoldás, mert mindkét tömb mérete pontosan akkora lesz, amekkorára szükségem lesz. Ha emlékszel, a kiválogatásnál itt egy megszámlálással bővítettem ki az alap megoldást.
Lássuk akkor az első esetet. Tételezzük fel, hogy van egy adott méretű tömböm, feltöltve elemekkel. Válogassuk szét az elemeket páros és páratlan elemeket tartalmazó tömbökbe. Vedd észre, hogy ez valójában egyetlen feltétel. Ami nem páros, az páratlan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int[] paros = new int[tomb.length];
int[] paratlan = new int[tomb.length];
int dbparos = 0;
int dbparatlan = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
paros[dbparos] = tomb[i];
dbparos++;
}
else
{
paratlan[dbparatlan] = tomb[i];
dbparatlan++;
}
}
Ha a kiválogatás algoritmusát megértetted, akkor ezzel se lesz probléma. Nem véletlenül csak két részt emeltem ki. A kiválogatásnál kellett egy számláló, amelyben nyilvántartottam, hogy hány elemet válogattam ki, ami egyúttal azt is jelezte, hogy hol van az új tömbben a következő üres hely. Itt is hasonló a helyzet, csak itt két tömb esetén két külön változóban kell tárolni, hogy hány elem van az egyikben-másikban, és ezáltal melyik tömbben hol van a következő üres hely, ahova az elemeket pakolhatom. A belső feltétel sem sokat változott, ha a feltételnek megfelel az elem, akkor berakom az egyik tömbbe, ha nem, akkor mindenképpen (else) a másik tömbbe kell tennem. Emlékszel: minden elem bekerül valamelyik tömbbe, ha nem az elsőbe, akkor a másodikba, nem hagyhatok ki semmit sem.
Ne felejtsd el, a két új tömb mérete nagyobb, mint amennyi tényleges elemet tartalmaznak. Az algoritmus után a két darabszámot tároló változó az, amiből megtudhatod, hogy mekkora valójában a tömb, amit kezelned kell. Nem a paros.length lesz az a határ, ameddig be kell járnod egy ciklussal, hanem a dbparos változó.
Lássuk akkor a második megoldást. Emlékeztetőül: megszámolom hány elemet kell majd beraknom az egyik tömbbe, akkor meglesznek a megfelelő tömbméretek.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int parosdb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
parosdb++;
}
}
int[] paros = new int[parosdb];
int[] paratlan = new int[tomb.length-parosdb];
parosdb = 0;
paratlandb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] % 2 == 0 )
{
paros[parosdb] = tomb[i];
parosdb++;
}
else
{
paratlan[paratlandb] = tomb[i];
paratlandb++;
}
}
Lássuk akkor a kiemelt részeket:
1-9 – Megszámolom, hány elem felel meg a szétválogatás feltételének.
11-12 – Létrehozom a két megfelelő méretű tömböt. A páratlan tömb méretét úgy kapom meg, hogy a tömb elemeinek darabszámából kivonom a párosok darabszámát, így megvan a páratlanok száma.
14-31 – Lenullázom a két számlálót, és elvégzem a szétválogatást az első megoldásnak megfelelően, csak itt már biztos lehetek benne, hogy mindkét új tömböt teljesen feltöltöm.
Az előzőhöz képest ez nyilván bonyolultabb megoldás. Cserébe takarékosabb, másrészt nem kell külön tárolni, hogy a tömbök valójában meddig vannak feltöltve, mivel a méretük pontosan megfelel a szétválogatott elemek darabszámának.
És ha nem mindent válogatok szét?
Ez az algoritmus csak abban az esetben használható, ha minden elemet szét kell válogatni. Ez mondjuk a szétválogatás elvéből is következik, mivel nem hagyhatunk ki elemeket, különben nem szétválogatásnak neveznénk. Mégis a példa kedvéért tételezzük fel, hogy egy tömbből szeretnénk a pozitív és negatív számokat két másik tömbbe átpakolni. Ebben az esetben már figyelnünk kell arra, hogy mi a helyzet a nullákkal. Természetesen ezt is meg kell oldani, csak itt az elemek megszámolásánál figyelembe kell venni, hogy kihagyunk elemeket, valamint a tényleges válogatásnál is ügyelni kell rájuk. Szándékosan kerültem a szétválogatás szót, mert ez valójában a kihagyott elemek miatt nem az lesz. Lássunk akkor erre egy példát.
Válogassuk ki egy tömb elemei közül a pozitív és negatív számokat. (Észrevetted? Kiválogatás)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int pozitivdb = 0;
int negativdb = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] > 0 )
{
pozitivdb++;
}
else if( tomb[i] < 0 )
{
negativdb++;
}
}
int[] pozitiv = new int[pozitivdb];
int[] negativ = new int[negativdb];
pozitivdb = 0;
negativdb = 0;
for( int i = 0; i < tomb.length; i++ ) { if( tomb[i] > 0 )
{
pozitiv[pozitivdb] = tomb[i];
pozitivdb++;
}
else if( tomb[i] < 0 )
{
negativ[negativdb] = tomb[i];
negativdb++;
}
}
1-13 – Egy ciklusban megszámolom a pozitív és negatív számokat.
15-16 – Létrehozom nekik a megfelelő méretű tömböket.
És kiválogatom őket egyetlen ciklusban.
Ez gyakorlatilag két kiválogatás egy ciklusba pakolva, a két feltételnek (pozitív vagy negatív) lényegében semmi köze egymáshoz, a számlálóik is teljesen függetlenek, mert nem tudom, hogy a két feltétel lefedi-e az összes eredeti elemet vagy sem. Ha a két feltétel minden elemet besorol valahova, akkor szétválogatás, egyébként két egymástól független kiválogatásról beszélünk.
Metszet
A metszet algoritmus egy kis magyarázatot igényel. Az alap algoritmusok metszetképzése nem egyezik meg a halmazelméletben tanult metszettel. A halmazt elemek sokaságának tekintjük, ahol az elemeknek nincs sorrendje, és minden elem csak egyszer szerepelhet a halmazban. Ez a tömböknél nyilvánvalóan nem áll fenn. A halmazoknál metszetként azon elemek halmazát vesszük, amelyek mindkét halmazban megtalálhatóak.
Tömbök esetén ez azt jelenti, hogy az egyik tömbből vesszük azokat az elemeket, amelyek benne vannak a másikban. Ezzel az algoritmussal csak az a bajom, hogy nem mindegy, hogy melyik tömb oldaláról kezdjük ez a dolgot. Lássuk a következő példát, hogy miről is van szó.
{2,2,3,4}
{3,5,2,6,6}
Ha az első tömb elemeiből hagyjuk meg azokat, amelyek benne vannak a másodikban, akkor ezt az eredményt kapjuk:
{2,2,3}
Ha a második tömb elemeiből hagyjuk meg azokat, amelyek benne vannak az elsőben, akkor ezt az eredményt kapjuk:
{3,2}
Nyilván látszik mi a gond. Ez pedig abból fakad, hogy egy elem többször is lehet egy tömb eleme. A sorszámozás miatt ezek egyértelműen megkülönböztethetőek. A halmazban viszont az elemek nem sorszámozottak, ezért két azonos értékű elemet nem különböztethetnénk meg. Az algoritmus nem foglalkozik ezzel a problémával, és nekünk sem kell. Más kérdés, hogy meg tudnánk oldani azt is, hogy minden elem egyszer szerepeljen csak a metszetben, később ezt is megmutatom.
Mint már fent említettem, az algoritmus annyiból áll, hogy az vesszük az egyik tömb elemei közül azokat, amelyek benne vannak a másikban. Nézzük meg jobban, mi is ez? Kiválogatjuk az egyik tömb elemei közül azokat, amelyek megfelelnek annak a feltételnek, hogy benne vannak a másik tömbben. Kiválogatás, amiben van egy eldöntés. A metszetképzés tehát két tanult algoritmus kombinációja.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int[] t1 = new int[] {2,2,3,4};
int[] t2 = new int[] {3,5,2,6,6};
int[] metszet = new int[t1.length];
int j;
int db = 0;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < t2.length && t2[j] != t1[i] )
{
j++;
}
if( j < t2.length )
{
metszet[db] = t2[j];
db++;
}
}
Lássuk a kiemelt részek magyarázatát:
3 – A metszet tömb mérete akkora, mint az első tömb mérete, hiszen lehet, hogy annak minden eleme megtalálható a másikban. Természetesen a kiválogatáshoz hasonlóan itt is ügyelni kell arra, hogy nem feltétlen kerül minden elem a metszet tömbbe, ezért majd a db változó fogja tárolni a metszet tömb valódi elemeinek számát.
7 – Ebben a sorban elkezdünk egy kiválogatást, vagyis elindulunk az első tömbön azt keresve, hogy ezek közül melyiket kell majd átrakni a metszetbe.
9-14 – Ez gyakorlatilag az eldöntés algoritmusa, addig haladunk a második tömb elemein, és addig megyünk, amíg nem találunk egyezést a második tömb eleme és az első tömb éppen aktuális eleme között. Ezt az algoritmust most nem magyaráznám el újra, de ami a lényeg: ha az elemet megtaláltuk, akkor visszatérünk a kiválogatáshoz
16-17 – Ha találtunk olyan első tömbbeli elemet, ami megfelelt a feltételünknek (benne van a másodikban is), akkor berakjuk a metszet tömbbe, és növeljük a számlálóját. Ez a kiválogatás algoritmus vége.
Metszet egyedi elemekkel
Mi van akkor, ha valóban csak annyit szeretnénk megtudni, hogy mik azok a számok, melyek mindkét tömbben megtalálhatóak? Ha valami többször szerepel a tömbben, attól mint szám csak egyszer szerepel. Ez nem alap algoritmus, hanem az eddig tanultakat kell alkalmazni. Akár teljesen eltérő megoldásokat is adhatunk:
A két tömb közül az elsőből létrehozok egy olyan tömböt, ami az eredetiben szerepelő számokat csak egyszer tartalmazza. Majd ha erről az oldalról metszetet képzek, akkor a metszetben is minden elem csak egyszer fog szerepelni.
Az első tömbből csak akkor teszek be egy számot a metszetbe, ha benne van a másodikban, és még nincs benne a metszetben. Vagyis a kiválogatáson belül két eldöntésre van szükségem, melyeknek egyszerre kell teljesülnie. Azzal még finomíthatom, hogy ha a második tömbben nincs benne, akkor felesleges a metszetben ellenőrizni, mert akkor oda semmiképpen nem kerülhetett be.
Lássuk az első megoldást:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int[] t1 = new int[] { 2, 2, 3, 4 };
int[] t2 = new int[] { 3, 5, 2, 6, 6 };
int[] metszet = new int[t1.length];
int[] egyedi = new int[t1.length];
int dbe = 0;
int j;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < dbe && t1[i] != egyedi[j] )
{
j++;
}
if( j == dbe )
{
egyedi[dbe] = t1[i];
dbe++;
}
}
int db = 0;
for( int i = 0; i < dbe; i++ )
{
j = 0;
while(j < t2.length && t2[j] != egyedi[i])
{
j++;
}
if( j < t2.length )
{
metszet[db] = t2[j];
db++;
}
}
Mit is csinálunk pontosan?
5 – Létrehozom azt a tömböt, ahova kiválogatom az első tömb számait. Ennek mérete az eredetivel megegyező, mert lehet, hogy egyik szám sem szerepel többször, akkor mindet át kell pakolni.
6 – Létrehozok egy számlálót, hogy nyilvántartsam, valójában hány elem lesz az egyedi tömbben.
8-21 – Kiválogatom az egyedi számokat. (kiválogatásban egy eldöntés) Fontos, hogy akkor rakom bele az egyedi tömbbe a számot, ha az eldöntés hamis eredményt ad, vagyis nincs benne: if( j == dbe )
23-36 – Ez pedig a metszetképzés algoritmusa, de az egyedi tömb és a második között. A 24-es sorban fontos a feltétel, hogy az egyedi tömbnek nem az összes elemét kell vizsgálni, hanem csak addig, ameddig valóban vannak benne elemek. Ezt a saját dbe számlálója tárolja.
A két részfeladat (egyedi tömb előállítása, majd metszetképzés) ugyanarról a tőről fakad, hiszen mindkét esetben egy elemről akarom eldönteni, hogy benne van-e egy tömbben. A különbség csak az, hogy egyedi elemek válogatásakor akkor rakom bele, ha nincs még benne, metszetképzésnél pedig akkor rakom bele, ha benne van.
Nézzük a másik megoldást, amikor a két eldöntést teszek a kiválogatásba:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int[] t1 = new int[] { 2, 2, 3, 4 };
int[] t2 = new int[] { 3, 5, 2, 6, 6 };
int[] metszet = new int[t1.length];
int j;
int jm;
int db = 0;
for( int i = 0; i < t1.length; i++ )
{
j = 0;
while( j < t2.length && t2[j] != t1[i] )
{
j++;
}
if( j < t2.length )
{
jm = 0;
while( jm < db && metszet[jm] != t1[i] )
{
jm++;
}
if( jm == db )
{
metszet[db] = t1[i];
db++;
}
}
}
Lássuk a lényegi részeket:
10-14 – Eldöntjük, hogy az első tömb eleme benne van-e a másodikban.
15 – Ha igen, akkor
15-27 – Eldöntjük, hogy benne van-e a metszetben.
22 – Csak akkor tesszük be a metszetbe, ha még nincs benne. Ha már egyszer betettünk ilyen számot, akkor nem tesszük bele még egyszer.
Ez a megoldás talán rövidebb és egyszerűbb is, mint a másik, és minden esetben egyedi elemeket tartalmazó metszet tömböt kapunk.
Természetesen ez a metszetképzés algoritmus több hasonló feladatnál is használható, hiszen ha metszetet tudunk képezni, akkor olyan kérdésekre is választ kaphatunk ennek segítségével, hogy van-e két tömbnek azonos eleme, hány közös eleme van két tömbnek, stb.
Komplex feladat
Lássunk egy komplexebb feladatot. Adott egy 10 elemű tömb melyet véletlen számokkal töltöttünk fel a [-9;9] intervallumból. Írjuk ki növekvő sorrendben a tömbben szereplő páros számokat.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
*
* @author http://webotlet.hu
*/
package webotlet_alapalg_komplex;
public class Webotlet_alapalg_komplex
{
public static void main(String[] args)
{
int[] tomb = new int[10];
for (int i = 0; i < tomb.length; i++)
{
tomb[i] = (int) (Math.random() * 19) - 9;
}
for (int i = 0; i < tomb.length; i++)
{
System.out.print(tomb[i] + " ");
}
System.out.println();
int db = 0;
for (int i = 0; i < tomb.length; i++)
{
if (tomb[i] % 2 == 0)
{
db++;
}
}
int[] paros = new int[db];
db = 0;
for (int i = 0; i < tomb.length; i++)
{
if (tomb[i] % 2 == 0)
{
paros[db] = tomb[i];
db++;
}
}
int csere;
for (int i = 0; i < db - 1; i++)
{
for (int j = i + 1; j < db; j++)
{
if (paros[i] > paros[j])
{
csere = paros[i];
paros[i] = paros[j];
paros[j] = csere;
}
}
}
for (int i = 0; i < db; i++)
{
System.out.print(paros[i] + " ");
}
System.out.println();
}
}
Ez egy tökéletes feladat arra, hogy az eddig tanultakat összefoglalja. Sok ismerős részletet láthatunk benne, de lássuk akkor részenként:
12-17 – Adott méretű tömb létrehozása, majd feltöltése véletlen számokkal.
19-22 – A kisorsolt tömb kiíratása.
24 – Sordobás a sorsolt tömb kiíratása után, hogy ne folyjon egybe majd a rendezett tömb kiíratásával.
26-33 – A kiválogatáshoz megszámoljuk, hány elemet kell majd átrakni az új tömbbe.
35 – Létrehozzuk az új tömböt.
37-45 – Kiválogatjuki (átmásoljuk) a páros számokat az új tömbbe.
47-59 – Rendezzük az új tömböt.
61-64 – Kiírjuk a kiválogatott és rendezett új tömböt.
66 – Egy bónusz sordobás a végére, hogy ha bővíteném a programot, akkor az új kiíratás új sorban kezdődjön.
Adott tehát egy elsőre bonyolultnak tűnő feladat, amit szétbontottuk olyan részekre, melyeket már külön-külön meg tudunk oldani. Ezeket a kész megoldásokat (tömb feltöltés, kiíratás, megszámlálás, kiválogatás, rendezés, stb) megfelelő sorrendben hibátlanul összerakjuk, és kész a feladat teljes megoldása. Ugye így jobban belegondolva nem is olyan nehéz? Feltéve hogy az eddigi tananyagokat már készségszinten alkalmazni tudod. Sokszor az a legnehezebb feladat, hogy felismerjük azt, hogy az aktuális feladat milyen kisebb alkotóelemekre bontható, melyekre már kész megoldásaink vannak. Ha ez a részekre bontás megy, akkor gyakorlatilag sokszor gépelési feladattá tudjuk egyszerűsíteni a feladatok nagy részének megoldását.
A feladat így szol: a program beker egesz szamokat, mig -1-et nem olvas, es kiirja a -1 elotti szamok atlagat! Az eredmenyt ket tizedesjegyre kerekiti. (A bemenet mindig egesz szam.)
Scanner sc = new Scanner(System.in);
double n = 0;
double bekert;
double atlag;
System.out.println(“Kérem a számokat (-1-re kilép):”);
bekert = sc.nextInt();
while (bekert != -1) {
n += bekert;
bekert = sc.nextInt();
}
if (bekert == -1) {
// atlag = na ez az a resz, ahol nem jovok ra a helyes kepletre, noha tudom hogy kell atlagot szamolni
System.out.print(“Az összeg: “+atlag+”.”);
} else {
System. out.print(“Az összeg: 0.0”);
}
}
}
Ez nagyon hasonlo a te atlagolos feladatodhoz, de valahogy megsem jovok ra, hogyan kellene megoldani. Nagyon megkoszonom, ha segitesz benne egy kis extra magyarazattal.
Megoldás;
int szam;
int osszeg = 0;
int db = 0;
Scanner sc = new Scanner(System.in);
do
{
szam = sc.nextInt();
if( szam != -1 )
{
osszeg += szam;
db++;
}
}
while( szam != -1);
if( db == 0 )
{
System.out.println(“Nem adtal meg szamot.”);
}
else
{
System.out.println((double)osszeg/db);
}
Fontos!
A lényeg, hogy ha a ciklusban nem -1 számot olvasol be, akkor gyűjteni kell a bekért számokat egy összegváltozóba, a darabszámukat meg egy darabba. Ebből tudsz összeget számolni, ha szükséges.
Az összegváltozód megvan, de nem számolod a beolvasásokat, ezért nem tudsz átlagot számolni.
Nincsenek megjegyzések:
Megjegyzés küldése