PROGRAMOZÁSI TÉTELEK. Java nyelven. Informatika Szakközépiskolai képzés. Nagy Zsolt

PROGRAMOZÁSI TÉTELEK Java nyelven

Informatika Szakközépiskolai képzés

Nagy Zsolt

2015

Programozási tételek

10 – 11. évfolyam

Tartalom Programozási tételek, algoritmusok ....................................................................................................................... 3 Feldolgozás végjelig ............................................................................................................................................ 3 Egy sorozathoz egy érték rendelése........................................................................................................................ 4 Megszámlálás tétele ........................................................................................................................................... 4 Összegzés tétele ................................................................................................................................................. 5 Átlagszámítás tétele ........................................................................................................................................... 6 Eldöntés tétele .................................................................................................................................................... 7 Kiválasztás tétele ................................................................................................................................................ 9 Gyakorlás .......................................................................................................................................................... 10 Minimum- / Maximum-kiválasztás ................................................................................................................... 12 Keresés tétele ................................................................................................................................................... 13 Lineáris keresés: rendezetlen sorozatban ........................................................................................................ 16 Lineáris keresés: rendezett sorozatban ............................................................................................................ 18 Bináris keresés .................................................................................................................................................. 19 Egy sorozathoz egy sorozat rendelése .................................................................................................................. 22 Másolás ............................................................................................................................................................. 22 Kiválogatás ........................................................................................................................................................ 23 Egy sorozathoz több sorozat rendelése ................................................................................................................ 24 Szétválogatás .................................................................................................................................................... 25 Gyakorlás (másolás, kiválogatás, szétválogatás) .............................................................................................. 28 Rendezések, rendezettség .................................................................................................................................... 28 Rendezettség .................................................................................................................................................... 28 Minimum-kiválasztásos rendezés ..................................................................................................................... 30 Maximum kiválasztásos rendezés..................................................................................................................... 34 Gyakorlás .......................................................................................................................................................... 34 Buborék rendezés ............................................................................................................................................. 41 Beszúrásos rendezés ......................................................................................................................................... 45 Rendezések összehasonlítása ........................................................................................................................... 46 Minimum-kiválasztásos rendezés ................................................................................................................. 46 Buborék rendezés ......................................................................................................................................... 46 Javított Buborékos rendezés ......................................................................................................................... 46 Beszúró rendezés .......................................................................................................................................... 46 Gyorsrendezés .............................................................................................................................................. 47 Kupacrendezés.............................................................................................................................................. 47 Halmazműveletek ................................................................................................................................................. 47 Metszetképzés tétele........................................................................................................................................ 49 Unióképzés tétele ............................................................................................................................................. 52

1. oldal



Különbség-képzés tétele ................................................................................................................................... 54 Rekurzió ................................................................................................................................................................ 56 Rekurzív függvények ......................................................................................................................................... 56 Rekurzív és iteratív forma ................................................................................................................................. 58 Gyorsrendezés (QuickSort) ............................................................................................................................... 60 Felhasznált és ajánlott irodalom ........................................................................................................................... 62

2. oldal



Programozási tételek, algoritmusok Az algoritmus különböző feladatok megoldására szolgáló utasítások jó szervezett együttesét jelenti. Jellemzői: véges, determinisztikus, teljes. Az informatikai programozási tételek olyan alap algoritmusokat jelentenek, amelyek különböző típusfeladatok általános megoldásait adják. Ezeket kis átalakítással alkalmazhatjuk egy konkrét feladat megoldása során. Fajtái: 

sorozathoz érték rendelése,



sorozathoz sorozat rendelése,



sorozathoz több sorozat rendelése,



több sorozathoz egy sorozat rendelése.

Feldolgozás végjelig Egy feladat többszöri végrehajtása során, az ismétlések meghatározására három eset különböztethető meg: 

végtelen számú ismétlés  nincs leállító feltétel



meghatározott számú ismétlés  a leállító feltétel az adott érték meghaladása



feltételtől függő ismétlés  végfeltétel alkalmazása.

Az utóbbi két esetben beszélhetünk végjelről, vagy végértékről. Ez a végjel fogja leállítani a feldolgozást. A végjelet sosem dolgozzuk fel. Fontos, hogy a végjelnek választott érték, ne essen a feldolgozandó adatok értelmezési tartományába. Alapvetően előfeltételes ciklussal szokás megoldani. Ugyanis lehetővé kell tenni, hogy már az első alkalommal végjelet kapunk, és nem a sorozat első értékes elemét. Az alapelv a következő: A ciklus előtt beolvassuk az első adatot (lehet végjel is), majd előfeltételes ciklus feltételében megvizsgáljuk, hogy nem végjel-e. Amennyiben nem, feldolgozzuk az adatot, majd újra beolvasást alkalmazunk. Abban az esetben, ha végjelet kapunk (ez lehet az első eset is), vége az ismétlésnek. A ciklust követő utasítással folytatjuk a programot.

3. oldal



Algoritmus: be: Adat amíg Adat<>Végjel ismétel Az adat feldolgozása be: Adat avége

Feladat: Kérjük be egy kör sugarát, és számítsuk ki a kör területét és kerületét. A bekérést addig végezzük, amíg a felhasználó nullát nem ad meg.

Egy sorozathoz egy érték rendelése Az algoritmus egy sorozatot dolgoz fel és egy értéket ad vissza.

Megszámlálás tétele Adott egy N elemű A tömb. A feladat az, hogy számoljuk meg, hány T tulajdonságnak megfelelő A(i) értéke van a tömbnek. Az A tömb elemek sorozatát tartalmazza. Az i értéke az A tömb i. sorszámú értékét hivatkozza. A T(A(i)) tulajdonság (logikai függvény) egy {igaz, hamis} értéket ad vissza, attól függően, hogy az A tömb i. értéke teljesíti-e a kitűzött feltételt. A darabszámot egy Db változóban gyűjtjük. A legegyszerűbb esetben a sorozat (A tömb) minden elemét megszámoljuk. Algoritmus: Db := 0 Ciklus i := 1-től N-ig Ha T(A(i)) akkor Db := Db + 1 Ciklus vége Ki: Db

Feladat: Kérjünk be számokat nulla végjelig, majd határozzuk meg a darabszámot. Feladat: Határozzuk meg, hogy adott két szám között hány hárommal osztható szám van. Pascal: szam MOD 3 = 0 Java: szam % 3 == 0

Feladat: Határozzuk meg, hogy adott két szám között hány prímszám van. Egy szám akkor prímszám, ha csak 1-el és önmagával osztható maradék nélkül. Az osztást elég a szám négyzetgyökéig végezni.

4. oldal



Java kód: package primek; public class Primek { public static void main(String[] args) { //2000-től 20001-ig keressük meg a prímszámokat! int primekszama = 0; for (int n = 2000; n <= 20001; n++) { int i = 2; double sq = Math.sqrt(n); while ((n%i != 0) && (i <= sq)) { i++; } if (i > sq) { primekszama++; //Kiíratásnál csak 15 számot írunk egy sorba. if (primekszama % 15 != 0){ System.out.print(n+", "); } else { System.out.println(); System.out.print(n+", "); } } } System.out.println(""); System.out.println("Primek száma 2000 és 20000 között: " +primekszama+" darab."); } }

Összegzés tétele Határozzuk meg egy számsorozat összegét. A számsorozatot egy N elemű A tömb tartalmazza. Algoritmus: S := 0 Ciklus i := 1-től N-ig S := S + A(i) Ciklus vége Ki: S

A sorozat összegét az S változó fogja tartalmazni, amit az összegzés előtt nullázni kell. A sorozat elemein (az A tömbön), az i változó segítségével megyünk végig. Feladat: Olvassunk be számokat nulla végjelig, majd írjuk ki a számok összegét. Az összegzéshez hasonló művelet még: A(i) elemek esetén, ahol A, a számokat tartalmazó tömb, i = {1..N} természetes szám, az A tömb elemszáma. 

a szorzat számítás: A(i)*A(i+1)*…*A(N-1)*A(N), 5. oldal





számtani közép (átlag) számítás: (A(i)+A(i+1)+…+A(N-1)+A(N)) / N



mértani közép: N√(A(i)*A(i+1)*…*A(N-1)*A(N)) N. gyök alatt egy szorzat

Feladat: Számítsuk ki egy adott n nemnegatív egész szám faktoriálisát (n!). Java-kód: package faktorialis; import java.util.Scanner; public class Faktorialis { public static void main(String[] args) { Scanner be = new Scanner(System.in); System.out.println("Faktoriális"); System.out.print("Szám: "); int szam = be.nextInt(); int n; //-1 végjelig folytatjuk while(szam != -1){ if(szam < 0) System.out.println("Csak nemnegatív számnak van faktoriálisa!"); else { n = fakt(szam); System.out.println(szam+" faktoriálisa: "+n); } System.out.print("Szám: "); szam = be.nextInt(); } } //Faktoriálist számító metódus public static int fakt(int sz){ int n = 1; if(sz == 0) return 1; else{ while(sz > 0){ n *= sz; sz--; } return n; } } }

Átlagszámítás tétele Átlagszámításkor egyszerre kell elvégezni a megszámlálást és az összegképzést, majd elosztani az összeget a darabszámmal. Viszont az átlagszámítást csak abban az esetben szabad végrehajtani, ha volt átlagolandó adat, különben nullával osztanánk!

6. oldal



Feladat: Határozzuk meg két felhasználótól bekért szám közötti páros / páratlan számok átlagát.

Eldöntés tétele Az eldöntés tételével egy adott tulajdonságú elem meglétét akarjuk bizonyítani. Adott egy N elemű A tömb. Továbbá adjunk meg egy olyan T tulajdonságot (logikai függvényt), amely {igaz} értékkel jelzi, ha az A tömbnek van ilyen eleme. A T logikai függvény tehát akkor ad vissza {igaz} értéket, ha az A tömb 1..N elemei között találunk megfelelő elemet. Algoritmus: i := 1 Ciklus i := Ciklus Ki: (i

amíg (i <= N) és nem T(A(i)) i + 1 vége <= N)

Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i <= N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). A visszatérési érték akkor lesz igaz, ha nem értük el tömb végét (i <= N). Feladat: Döntsük el, hogy egy szavakat tároló tömbben van-e olyan szó, amely palindróma (tükörszó). Java: String str; str.equals((new StringBuilder(str)).reverse().toString()); Feladat: Kérjünk be egész számokat nulla végjelig, és határozzuk meg, hogy van-e közöttük négyzetszám. Egy egész szám pontosan akkor négyzetszám, ha négyzetgyöke (létezik, és) egész. Minden négyzetszám nemnegatív.1 Tízes számrendszerben a négyzetszámok a következő végződésűek lehetnek: 00, 1, 4, 6, 9 vagy 25 a következő szabályok szerint: 

Ha a szám utolsó számjegye 0, akkor a négyzete 00 végződésű és az azt megelőző számjegyek is négyzetszámot alkotnak.

1

https://hu.wikipedia.org/wiki/Négyzetszámok

7. oldal

Programozási tételek 


Ha a szám utolsó számjegye 1 vagy 9, akkor a négyzete 1-re végződik és az azt megelőző számjegyek 4-gyel osztható számot alkotnak.



Ha a szám utolsó számjegye 2 vagy 8, akkor a négyzete 4-re végződik és az azt megelőző számjegyek páros számot alkotnak.



Ha a szám utolsó számjegye 3 vagy 7, akkor a négyzete 9-re végződik és az azt megelőző számjegyek 4-gyel osztható számot alkotnak.



Ha a szám utolsó számjegye 4 vagy 6, akkor a négyzete 6-ra végződik és az azt megelőző számjegyek páratlan számot alkotnak.



Ha a szám utolsó számjegye 5, akkor a négyzete 25-re végződik.

Java-kód: package negyzetszam; import java.util.Scanner; import java.lang.Math; public class NegyzetSzam { public static void main(String[] args) { Scanner be = new Scanner(System.in); int szam; System.out.println("Írj be egy számot, megmondom nényzetszám-e!"); System.out.print("Szám = "); while((szam = be.nextInt()) != 0){ if(isNegyzetSzam(szam)) System.out.println("Négyzetszám"); else System.out.println("Nem négyzetszám"); System.out.print("Szám = "); } } //logikai függvény public static boolean isNegyzetSzam(int sz){ int e; double d; if(sz >= 0){ d = Math.sqrt(sz); e = (int) Math.round(d); return (e * e == sz); } else { return false; } } }

8. oldal



Kiválasztás tétele A kiválasztás tételével keresünk egy adott T() tulajdonsággal rendelkező elemet, vagy annak az indexét (helyét a sorozaton belül). Tudjuk, hogy a tömbnek van T() tulajdonságú eleme. A sorozatot egy N elemszámú A tömb reprezentálja. A T() függvény {igaz} értéket ad, ha a sorozat i. eleme adott tulajdonságú. Algoritmus: i := 1 Ciklus i := Ciklus Ki: i,

amíg nem T(A(i)) i + 1 vége A(i)

A visszatérési érték tehát az A tömb i. eleme, vagy annak A(i) értéke. Feladat: 70 és 200 között melyik az első 9-cel osztható szám. (Kilenccel osztható a szám, ha a számjegyek összege osztható 9-cel.) Java-kód: package oszthatokilenc; public class OszthatoKilenc { public static void main(String[] args) { System.out.println("A program 70 - 200 között megkeresi " + "az első 9-cel osztható számot."); for(int i = 70; i<= 200; i++){ if(isOszthatoKilenc(i)){ System.out.println("Az első kilenccel osztható szám: "+i); break; } } } public static boolean isOszthatoKilenc(int szam){ int m, ossz = 0; while(szam != 0){ m = szam % 10; szam /= 10; ossz += m; } return (ossz % 9) == 0; } }

Feladat: Határozzuk meg egy számtani sorozat mediánját (középértékét).

9. oldal



Véges elemszámú sokaság esetén a medián a sorba rendezett adatok közül a középső érték; vagy másképpen: a medián az az érték, amely a sorba rendezett adatokat két egyenlő részre osztja. Ha a sokaság elemeinek száma páratlan, akkor az iménti meghatározás egyértelmű, mert akkor van egy középső adat, amely előtt ugyanannyi adat van, mint utána. Páros számú elem esetén két középső adat van, ez esetben a kettő közti bármelyik érték mediánnak tekinthető. A gyakorlatban a két érték számtani közepét szokták megadni.2 

Páratlan elemszám esetén: 1254314334351 A rendezett sokaság: 1112333344455 A medián a középső elem: 1112333344455



Páros elemszám esetén: 1424235311 A rendezett sokaság: 1112233445 A medián a középső elemek számtani közepe: 2,5.

Gyakorlás Feladat: Határozzuk meg két szám legnagyobb közös osztóját. Leírás:3 Két (nem egyszerre nulla) egész szám közös osztói közül a lehetséges legnagyobb nem nulla pozitív egész, amely mindkét egész számot (maradék nélkül) osztja. Az euklideszi algoritmus egy számelméleti algoritmus, mellyel két szám legnagyobb közös osztója határozható meg. Legyen:

2 3

https://hu.wikipedia.org/wiki/Medián Forrás: http://hu.wikipedia.org/wiki/Euklideszi_algoritmus

10. oldal



Az algoritmus első lépésében maradékosan osztjuk

-t

-vel, a második lépésben

-t a

maradékkal, majd az előbbi maradékot az új maradékkal, és így tovább, mindig az osztót a maradékkal. Így a következő lépéssorozatot kapjuk:    

ahol

A maradék véges sok lépés után nulla lesz, hiszen amíg nem nulla, addig minden lépésben legalább eggyel csökkenni fog, tehát az utolsó lépésnél:

A keresett legnagyobb közös osztó az

, azaz az utolsó nem nulla maradék.

Példa: A 360 és a 225 legnagyobb közös osztójának meghatározása az euklideszi algoritmussal:

Tehát a legnagyobb közös osztó a 45. Java-kód: package lnkoeuklidesz; import java.util.Scanner; public class LnkoEuklidesz { public static void main(String[] args) { Scanner be = new Scanner(System.in); System.out.println("LNKO meghatározása"); System.out.print("első szám: "); int szam1 = be.nextInt(); System.out.print("második szám: "); int szam2 = be.nextInt(); int kozos = lnko(szam1, szam2); if(kozos > 0) System.out.println("A két szám közös osztója:"+kozos);

11. oldal



else System.out.println("A két számnak nincs közös osztója."); } //0 visszatérési érték jelzi, hogy nincs közös osztó. public static int lnko(int szam1, int szam2){ int m; if(szam1 < szam2){ //szam1 és szam2 megcserélése kizáró vagy művelettel (^) szam1 = szam1 ^ szam2; szam2 = szam1 ^ szam2; szam1 = szam1 ^ szam2; } //Az osztó nem lehet nulla. if(szam2 == 0) return 0; // szam1 >= szam2 m = szam1 % szam2; while(m != 0){ szam1 = szam2; szam2 = m; m = szam1 % szam2; } return szam2; } }

Feladat: Számoljuk meg, hogy egy életkorokat tartalmazó tömbben hány 10 évnél fiatalabb, tizenéves, huszonéves, … ember adata van. Feladat: Olvassunk be osztályzatokat 0 végjelig, és számoljuk meg, hogy hány ötös, négyes, hármas, kettes, illetve egyes volt közöttük.

Minimum- / Maximum-kiválasztás Minimum-kiválasztás esetén egy A sorozat legkisebb, maximum-kiválasztásnál a legnagyobb elemét A(i) kell meghatározni. Minimum-kiválasztásnál az algoritmus lényege, hogy az elemeket sorban megvizsgáljuk nem kisebb-e, mint az addigi legkisebbnek tartott elem. Ha találtunk egy kisebb elemet, akkor megjegyezzük. Induló minimális elemnek, vagy a sorozat első elemét A(1) vesszük, vagy egy olyan értéket, amitől a sorozat minden eleme csak kisebb lehet A(i) < MIN, ahol i a sorozat elemeinek indexe, i  1..N.

12. oldal



Algoritmus: MinIndex := 1 Ciklus i := 2-től N-ig Ha A(i) < A(MinIndex) akkor MinIndex := i Ha vége Ciklus vége Ki: MinIndex, A(MinIndex)

Feladat: Generáljunk véletlen számokat, amelyek egy téli hónap éjszakai hőmérsékleti értékeit jelentik. (pl. -20..-5) Határozzuk meg a leghidegebb értéket, és azt, hogy ez hányadik napja volt a hónapnak! (Véletlen szám 0-15-ig mínusz 20.) Java-kód: package leghidegebb; import java.util.Random; public class LegHidegebb { public static void main(String[] args) { Random rnd = new Random(); int [] honap = new int [30]; //véletlen számok generálása -20..-5 for(int i = 0; i < honap.length; i++){ honap[i] = rnd.nextInt(16)-20; } //hőmérsékletek kiíratása System.out.print("A hónap hőmérsékleteti: "); for(int i = 0; i < honap.length; i++) System.out.print(honap[i]+", "); System.out.println(""); //leghidegebb nap kiválasztása int mini = 0; for(int i = 1; i < honap.length; i++ ){ if(honap[i] < honap[mini]) mini = i; } System.out.println("A leghidegebb nap: "+mini); System.out.println("A leghidgebb hőmérséklet: "+honap[mini]); } }

Keresés tétele Adott egy N elemű A tömb, valamint egy T() tulajdonság (logikai függvény). Döntsük el, hogy van-e az A tömbnek T tulajdonságú eleme. Ha van, adjuk meg az elemet, vagy az elem tömbbeli indexét! Algoritmus: i := 1

13. oldal



Ciklus amíg (i <= N) és nem T(A(i)) i := i + 1 Ciklus vége Ha (i <= N) akkor Ki: i, A(i) különben Ki: hamis Elágazás vége

Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i <= N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). Ha nem értük el tömb végét (i <= N), akkor találtunk T tulajdonságú elemet, így ezt, illetve ennek indexét adjuk vissza, egyéb esetben hamis logikai értékkel tér vissza. Feladat: A felhasználótól bekért számsorozatban melyik volt és hányadik az első 6-tal osztható szám. (Hattal osztható egy szám, ha osztható 2-vel és 3-mal is.) Nulla végjelig! Java-kód: package kereses6oszthato; import java.util.Scanner; public class Kereses6Oszthato { public static void main(String[] args) { Scanner be = new Scanner(System.in); System.out.println("Keressük az első hattal osztható számot!"); System.out.print("szám: "); int szam = be.nextInt(); // !((szam % 2 == 0) && (szam % 3 == 0)) --> //(szam % 2 != 0) || (szam % 3 != 0) // 0-ra kilépés while(((szam % 2 != 0) || (szam % 3 != 0)) && (szam != 0)){ System.out.print("szám: "); szam = be.nextInt(); } //Miért hagytuk el a ciklust? if(szam != 0) System.out.println("Az első hattal osztható szám: "+szam); else System.out.println("Nem adtunk meg hattal osztható számot!"); } }

Feladat: A felhasználótól bekért számsorozatban melyik volt és hányadik az első 5-tel osztható szám. (Öttel osztható egy szám, ha utolsó helyen 0 vagy 5 számjegy áll.)

14. oldal



Feladat: A felhasználótól bekért számsorozatban melyik volt és hányadik az első 25-tel osztható szám. (Huszonöttel osztható, ha az utolsó két helyen 0 áll, vagy ha az utolsó két számjegy osztható 25-tel.) Feladat: A felhasználótól bekért számsorozatban melyik volt és hányadik az első 9-cel osztható szám. (Kilenccel osztható a szám, ha a számjegyek összege osztható 9-cel.) Java-kód: package oszthato; import java.util.Scanner; public class Oszthato { public static void main(String[] args) { Scanner be = new Scanner(System.in); int szam, sorszam = 0; boolean megvan = false; System.out.println("Melyik és hányadik az első kilencel osztható szám?"); System.out.print("Szám = "); szam = be.nextInt(); while((szam != 0) && !megvan){ if(isOszthatoKilenc(szam)){ sorszam++; megvan = true; System.out.println("A(z) "+sorszam+". szám: "+szam+" osztható" + " kilencel."); } else{ sorszam++; System.out.print("Szám = "); szam = be.nextInt(); } } if(!megvan) System.out.println("Eddig nem volt 9-cel osztható szám."); } //kilencel osztható, ha a számjegyek összge osztható kilencel private static boolean isOszthatoKilenc(int sz){ int ossz = 0; while(sz != 0){ ossz += sz % 10; sz = sz / 10; } return ossz % 9 == 0; } }

15. oldal



Lineáris keresés: rendezetlen sorozatban Adott N elemszámú sorozatban keressük a T() tulajdonsággal rendelkező elemet. Az elemeket sorban, a sorozat elejétől egyesével vizsgáljuk. Mivel a sorozat a kereső tulajdonság szerint nincs rendezve, ezért nem tudjuk benne van-e a keresett elem, és hol. A keresést leállító feltétel kétféle lehet: 

Egy elemet tartalmaz a sorozat, akkor az elem megtalálásáig, vagy, ha nincs benne, akkor a sorozat végéig keresünk.



Több elem esetén, ha szükségünk van minden elemre, akkor szintén a sorozat végéig kell keresni. Amennyiben nincs szükség minden elemre, akkor általában az első elem megtalálása után vége a keresésnek.

A lineáris keresést hívják még szekvenciális keresésnek is. Az összehasonlítások száma N elem estén minimum 1, maximum N, átlagban (N+1)/2. Az, hogy a keresett elem nincs benne a sorozatban, csak az utolsó összehasonlítás után derül ki. Algoritmus: változó I, Hely:egész változó Adat: ElemTípus változó Talált: logikai I:=1 Ciklus amíg (I<=N) és (A[I]<>Adat) ismétel I:=I+1 Ciklus vége Talált := I<=N Ha Talált akkor Hely:=I Ha vége

Feladat: Generáljunk véletlen számokat -20 °C és +35 °C között, majd keressük meg benne az első olyan hőmérsékletet, amelyiket a felhasználótól kértük be. Java-kód: package lineariskeresesrendezetlen; import java.util.Scanner; import java.util.Random; public class LinearisKeresesRendezetlen { public static void main(String[] args) { Random rnd = new Random(); Scanner be = new Scanner(System.in); //Véletlen számok generálása -20..+35.

16. oldal



int tomb[] = new int[20]; for(int i = 0; i < tomb.length; i++) tomb[i] = rnd.nextInt(56)-20; //lista System.out.println("A tömb elemei:"); for(int i = 0; i < tomb.length; i++) System.out.print(tomb[i]+", "); System.out.println(""); //mit keressek System.out.print("Kérem a számot, amit meg kell keresnem: "); int szam = be.nextInt(); //keresés int i = 0; while((i < tomb.length) && (tomb[i] != szam)) i++; //miért hagytuk el a tömböt if(i < tomb.length) System.out.println("Benne van, helye: "+ (i+1)+"."); else System.out.println("Nincs benne!"); } }

Futási kép: run: A tömb elemei: 5, -17, 12, 14, 22, 1, 20, 20, 8, -20, 1, 21, 13, -20, 4, -19, 15, 29, -16, 33, Kérem a számot, amit meg kell keresnem: 1 Benne van, helye: 6. BUILD SUCCESSFUL (total time: 3 seconds)

A pirossal szedett részt nézzük meg alaposabban! Annak az eldöntését, hogy egy elem benne van-e a sorozatban, a ciklusból kilépve kell megvizsgálni. Logikusabbnak gondolhatnánk a vizsgálatot, ha a tömb adott elemét a bekért számmal hasonlítanánk össze. A következő módon: //miért hagytuk el a tömböt if(tomb[i] == szam) System.out.println("Benne van, helye: "+ (i+1)+"."); else System.out.println("Nincs benne!");

Helyes eredményt kapunk, ha a keresett elem benne van a sorozatban. Amennyiben a keresett elem nincs benne, hibajelzést kapunk. Futási kép: A tömb elemei: 17. oldal



3, -8, 7, 17, -8, 12, -19, -15, 12, 14, -16, 28, 27, -13, -20, 15, -14, 31, -2, 5, Kérem a számot, amit meg kell keresnem: 40 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20 at lineariskeresesrendezetlen.LinearisKeresesRendezetlen.main(Line arisKeresesRendezetlen.java:38) Java Result: 1 BUILD SUCCESSFUL (total time: 5 seconds)

Gondoljuk végig a ciklus működését! Mivel nincs benne a keresett elem a sorozatban, ezért végig keresünk. A ciklus utolsó lépésében a ciklusváltozó értéke nagyobb, mint a tömb elemszáma (i > tomb.length). Ez pedig túlindexelést eredményez, és hibát generál!

Lineáris keresés: rendezett sorozatban A sorozatnak rendezettnek kell lenni. Az előzőhöz képest növeli a hatékonyságot, hogy akkor is leáll a keresés, ha nagyobb elemre lépünk, mint a keresett érték. Algoritmus: változó I, Hely:egész változó Adat: ElemTípus változó Talált: logikai I:=1 Ciklus amíg (I<=N) és (A[I]
Feladat: Generáljunk 20 véletlen egész számot, az 5..50 tartományból. Rendezzük nagyság szerint, majd keressünk meg benne egy felhasználó által megadott számot. Java-kód: package lieariskeresrendezett; import java.util.Scanner; import java.util.Random; // tömbökkel kapcsolatos metódusok, pl. rendezések import java.util.Arrays; public class LiearisKeresRendezett { public static void main(String[] args) { // Deklarációk Scanner be = new Scanner(System.in); int [] tomb = new int [20]; // tömb feltöltése véletlen számokkal feltoltVeletlen(tomb); 18. oldal



// tömb listázása rendezés előtt System.out.println("A véletlen számok rendezés előtt:"); lista(tomb); // tömb rendezése Arrays.sort(tomb); // tömb listázása rendezés után System.out.println("A véletlen számok rendezés után:"); lista(tomb); // szám bekérése System.out.print("Mit keressek: "); int szam = be.nextInt(); // keresés rendezett tömbben // ha nincs benne az eredmény -1, egyébként az index int eredmeny = keres(tomb, szam); if(eredmeny < 0) System.out.println("Nincs benne!"); else System.out.println("A keresett elem indexe: "+eredmeny); } // tömb feltöltését elvégző metódus 5..50 közötti számokkal public static void feltoltVeletlen(int[] t){ Random rnd = new Random(); for(int i = 0; i < t.length; i++){ t[i] = rnd.nextInt(46)+5; } } // tömb listázása public static void lista(int[] t){ for(int i = 0; i < t.length; i++){ System.out.print(t[i]+", "); } System.out.println(""); } // keresés a tömbben, ha -1 nincs benne, egyébként az index public static int keres(int[] t, int sz){ int i = 0; while((i < t.length) && (t[i] < sz)) i++; if((i < t.length) && (sz == t[i])) return i; else return -1; } }

Az Arrays osztályban sok tömbökön dolgozó metódus van definiálva, pl. a rendezések különböző típusú adatokon.

Bináris keresés Adott egy N elemű, rendezett A sorozat. Keressük meg benne az X értéket!

19. oldal



A keresés maximális időigénye log2(N), N az elemszám, ezért nevezik a keresést logaritmikus keresésnek. Minél nagyobb az elemszám, annál jobban megmutatkozik az algoritmus hatékonysága. Például 1024 elemszámnál log2(1024)=10, azaz maximum 10 lépésen belül megvan az elem vagy kiderül, hogy nincs benne. Algoritmus: Logaritmikus(be:tömb[1..N], be:keresett, ki: sorszám) Deklaráció alsó, felső: egész Logaritmus kezdet alsó:=1 felső:= N Ciklus sorszám:= (alsó + felső) DIV 2 Ha keresett > tömb[sorszám] akkor alsó:= sorszám + 1 Ha vége Ha keresett < tömb[sorszám] akkor felső:= sorszám – 1 Ha vége Mígnem (tömb[sorszám] = keresett) VAGY (alsó > felső) Ciklus vége Ha alsó > felső akkor sorszám := -1 Ha vége Logaritmikus vége

Fontos megérteni, hogy ez az általános algoritmus a végfeltételes ciklusnál kilépési feltételt fogalmaz meg. Az általunk használt Java nyelv végfeltételes ciklusa pedig belépési feltételt használ. De-Morgan azonosságok, amennyiben szükséges: 

nem (a és b) = (nem a) vagy (nem b),



nem (a vagy b) = (nem a) és (nem b)

Feladat: Töltsünk fel egy tömböt véletlen számokkal, majd keressünk meg benne egy felhasználó által megadott számot. package binariskereses; import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class BinarisKereses { public static void main(String[] args) { 20. oldal



System.out.println("Bináris keresés feladat."); int[] tomb = new int[20]; //Véletlen számok generálása - mibe, alsó, felső érték randomGenerator(tomb, 0, 100); //Számok kiíratása rendezetlenül System.out.println("Rendezetlen lista:"); lista(tomb); //Rendezés az Arrays osztály statikus sort() metódusával. Arrays.sort(tomb); //Rendezett lista System.out.println("Rendezett lista:"); lista(tomb); //Kereséshez adat bekérés System.out.print("Kérem a számot: "); Scanner be = new Scanner(System.in); int keresett = be.nextInt(); //Bináris keresés int eredmeny = binSearch(tomb, keresett); if(eredmeny == -1){ System.out.println("Nincs benne a keresett érték."); } else{ System.out.println("Index: "+eredmeny); } ........//Keresés az Arrays tömb beépített függvényével eredmeny = Arrays.binarySearch(tomb, keresett); System.out.println("\nKeresés eredménye az Arrays beépített függvényével."); if(eredmeny == -1){ System.out.println("Nincs benne a keresett érték."); } else{ System.out.println("Index: "+eredmeny); } } //Tömb feltöltése véletlen számmal. public static void randomGenerator(int [] t, int also, int felso){ Random rnd = new Random(); for(int i = 0; i < t.length; i++){ t[i] = rnd.nextInt(felso-also+1)+also; } } //Tömb listázása. public static void lista(int [] t){ for(int i = 0; i < t.length; i++){ System.out.print(t[i]+", "); if((i+1) % 10 == 0) System.out.println(""); } System.out.println(""); }

21. oldal



//Bináris keresés függvénye, -1 ha nincs benne egyébként az index. public static int binSearch(int[] t, int keresett){ int also = 0; int felso = t.length-1; int kozepso; do{ kozepso = (also + felso) / 2; if(keresett < t[kozepso]) felso = kozepso - 1; else if(keresett > t[kozepso]) also = kozepso + 1; }while((t[kozepso] != keresett) && (also <= felso)); if(also <= felso) return kozepso; else return -1; } }

Egy sorozathoz egy sorozat rendelése Az algoritmus bemenete egy sorozat, a kimenete szintén egy sorozat. A kimeneti sorozat lehet szűkebb, egyező, vagy bővebb, mint a bemeneti. Az elemeken különböző transzformációt is végezhetünk.

Másolás Egy bemenő sorozatból egy kimenő sorozatot készítünk, mégpedig úgy, hogy az eredménysorozat ugyanolyan elemszámú, mint a bemeneti sorozat, és az eredménysorozat I. tagját a bemenő sorozat I. tagjából lehet meghatározni. A bemenő sorozatot tehát átmásoljuk úgy, hogy közben az elemeken esetleges átalakításokat végzünk. Algoritmus: Ciklus I:=1..NBemenő ismétel Bemenő sorozat I. eleméből Kimenő sor I. elemének előállítása Ciklus vége

Feladat: A születési éveket tartalmazó tömbből hozzunk létre egy tömböt, mely az életkorokat tartalmazza. Feladat: Töltsünk fel véletlen számokkal egy 20 elemű tömböt úgy, hogy az elemek 1000 és 5000 közöttiek legyenek. Ez legyen például könyvek nettó ára. Számoljuk ki a bruttó árakat egy másik tömbbe (ÁFA: 27%).

22. oldal



Java-kód: package masolnettobrutto; import java.util.Random; import java.lang.Math; public class MasolNettoBrutto { public static void main(String[] args) { // deklarációk int[] netto = new int[20]; int[] brutto = new int[20]; // egész értékekkel // nettó értékek feltöltése 1000..5000 között Random rnd = new Random(); for(int i = 0; i < netto.length; i++) netto[i] = rnd.nextInt(4001)+1000; // másolás transzformációval - bruttó előállítása for(int i = 0; i < brutto.length; i++) brutto[i] = (int)Math.round(netto[i] * 1.27); //nettó, bruttó ár listázása System.out.println("A könyvek nettó árai:"); lista(netto); System.out.println("A könyvek bruttó árai:"); lista(brutto); } // Listázó metódus public static void lista(int[] t){ for(int i = 0; i < t.length; i++) System.out.print(t[i]+", "); System.out.println(""); } }

Kiválogatás Adott egy N elemű A tömb és egy T() tulajdonság. Válogassuk ki egy B tömbbe az A vektor T() tulajdonságú elemeit. A két tömb elemszámának meg kell egyezni, mert lehet, hogy az első tömb minden elemét át kell másolni. Algoritmus: Db := 0 Ciklus i := 1-től N-ig Ha T(A(i) akkor Db := Db + 1 B(Db) := A(i) Ha vége Ciklus vége

Feladat: Töltsünk fel egy String tömböt nevekkel, majd válogassuk ki egy másik tömbbe a K, L, M betűkkel kezdődő neveket. Java-kód: package kivalogatastetele; public class KivalogatasTetele { 23. oldal



public static void main(String[] args) { // deklaráció kezdőértékadással String[] nevek = {"Ákos", "Béla", "Zénó", "Mátyás", "Eszter", "Leopold", "Géza", "Éva", "Laura", "Mária"}; // nevek kiíratása kiir(nevek, nevek.length); // a két tömb elemszámának meg kell egyezni String[] nevek2 = new String[10]; // K,L,M betűkkel kezdődő nevek kiválogatása // nevek2 indexváltozója -1, mert lehet, hogy egy sem egyezik int j = -1; for(int i = 0; i < nevek.length; i++) if(isEgyezik(nevek[i])){ j++; nevek2[j] = nevek[i]; } // Ha volt K, L, M kezdőbetűjű név, akkor kiírjuk. if(j > -1) kiir(nevek2, j); else System.out.println("Nincs K, L, M kezdőbetűvel név."); } // isEgyezik metódus megvizsgálja a nevek első betűjének egyezőségét public static boolean isEgyezik(String nev){ return (nev.charAt(0) == 'K')||(nev.charAt(0) == 'L') ||(nev.charAt(0) == 'M'); } // nevek kiíratása public static void kiir(String[] n, int db){ System.out.println("Nevek:"); for(int i = 0; i < db; i++){ System.out.print(n[i]+", "); // minden ötödik név után sort emel if((i+1) % 5 == 0) System.out.println(""); } System.out.println(""); } }

Feladat: Töltsünk fel véletlen számokkal egy 20 elemű tömböt úgy, hogy az elemek 10 és 100 közöttiek legyenek. Válogassuk ki a 10-zel osztható számokat egy másik tömbbe.

Egy sorozathoz több sorozat rendelése Van egy bemeneti és több kimeneti sorozat.

24. oldal



Szétválogatás Egy bemenő sorozatból több kimenő sorozatot készítünk. Azok a feladatok tartoznak ide, amelyeknél a bejövő adatok mindegyikére szükségünk van ugyan, de azokat valamilyen szempontból el kell különíteni, szét kell válogatni. A kimenő sorozatok elemszámainak összege megegyezik a bemenő sorozat elemszámával. A szétválogatást fel lehet fogni több egymás utáni kiválogatásként is, ahol egyszer minden elemre sor kerül. Mindegyik eredménysorozatban ugyanannyi elemszámra kell felkészülni, mint a bemenő sorozat elemszáma, hiszen szélsőséges esetben elképzelhető, hogy minden elem egyetlen kimenő sorozatba kerül át. Algoritmus: Eljárás szétválogatás NBemenő // bemeneti sorozat elemszáma NKimenő1:=0 // első kimeneti sorozat elemszáma NKimenő2:=0 // második kimeneti sorozat elemszáma ... // szükség esetén további kimeneti sorozatok ciklus I:=1..NBemenő ismétel elágazás amikor Bemenő[I] az 1. tulajdonságú: NKimenő1:=NKimenő1+1 Kimenő1[NKimenő1]:=Bemenő[I] amikor Bemenő[I] az 2. tulajdonságú: NKimenő2:=NKimenő2+1 Kimenő2[NKimenő2]:=Bemenő[I] ... különben ... elágazás vége Ciklus vége Eljárás vége

Feladat: Adott egy osztály névsor. Válogassuk szét a tanulókat nemük szerint két csoportba. A Tanulo osztály tartalmaz egy ffi adattagot, a fiú/lány – igaz/hamis jelölésére. Java-kód: package szetvalogattanulo; import java.util.Scanner; public class SzetvalogatTanulo { public static void main(String[] args) { // Kapcsolat létrahozása a Tanulo osztállyal. // tárolás tömbben Tanulo[] tanulok = new Tanulo[10]; // a tanulok tömb feltöltése feltolt(tanulok); // lista a tanulókról System.out.println("A tanulók listázása:"); lista(tanulok, tanulok.length); 25. oldal



// két nemek szerinti tömb létrehozása Tanulo[] ferfiak = new Tanulo[10]; Tanulo[] nok = new Tanulo[10]; // elemszám a lányok és férfiak tömbjeihez // tömbben tárolva a referencia miatt // első elem férfi, második a nők száma int[] letszam = new int[2]; letszam[0] = 0; letszam[1] = 0; // nemek szerinti szétválogatás szetvalogat(tanulok, ferfiak, nok, letszam); // nemek szinti listázás, ha volt elem System.out.println("Lányok listázása:"); if(letszam[1] > 0) lista(nok, letszam[1]); else System.out.println("Nem voltak lányok"); System.out.println("Fiúk listázása:"); if(letszam[0] > 0) lista(ferfiak, letszam[0]); else System.out.println("Nem voltak fiúk"); } // tanulok tömb feltöltése public static void feltolt(Tanulo[] t){ Scanner be = new Scanner(System.in); System.out.println("A 10 elemű tanulók tömb feltöltése"); String nev; char ffi; for(int i = 0; i < t.length; i++){ System.out.print("Név: "); nev = be.nextLine(); System.out.print("Férfi-e (f/n): "); ffi = be.nextLine().charAt(0); t[i] = new Tanulo(nev, ffi); } } // lista public static void lista(Tanulo[] t, int letszam){ System.out.println("Név\t\tNeme"); for(int i = 0; i < letszam; i++){ System.out.printf("%10s\t%3c\n",t[i].getNev(), t[i].getFerfi()); } } // szétválogatás nemek szerint public static void szetvalogat(Tanulo[] t, Tanulo[] f, Tanulo[] n, int[] l){ for(int i = 0; i < t.length; i++){ if(t[i].getFerfi() == 'f'){ // férfiak elemszámának növelése l[0]++; // elhelyezés a fiúk tömbjébe // az index elemszam-1

26. oldal



f[l[0]-1] = new Tanulo(t[i].getNev(), t[i].getFerfi()); } else if(t[i].getFerfi() == 'n'){ // nők elemszámának növelése l[1]++; // elhelyezés a lányok tömbjébe // az index elemszám-1 n[l[1]-1] = new Tanulo(t[i].getNev(), t[i].getFerfi()); } } } }

A Tanulo osztály: package szetvalogattanulo; public class Tanulo { // adattagok String nev; char ffi; //f - férfi, n - nő // konstruktor public Tanulo(String nev, char ffi){ // A this objektumreferencia szükséges, mert a lokális // változók takarják az osztály szintű változókat. this.nev = nev; this.ffi = ffi; } //setter (beállító) metódusok public void setNev(String n){ // Mivel a lokális szinten lévő paraméter nem takarja // az osztály adattagot, nem szükséges this előtag. nev = n; } public void setNeme(char n){ ffi = n; } // getter (lekérdező) metódusok public String getNev(){ return nev; } public char getFerfi(){ return ffi; } }

Feladat: Állítsunk elő egy 20 elemű véletlen egészeket [0..100] tartalmazó sorozatot, majd válogassuk szét a páros és a páratlan számokat.

27. oldal



Gyakorlás (másolás, kiválogatás, szétválogatás) Feladat: Adott egy neveket (vezeték és keresztnév) tartalmazó szóközzel elválasztott tömb. A vezeték és keresztnevek szóközzel vannak elválasztva. Állítsuk elő a monogramokat tartalmazó tömböt. A kiíratásokat végezzük el. Feladat: Adott egy dolgozók nevét és fizetését tartalmazó vektor. Válogassuk ki azon dolgozók neveit, akiknek a fizetése kisebb, mint 120000 Ft. Feladat: Egy iskola sportolási lehetőséget biztosít a tanulóinak. Háromféle lehetőség közül választhatnak a diákok (futball, ping-pong, kosárlabda). Egyet kötelezően választani kell. A tanulóknál nyílván tartják, hogy ki mit választott. Készíts listát, amelyben szétválogatjuk a tanulókat a sport csoportoknak megfelelően.

Rendezések, rendezettség Rendezésnek nevezünk egy algoritmust, ha az valamilyen szempont alapján sorba állítja elemek egy listáját. Legyen adott egy N elemszámú A sorozat. A rendezés feladata, hogy a sorozat A(i) és A(i+1) elemeit a rendező elv R(A(i), A(i+1)) szerinti sorrendbe tegye. A legegyszerűbb esetben növekvő rendezést végzünk. Tehát az R(A(i), A(i+1)) rendezettség (logikai) függvény igaz értékkel tér vissza, ha az A(i) értéke kisebb egyenlő, mint az A(i+1) értéke.

Rendezettség A rendezettség azt jelenti, hogy egy sorozat egymást követő két eleméről (pl. A és B) egyértelműen meg lehet állapítani, hogy melyikük az előrébb való. A rendező elv lehet bonyolultabb is, mint a kisebb/nagyobb reláció. Amikor egy összetett feltétel szerint kell meghatározni az elemek egymáshoz viszonyított helyét, érdemes egy rendező függvényt készíteni. Ez a függvény, akkor fog igazat visszaadni, ha a két rendezendő elem egymáshoz képest jó helyen van. Rendező függvény: Rendezett(A(i), A(i+1)): logikai return A(i) <= A(i+1) 28. oldal



Rendezett vége

Feladat: Töltsünk fel egy 20 elemű vektort véletlen értékekkel, és rendezzük úgy, hogy elől legyenek a páratlan számok növekvően, majd a párosak szintén növekvő sorrendben! Rendező elv (feltétel) meghatározása: Azokat a feltételeket kell megtalálni, amelyek szükségesek a rendezettség előállításához. Legyen A az első, B a második szám az R(A, B) rendező függvénynél:  A páratlan, B páros, 

Ha A és B páratlan, akkor A < B,



Ha A és B páros, akkor A < B.

Nézzük a relációkat:  Páratlanság vizsgálata: (A % 2 != 0) – a szám kettővel való osztása nem nulla osztási maradékot ad. 

Párosság vizsgálata: (A % 2 == 0) – a szám kettővel való osztása esetén nincs maradék.



Elől legyenek a páratlan számok, hátul a párosak: (A % 2 != 0) & (B % 2 == 0).



Két páratlan szám esetén az első kisebb egyenlő legyen, mint a második: (A % 2 != 0) & (B % 2 != 0) & (A <= B).



Két páros szám esetén az első kisebb egyenlő legyen, mint a második: (A % 2 == 0) & (B % 2 == 0) & (A <= B).

Tehát a szükséges feltétel: ((A % 2 != 0) & (B % 2 == 0)) | ((A % 2 != 0) & (B % 2 != 0) & (A <= B)) | ((A % 2 == 0) & (B % 2 == 0) & (A <= B)). Az AND (&) erősebb prioritású művelet, mint az OR ( | ), ezért a külső zárójelek elhagyhatók. A % szintén erősebb, mint a relációjel, ezért oda nem lett téve zárójel. Feladat: Rendezzük az egész számok egy listáját úgy, hogy a páros számok emelkedő, illetve a páratlan számok csökkenő sorrendben legyenek. A rendező feladatokban szükséges az elempárok felcserélése. Ennek az algoritmusa a következő.

29. oldal



Algoritmus: csere(elso, masodik: tipus) temp: tipus temp := elso elso := masodik masodik := temp csere vege

A csere eljárás implementálásánál Java nyelven, figyelni kell arra, hogy a Java-ban érték szerinti paraméterátadás van. (Vagyis referenciát adunk át, például egy tömb nevet, illetve a két megcserélendő elem indexét.) A csere referencia átadással (Java): csere(t: tömb, i: egész, j: egész) temp: tipus temp := t[i] t[i] := t[j] t[j] := temp csere vége

A „t” egy tömb referencia, az „i” és „j” a cserélendő elemek indexei.

Minimum-kiválasztásos rendezés A rendezés egy sorozat elemeinek egymáshoz viszonyított helyét állítja be. A minimumkiválasztásos rendezésnél a rendező elv az adott rendezettség szerinti első elem kiválasztása. A legegyszerűbb esetben növekvő relációt használunk. Ebben az esetben a minimum-kiválasztásos rendezés lényege: 

Első lépésben megkeressük a sorozat legkisebb elemét. Majd, ha ez nem az első elem, kicseréljük az első elemmel. Így az első helyen a sorozat legkisebb eleme lesz.



A következő lépésben, a második legkisebb elemet keressük, a még nem rendezett (második elemtől az utolsóig) részben. A megtalált elemet, ha ez nem egyenlő a második helyen lévővel, megcseréljük. Ekkor a sorozatunk, a második elemig rendezett.



A további lépések az előző kettőhöz hasonlóan futnak le, mindig megkeresve a sorozat következő legkisebb elemét. Amely ez által addig rendezetté válik.



Utolsó lépésként az utolsó előtti helyre kell kiválasztani a legkisebb elemet. Ezt követően a sorozat rendezetté válik.

30. oldal



Algoritmus: Ciklus i := 1-től a sorozat vége -1-ig minindex := i Ciklus j := i + 1-től a sorozat végéig Ha sorozat[j] < sorozat[minindex] akkor minindex := j Ha vége Ciklus vége Ha i <> minindex akkor Csere(sorozat[i], sorozat[minindex]) Ha vége Ciklus vége

A Csere() eljárás hívása a Java-ban, a következőre módosul az érték szerinti paraméterátadás miatt: Csere(sorozat, i, minindex). Átadjuk a tömb referenciát, majd a két cserélendő elem helyét a tömbben. Ezzel a tömb referencia átadással a változás maradandó lesz. Példa: 3, 1, 1, 1, 1, 1, 1, 1, 1,

6, 6, 2, 2, 2, 2, 2, 2, 2,

2, 2, 6, 3, 3, 3, 3, 3, 3,

7, 7, 7, 7, 4, 4, 4, 4, 4,

4, 4, 4, 4, 7, 5, 5, 5, 5,

9, 9, 9, 9, 9, 9, 6, 6, 6,

1, 3, 3, 6, 6, 6, 9, 7, 7,

8, 8, 8, 8, 8, 8, 8, 8, 8,

5  rendezetlen sorozat 5 5 5 5 7 7 9 9  rendezett sorozat

Ciklusok száma: 8 Feladat: Generáljunk egy véletlen egész számokat tartalmazó tömböt, és rendezzük növekvő, sorrendbe. Java-kód: package minkivalrendezes; import java.util.Random; public class MinKivalRendezes { public static void main(String[] args) { Random rnd = new Random(); // 20 elemű tömb deklarálása és feltöltése 0..100 közötti számokkal int [] t = new int[20]; for(int i = 0; i < t.length; i++) t[i] = rnd.nextInt(101); // elemek kiíratása foreach jellegű ciklussal System.out.println("Rendezetlen sorozat:"); for(int e : t) System.out.print(e+", "); System.out.println(""); // elemek rendezése minimum-kiválasztásos rendezéssel int minIndex; 31. oldal



for(int i = 0; i < t.length-1; i++){ // feltételezzük, hogy az i. elem a legkisebb minIndex = i; for(int j = i+1; j < t.length; j++){ // ha találtunk a minIndex. elemtől kisebbet if(t[j] < t[minIndex]){ // akkor megjegyezzük az indexet minIndex = j; } } // ha a minIndex != i-vel akkor találtunk kisebbet, és akkor csere if(minIndex != i){ // cserélje meg a t tömbben az i. elemet a minIndex. elemmel csere(t, i, minIndex); } } // rendezés után kiíratjuk System.out.println("Rendezett sorozat:"); for(int e : t) System.out.print(e+", "); System.out.println(""); } // a csere metódus definiálása, paraméterek a tömb, és a két index public static void csere(int[] t, int i, int j){ // segéd változó a cseréhez temporary - ideiglenes int temp; temp = t[i]; t[i] = t[j]; t[j] = temp; } }

Feladat: Mit kell megváltoztatni az előző feladatban, hogy csökkenő rendezést kapjunk? Feladat: Generáljunk egy egészeket tartalmazó 20 elemű tömböt, majd rendezzük úgy, hogy elől legyenek a páros számok növekvő, végül a páratlanok csökkenő sorrendben. Java-kód: package rendezesparosparatlan; import java.util.Random; public class RendezesParosParatlan { public static void main(String[] args) { // deklaráció int[] tomb = new int[20]; // tömb feltöltése véletlen számokkal feltolt(tomb); // elemek kiíratása

32. oldal



System.out.println("A tömb elemei:"); lista(tomb); // rendezés rendez(tomb); // rendezett tömb kiíratása System.out.println("\nA rendezett tömb elemei:"); lista(tomb); } // a tömb feltöltése véletlen számokkal 0..100 public static void feltolt(int[] t){ Random rnd = new Random(); for(int i = 0; i < t.length; i++) t[i] = rnd.nextInt(101); } // a tömb elemeinek listázása public static void lista(int[] t){ for(int i = 0; i < t.length; i++) System.out.print(t[i]+", "); System.out.println(""); } // a rendezettség megállapítása függvénnyel public static boolean rendezett(int a, int b){ // a következő esetekben ad vissza igazat // ha a, b páros és a < b // ha a, b páratlan és a > b // ha a páros és b páratlan return ((a % 2 == 0) && (b % 2 == 0) && (a < b)) || ((a % 2 != 0) && (b % 2 != 0) && (a > b)) || ((a % 2 == 0) && (b % 2 != 0)); } // a csere eljárás megvalósítása public static void csere(int[] t, int mit, int mivel){ int temp = t[mit]; t[mit] = t[mivel]; t[mivel] = temp; } // a tömb eleminek rendezése minimum-kiválasztásos rendezéssel public static void rendez(int[] t){ int minIndex; for(int i = 0; i < t.length-1; i++){ minIndex = i; for(int j = i+1; j < t.length; j++){ if(!rendezett(t[minIndex], t[j])) minIndex = j; } if(minIndex != i){ csere(t, i, minIndex); } } } }

Futási kép: A tömb elemei:

33. oldal



7, 90, 48, 44, 37, 52, 30, 29, 67, 92, 30, 24, 22, 84, 26, 42, 13, 65, 96, 98, A rendezett tömb elemei: 22, 24, 26, 30, 30, 42, 44, 48, 52, 84, 90, 92, 96, 98, 67, 65, 37, 29, 13, 7, BUILD SUCCESSFUL (total time: 0 seconds)

Maximum kiválasztásos rendezés A reláció megfordul, nem a legkisebbet, hanem a legnagyobbat keressük.

Gyakorlás Feladat: Rendezzük az előző sorozatot úgy, hogy a páros számok növekvő, majd a páratlanok csökkenő sorrendben legyenek. Java-kód: Elég az előző feladat rendezettséget megállapító függvényét aktualizálni. // a rendezettség megállapítása függvénnyel public static boolean rendezett(int a, int b){ // a következő esetekben ad vissza igazat // ha a, b páros és a < b // ha a, b páratlan és a > b // ha a páros és b páratlan // ha a páratlan és b páros return ((a % 2 == 0) && (b % 2 == 0) && (a < b)) || ((a % 2 != 0) && (b % 2 != 0) && (a > b)) || ((a % 2 == 0) && (b % 2 != 0)) || ((a % 2 != 0) && (b % 2 == 0)); }

Futási kép: A tömb elemei: 10, 37, 35, 7, 100, 40, 9, 36, 38, 72, 94, 96, 7, 2, 11, 92, 63, 19, 84, 57, A rendezett tömb elemei: 2, 63, 57, 37, 10, 36, 35, 38, 40, 72, 84, 92, 19, 94, 11, 96, 9, 7, 100, 7, BUILD SUCCESSFUL (total time: 0 seconds)

A következő feladatban a rendezendő elemek nem primitív típusok, hanem objektumok. Így reláció jelekkel közvetlenül nem tudjuk az elsőbbséget megállapítani. Objektumok összehasonlítására a compareTo() metódus használható. A String osztály tartalmazza, nekünk csak használnunk kell. Az általunk létrehozott osztályokban többnyire a programozónak kell megvalósítani.

34. oldal



Feladat: Rendezzünk egy sztringeket tartalmazó 10 elemű tömböt nagyság szerint. Java-kód: package rendezesstring; import java.util.Scanner; public class RendezesString { public static void main(String[] args) { // deklaráció String[] tomb = new String[10]; // tömb feltöltése sztringekkel feltolt(tomb); // elemek kiíratása System.out.println("A tömb elemei:"); lista(tomb); // rendezés rendez(tomb); // rendezett tömb kiíratása System.out.println("\nA rendezett tömb elemei:"); lista(tomb); } // a tömb feltöltése sztringekkel public static void feltolt(String[] t){ Scanner be = new Scanner(System.in); for(int i = 0; i < t.length; i++){ System.out.print("Szöveg: "); t[i] = be.nextLine(); } } // a tömb elemeinek listázása public static void lista(String[] t){ for(int i = 0; i < t.length; i++) System.out.print(t[i]+", "); System.out.println(""); } // a rendezettség megállapítása függvénnyel public static boolean rendezett(String str1, String str2){ // a következő esetben ad vissza igazat // ha str1 <= str2 return str1.compareTo(str2) <= 0; } // a csere eljárás megvalósítása public static void csere(String[] t, int mit, int mivel){ String temp = t[mit]; t[mit] = t[mivel]; t[mivel] = temp; } // a tömb elemeinek rendezése minimum-kiválasztásos rendezéssel public static void rendez(String[] t){ int minIndex; for(int i = 0; i < t.length-1; i++){ minIndex = i; for(int j = i+1; j < t.length; j++){

35. oldal


10 – 11. évfolyam if(!rendezett(t[minIndex], t[j])) minIndex = j; } if(minIndex != i){ csere(t, i, minIndex); }

} } }

Futási kép: Szöveg: alma Szöveg: körte Szöveg: banán Szöveg: eper Szöveg: málna Szöveg: szamóca Szöveg: ribizli Szöveg: szőlő Szöveg: cseresznye Szöveg: meggy A tömb elemei: alma, körte, banán, eper, málna, szamóca, ribizli, szőlő, cseresznye, meggy, A rendezett tömb elemei: alma, banán, cseresznye, eper, körte, meggy, málna, ribizli, szamóca, szőlő, BUILD SUCCESSFUL (total time: 1 minute 2 seconds)

Feladat: Töltsünk fel egy 10 elemű tömböt téglalapokkal (osztály létrehozása). Majd rendezzük terület szerint csökkenő sorrendbe. Java-kód: A RendezTeglalapMinKival osztály forráskódja package rendezteglalapminkival; import java.util.Random; public class RendezTeglalapMinKival { public static void main(String[] args) { // deklarációk Random rnd = new Random(); Teglalap[] tomb = new Teglalap[10]; int a; int b; // tömb feltöltése ciklusban véletlenszám generálással // 1..100 közötti oldal hosszúságok for(int i = 0; i < tomb.length; i++){ a = rnd.nextInt(100)+1; b = rnd.nextInt(100)+1; // téglalap létrehozása konstruktorral tomb[i] = new Teglalap(a, b); }

36. oldal



// listázás System.out.println("Rendezés előtt:"); lista(tomb); // rendezés terület szerint növekvően rendez(tomb); // rendezés után listázás System.out.println("\nRendezés után:"); lista(tomb); } // a téglalapok adatainak listázása public static void lista(Teglalap[] t){ for(int i = 0; i < t.length; i++) System.out.println((i+1)+". "+t[i].toString()); } // minimum-kiválasztásos rendezés public static void rendez(Teglalap[] t){ int minIndex; for(int i = 0; i < t.length-1; i++){ minIndex = i; for(int j = i+1; j < t.length; j++){ if(!rendezett(t[minIndex], t[j])){ minIndex = j; } } if(minIndex != i){ csere(t, minIndex, i); } } } // terület alapján a rendezettséget mutató metódus private static boolean rendezett(Teglalap a, Teglalap b){ return a.terulet() < b.terulet(); } // csere metódus private static void csere(Teglalap[] t, int i, int j){ Teglalap temp; temp = t[i]; t[i] = t[j]; t[j] = temp; } }

A rendezés a Teglalap osztály egy primitív típusú tulajdonsága (adattagja) alapján történik, ezért nem kell compareTo() metódus. A Teglalap osztaly forraskódja package rendezteglalapminkival; public class Teglalap { // példány adattagok private int a; private int b; // statikus adattag - a létrehozott téglalap példányok száma private static int db = 0; // konstruktor

37. oldal



public Teglalap(int _a, int _b){ a = _a; b = _b; db++; } // adatlekérdező (getter) példány metódusok public int getA() { return a; } public int getB() { return b; } // adatlekérdező statikus metódus public static int getDb() { return db; } // terület számítás public int terulet(){ return a *b; } // kerület számítás public int kerulet(){ return 2 * (a + b); } // toString() metódus @Override // az Object osztály felülírt metódusa public String toString(){ return "téglalap:\n"+ " a = "+a+" cm"+"\n"+ " b = "+b+" cm"+"\n"+ " terület = "+this.terulet()+" cm2"+"\n"+ " kerület = "+this.kerulet()+" cm"+"\n"; } }

Futási kép részlet: run: Rendezés előtt: 1. téglalap: a = 2 cm b = 19 cm terület = 38 cm2 kerület = 42 cm 2. téglalap: a = 68 cm b = 81 cm terület = 5508 cm2 kerület = 298 cm 3. téglalap: a = 5 cm b = 32 cm terület = 160 cm2 kerület = 74 cm

38. oldal



4. téglalap: a = 24 cm b = 49 cm terület = 1176 cm2 kerület = 146 cm … Téglalap objektumok száma: 10 db … Rendezés után: 1. téglalap: a = 2 cm b = 19 cm terület = 38 cm2 kerület = 42 cm 2. téglalap: a = 53 cm b = 3 cm terület = 159 cm2 kerület = 112 cm 3. téglalap: a = 5 cm b = 32 cm terület = 160 cm2 kerület = 74 cm 4. téglalap: a = 46 cm b = 11 cm terület = 506 cm2 kerület = 114 cm

Rendezés compareTo() metódussal: A rendezéskor objektumokat hasonlítunk össze, nem egy primitív értékű résztulajdonságot. Java-kód: package rendezteglalapminkival_compareTo; import java.util.Random; public class RendezTeglalapMinKival_compareTo { public static void main(String[] args) { // deklarációk Random rnd = new Random(); Teglalap[] tomb = new Teglalap[10]; int a; int b; // tömb feltöltése ciklusban véletlenszám generálással // 1..100 közötti oldal hosszúságok for(int i = 0; i < tomb.length; i++){ a = rnd.nextInt(100)+1; b = rnd.nextInt(100)+1; // téglalap létrehozása konstruktorral tomb[i] = new Teglalap(a, b); }

39. oldal



// listázás System.out.println("Rendezés előtt:"); lista(tomb); // létrehozott téglalpok száma System.out.println("Téglalap objektumok száma: "+Teglalap.getDb()+" db"); // rendezés terület szerint növekvőleg rendez(tomb); // rendezés után listázás System.out.println("\nRendezés után:"); lista(tomb); } // a téglalapok adatainak listázása public static void lista(Teglalap[] t){ for(int i = 0; i < t.length; i++) System.out.println((i+1)+". "+t[i].toString()); } // minimum-kiválasztásos rendezés public static void rendez(Teglalap[] t){ int minIndex; for(int i = 0; i < t.length-1; i++){ minIndex = i; for(int j = i+1; j < t.length; j++){ // ha a j. elem kisebb mint a minIndex., akkor csere if(t[j].compareTo(t[minIndex]) < 0){ minIndex = j; } } if(minIndex != i){ csere(t, minIndex, i); } } } // csere metódus private static void csere(Teglalap[] t, int i, int j){ Teglalap temp; temp = t[i]; t[i] = t[j]; t[j] = temp; } }

package rendezteglalapminkival_compareTo; public class Teglalap { // példány adattagok private int a; private int b; // statikus adattag - a létrehozott téglalap példányok száma private static int db = 0; // konstruktor public Teglalap(int _a, int _b){ a = _a; b = _b; 40. oldal



db++; } // adatlekérdező (getter) példány metódusok public int getA() { return a; } public int getB() { return b; } // adatlekérdező statikus metódus public static int getDb() { return db; } // terület számítás public int terulet(){ return a *b; } // kerület számítás public int kerulet(){ return 2 * (a + b); } // toString() metódus @Override public String toString(){ return "téglalap:\n"+ " a = "+a+" cm"+"\n"+ " b = "+b+" cm"+"\n"+ " terület = "+this.terulet()+" cm2"+"\n"+ " kerület = "+this.kerulet()+" cm"+"\n"; } /* * összehasonlításhoz a compareTo() metódus * ha a megszólított objektum területe kisebb, mint a * paraméterül kapott objektum területe, akkor a * visszatérési érték negatív, ha egyenlő a két érték, * akkor az eredmény nulla, ha nagyobb a paraméter * értéke, akkor pedig pozitív */ public int compareTo(Teglalap t){ return this.terulet() - t.terulet(); } }

Buborék rendezés A buborék rendezés a szomszédos elemeket cseréli, ha a sorrend nem megfelelő. Kezdetben az első két elemet hasonlítjuk össze, és szükség esetén felcseréljük őket. A második lépésben a 2. és a 3. elemet hasonlítjuk, és ha kell, cseréljük. Ezt így folytatjuk a sorozat végéig. Ekkor növekvő rendezettséget feltételezve a sorozat végén lesz a legnagyobb elem. A második ciklusban, már csak az utolsó előtti elemig végezzük a hasonlítást és szükség esetén a cserét. Ha a második ciklus lefutott, a sorozat utolsó két eleme már a helyén van. A harmadik, és az

41. oldal



azt követő ciklusokban egyre kisebb része marad rendezetlenül a sorozatnak. Utolsó ciklus az első két elemet rendezi. Algoritmus: Buborék(T: tömb[1..N] egész) Deklaráció i, j: egész Buborék_kezd Ciklus i:= N-1-től 1-ig -1-esével Ciklus j:= 1-től i-ig 1-esével Ha A[j] > A[j+1] akkor csere(A[j], A[j+1]) Elágazás vége Ciklus vége Ciklus vége Buborék vége

Példa:

Ez a megvalósítás a legegyszerűbb, viszont egy rendezett tömbön is a (külső ciklus) * (belső ciklus) számszor fut le, és végzi az összehasonlításokat. Javíthatunk az algoritmuson, ha

42. oldal



figyeljük, hogy a belső ciklusban történt-e csere. Ha nem, akkor a következő külső ciklusban sem fog. Így abba lehet hagyni a rendezést. Ezt mutatja be a következő megvalósítás. Algoritmus: Buborék2(T: tömb[1..N] egész) Deklaráció i, j: egész vége: logikai Buborék2 kezdet i:= N-1 vége:= HAMIS Ciklus amíg i >= 1 ÉS NEM vége vége:= IGAZ Ciklus j:= 1-től i-ig 1-esével Ha T[j] > T[j+1] akkor csere(T[j], T[j+1]) vége:= HAMIS Ha vége Ciklus vége i:= i-1 Ciklus vége Buborék2 vége

Példa:

43. oldal



Ha a belső ciklusban kiderül, hogy a sorozat már rendezett, akkor kilép. Viszont a külső ciklus csak egyet lép, pedig a rendezettség többet is megengedne. Ezen segíthetünk, ha megjegyezzük azt a sorszámot, ahol utoljára kellett cserélni. E fölött a sorozat rendezett, így felesleges újra végigjárni. A harmadik algoritmus ezt mutatja be. Algoritmus: Buborék3(T: tömb[1..N] egész) Deklaráció i, j: egész utolsó_csere Buborék3 kezdet i:= N-1 Ciklus amíg i >= 1 utolsó_csere:= 0 Ciklus j:= 1-től i-ig 1-esével Ha T[j] > T[j+1] akkor csere(T[j], T[j+1]) utolsó_csere:= j Ha vége Ciklus vége i:= utolsó_csere-1 Ciklus vége Buborék3 vége

Példa:

44. oldal



A második és a harmadik buborékrendezés akkor hatékony, ha a sorozat nagy része rendezett. Feladat: Készítsünk programot, amely az iskolai sportnap eredményeit tárolja és dolgozza fel! A

sportnapon

egyéni

számok

vannak

(futás,

gerelyhajítás,

kislabdadobás,

kosárbadobás). Vigyük fel az adatokat 5 diákra, és listázzuk ki csökkenő sorrendben az eredményeket számonként, és összesítésben is. Az összesítésben a sorrendet az határozza meg, hogy ki nyert többször. Feladat: Tároljuk el egy hónap napi középhőmérsékleti értékeit! Majd menüből engedje meg az adatok módosítását, adjon listát a bevitt adatokról akár nap szerinti sorrendben, akár hőméréskelt szerint növekvően, vagy csökkenően. A naphoz írjuk ki a hőmérsékletet, és a hőmérséklethez a napot.

Beszúrásos rendezés A beszúrásos, vagy pókerrendezés hasonlít arra, ahogy az ember kártyaosztás után elrendezi a lapokat a kezében. Felvesszük az első lapot, majd a másodikat, és helyére tesszük. A helyét, egy adott rendező elv határozza meg. Minden újabb lapnál megkeressük és elkészítjük a helyét, majd betesszük a lapot. Algoritmus: Beszúrásos(T: tömb[1..N] egész) Deklaráció x, i, j: egész Beszúrásos kezdet Ciklus i:= 2-től N-ig j:= i-1 x:= T[i] Ciklus amíg j >= 1 ÉS x < T[j] T[j+1]:= T[j] j:= j-1 Ciklus vége T[j+1]:= x Ciklus vége Beszúrásos vége

Előnyök: 

Hatékony kis adatsorok esetén



Hatékony, ha az adatsorok már részben rendezettek



Gyakorlatban hatékonyabb a többi O(n2)-es rendezésnél



Online algoritmus, képes rendezni egy listát az új elemek felvételekor

45. oldal



Rendezések összehasonlítása4 A rendezések hatékonyságát általában a szükséges összehasonlítások, cserék átlagos és maximális száma és az extra tárigény alapján végezzük. „A nagy ordó jelölés egy olyan, matematikában használt jelölésmód, amely tömören fejezi ki egy adott függvény növekedésének mértékét. Informatikában általában egy algoritmus futásidejének jellemzésére használjuk: a vizsgált függvény a futáshoz szükséges időt adja meg a bemenet hosszának függvényében. Leegyszerűsítve, egy O(n^2) futásidejű algoritmus kétszer akkora méretű bemenetre négyszer annyi ideig fog futni, háromszor akkora bemenetre kilencszer annyi ideig. Míg maga a futásidőt leíró függvény függ az implementáció részleteitől és a futtatáshoz használt architektúrától, az algoritmus nagy ordója csak az algoritmus alapelvétől függ.”5 Minimum-kiválasztásos rendezés  Helyfoglalás: N+1, azaz O(N) 

Hasonlítások száma: N*(N-1)/2, azaz O(N2)



Mozgatások száma: 3*(N-1)/2, azaz O(N)

Buborék rendezés  Helyfoglalás: N+1, azaz O(N) 

Hasonlítások száma: N*(N-1)/2, azaz O(N2)



Mozgatások száma: 0 – 3*N*(N-1)/2, azaz O(N2)

Javított Buborékos rendezés  Helyfoglalás: N+1, azaz O(N) 

Hasonlítások száma: N-1 – N*(N-1)/2, azaz O(N2)




Beszúró rendezés  Helyfoglalás: N+1, azaz O(N)

4 5



Hasonlítások száma: N-1 – N*(N-1)/2, azaz O(N2)




https://hu.wikipedia.org/wiki/Rendezés_(programozás) http://wiki.prog.hu/wiki/Nagy_ordó_jelölés

46. oldal



Gyorsrendezés Rekurzív algoritmus, kettéosztja a rendezendő listát egy kiemelt elemnél kisebb és nagyobb elemekre, majd a részekre külön-külön alkalmazza a gyorsrendezést. 

Átlagos eset: 𝑂(𝑛 lg 𝑛)



Legrosszabb eset:



Tárigénye:

Kupacrendezés A kupacrendezés a használt adatszerkezetről kapta a nevét, a kupacról. Működése során felépíti a kupacot, majd egyesével kiemeli a gyökérelemet, ami a kupac definíciója miatt a legnagyobb/legkisebb elem lesz. 

Átlagos eset:



Legrosszabb eset:



Tárigénye:

Rendezések animációit bemutató oldal: http://tenger.web.elte.hu/flash/index.htm

Halmazműveletek A halmaz a matematika egyik legalapvetőbb fogalma, melyet leginkább az „összesség”, „sokaság” szavakkal tudunk körülírni, de mivel igazából alapfogalom; így nem tartjuk definiálandónak. A naiv halmazelméletben egy halmaz meghatározott, egymástól különböző objektumok gyűjteménye, összessége. Ezeket az objektumokat a halmaz elemeinek nevezzük. Azt, hogy eleme, így: 𝑎

halmaznak, így jelöljük:

eleme az

∉𝐴

Tulajdonságok:  Legyenek

és

tetszőleges halmazok. Akkor mondjuk, hogy az

egyenlőek, ha ugyanazok az elemeik, és ezt így jelöljük: 

Azt mondjuk, hogy az a

. Azt pedig, hogy nem

halmaz részhalmaza a

halmaz tartalmazza az

halmazt), ha az

47. oldal

és

halmazok

.

halmaznak (vagy más szavakkal: minden eleme a

halmaznak is



eleme. Ezt így jelöljük: nevezzük, ha 

. Az

, és

Azt a halmazt, amelynek minden és

halmazt a

halmaz valódi részhalmazának

. A valódi részhalmaz jele: 𝐴

⊂𝐵

elemére teljesül, hogy

és/vagy

, az

halmazok egyesítésének (más szóval uniójának) nevezzük, és így jelöljük: .






6

halmazok metszetének nevezzük, és így jelöljük:



és .


halmazok különbségének nevezzük, és így jelöljük:

Forrás: http://hu.wikipedia.org/wiki/Halmaz

48. oldal

is, az

, de .6

, az



Metszetképzés tétele A programozási feladatoknál a halmazokat többnyire tömb adatszerkezettel ábrázoljuk (reprezentáljuk), így elemek sorozataival dolgozunk. A metszet, vagy közös rész meghatározása során két vagy több sorozat azon elemeit válogatjuk ki, amelyek minden sorozatban benne vannak. A sorozatok nincsenek rendezve, és feltételezzük, hogy minden elem csak egyszer fordul elő az egyes sorozatokban. A képződő sorozat elemszáma kisebb vagy egyenlő, mint a legkisebb elemszámú bemenő sorozat elemszáma. A feladatot úgy oldjuk meg, hogy végigmegyünk az egyik sorozaton, és az aktuális elemet keressük a többi sorozatban. Ha mindegyikben benne van, akkor betesszük a közös rész sorozatába. Pl. adott két halmaz: 

A = {4, 7, 3, 9, 0, 8} és

elemszám: 6



B = {1, 5, 4, 3, 0, 2, 6, 9} halmazok közös része

elemszám: 8



𝐴 ∩ 𝐵 = {4, 3, 9, 0}

elemszám: 4.

Algoritmus: //H1 és H2 halmazok, K azok közös része, //N, M  N természetes számok halmazának, beleértve a 0-át //feltételezzük, hogy N <= M Metszet(H1: tömb[N], H2: tömb[M], K: tömb[N]) Deklaráció: i, j: egész Metszet kezdet //A közös rész (K) indexváltozójának inicializálása. j:=0 //A H1 sorozaton megyünk végig egyesével.  - eleme Ciklus i := 1-től N-ig Ha H1[i]  H2-nek, akkor j := j+1 K[j] := H1[i] Ha vége Ciklus vége Metszet vége

A „H1[i]  H2-nek” tartalmazás vizsgálatot érdemes egy külön alprogramban megvalósítani. Az alprogram függvényszerűen hívódik, és logikai igaz/hamis értéket ad vissza attól függően, hogy a keresett elem benne van-e a sorozatban.

49. oldal



Algoritmus: Eleme(elem: típus, sorozat: tömb[N]): logikai Deklaráció: i : egész Eleme kezdet //Végigmegyünk a sorozaton Ciklus i := 1-től N-ig Ha elem = sorozat[i], akkor //Ha megtaláltuk, akkor igazzal térünk vissza. return true Ciklus vége //Ha végigmentünk a sorozaton, akkor nincs benne. Ha i > N, akkor return false Eleme vége

Vizsgáljuk meg azt az esetet, amikor három bemenő sorozatunk van. Ekkor is végigmegyünk az egyik sorozaton, és sorban megvizsgáljuk az aktuális elemet, hogy benne van-e a másik két sorozatban. A tartalmazás vizsgálatot szintén alprogrammal valósítjuk meg, egy összetett feltételben. Algoritmus: Metszet(H1: tömb[N], H2: tömb[M], H3: tömb[L], K: tömb[N]) Deklaráció: i, j: egész Metszet kezdet //A közös rész (K) indexváltozójának inicializálása. j:=0 //A H1 sorozaton megyünk végig egyesével.  - eleme Ciklus i := 1-től N-ig Ha H1[i]  H2-nek és H1[i]  H3-nak akkor j := j+1 K[j] := H1[i] Ha vége Ciklus vége Metszet vége

Feladat: Határozzuk meg két 20 elemű egészeket tartalmazó sorozat közös elemeit! A sorozatok elemeit véletlen generátorral adjuk meg, ahol az egyes elemek 1..99 közül kerülhetnek ki. Java-kód: package metszet; import java.util.Random; public class Metszet { public static void main(String[] args) { // sorozatok (halmazok) deklarációi int[] h1 = new int[20]; int[] h2 = new int[30];

50. oldal



int[] kozos = new int[20]; // tömbök feltöltése véletlen elemekkel 1..99 feltolt(h1); feltolt(h2); // elemek listázása System.out.println("Első sorozat elemei:"); lista(h1); System.out.println("Második sorozat elemei:"); lista(h2); // közös rész meghatározása kozosResz(kozos, h1, h2); // a metszet elemeinek listázása System.out.println("A közös elemek:"); lista(kozos); } // a feltöltést végző metódus, // minden elem csak egyszer fordul elő public static void feltolt(int[] t){ Random rnd = new Random(); int vel; for(int i = 0; i < t.length; i++){ do{ vel = rnd.nextInt(99)+1; }while(benneVan(t, vel)); // ha előállítottunk egy olyat ami nics benne t[i] = vel; } } // elemet keresünk egy sorozatban public static boolean benneVan(int[] t, int v){ int i = 0; // a feltételek sorrendje nem mindegy while((i < t.length) && (t[i] != v)) i++; // az index értékétől függ, hogy megtaláltuk-e return i < t.length; } // a listázást végző metódus public static void lista(int[] t){ for(int i = 0; i < t.length; i++) System.out.print(t[i]+", "); System.out.println(""); } // a metszetet meghatározó metódus public static void kozosResz(int[] k, int[] t1, int[] t2){ int kIndex = -1; // a rövidebb sorozaton végigmegyünk for(int i = 0; i < t1.length; i++){ // megnézzük, hogy benne van-e // az adott elem a másik sorozazban // ha benn van beletesszük a közösbe if(benneVan(t2, t1[i])){ kIndex++; k[kIndex] = t1[i]; } } 51. oldal



} }

Futási kép: run: Első sorozat elemei: 72, 45, 69, 14, 63, 96, 51, 56, 64, 36, 29, 59, 89, 71, 90, 82, 93, 37, 11, 98, Második sorozat elemei: 5, 69, 34, 85, 3, 88, 90, 27, 4, 41, 82, 39, 63, 71, 91, 67, 6, 22, 15, 57, 58, 24, 66, 76, 40, 61, 38, 89, 42, 86, A közös elemek: 69, 63, 89, 71, 90, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, BUILD SUCCESSFUL (total time: 0 seconds)

A megvalósítás szépséghibája, hogy a közös sorozat elemeit a tömb teljes hosszáig kiírja. Egy megoldás lehet, ha a listázást a kozosResz() metóduson belül végezzük. Feladat: Készítsük el a fenti feladatot három bemeneti sorozatra.

Unióképzés tétele A bemenő sorozatokból készítünk egy kimenő sorozatot. Itt a bemenő sorozatok egyesítését (unióját) keressük. Az unióba bekerül az elem, ha része valamelyik kiindulási sorozatnak. A unió elemszáma maximálisan a kiindulási sorozatok elemszámainak az összege lehet. Itt is követelmény, hogy az egyes sorozatokban minden elem csak egyszer szerepel. A feladatot úgy oldjuk meg, hogy az első sorozatot teljes egészében beletesszük a kimenő sorozatba. Majd a többi sorozatot megvizsgáljuk, hogy van-e olyan elemük, amely még nincs benne az unió sorozatában és, ha van, akkor beletesszük. Algoritmus: //H1 és H2 halmazok, elemszámuk N, M  N //U azok egyesítése, elemszáma L = N+M Unio(H1: tömb[N], H2: tömb[M], U: tömb[L]) Deklaráció: i, j: egész Unio kezdet //Első sorozat átmásolása a kimenő (U) sorozatba. //i értékére szükségünk van i := 0 Ciklus, amíg i <= N i := i + 1 U[i] := H1[i] Ciklus vége //U feltöltése H2-es sorozat azon elemeivel, //amelyeket még nem tartalmaz. 52. oldal



//A ciklus a H2 elemein megy végig. Ciklus j := 1-től M-ig //Ha az aktuális elem nincs benne, akkor beletesszük. Ha H2[j]  U-nak, akkor //Az U sorozat indexének (i) értékét léptetni kell. i := i+1 U[i] := H2[j] Ha vége Ciklus vége Metszet vége

Az elemvizsgálat algoritmusa a metszetképzés tételénél található. Feladat: Az előző feladatot bővítve, készítsük el a két sorozat unióját. Java-kód: package metszetUnio; import java.util.Random; public class MetszetUnio { public static void main(String[] args) { // sorozatok (halmazok) deklarációi int[] h1 = new int[20]; int[] h2 = new int[30]; int[] kozos = new int[20]; int[] unio = new int[20+30]; // tömbök feltöltése véletlen elemekkel 1..99 feltolt(h1); feltolt(h2); // elemek listázása System.out.println("Első sorozat elemei:"); lista(h1); System.out.println("Második sorozat elemei:"); lista(h2); // közös rész meghatározása kozosResz(kozos, h1, h2); // a metszet elemeinek listázása System.out.println("A közös elemek:"); lista(kozos); // unió meghatározása unioKepzes(unio, h1, h2); System.out.println("Az egyesítés elemei:"); lista(unio); } // a feltöltést végző metódus, // minden elem csak egyszer fordul elő public static void feltolt(int[] t){ Random rnd = new Random(); int vel; for(int i = 0; i < t.length; i++){ do{ vel = rnd.nextInt(99)+1; }while(benneVan(t, vel)); // ha előállítottunk egy olyat ami nics benne

53. oldal


10 – 11. évfolyam t[i] = vel;

} } // elemet keresünk egy sorozatban public static boolean benneVan(int[] t, int v){ int i = 0; // a feltételek sorrendje nem mindegy while((i < t.length) && (t[i] != v)) i++; // az index értékétől függ, hogy megtaláltuk-e return i < t.length; } // a listázást végző metódus public static void lista(int[] t){ for(int i = 0; i < t.length; i++) System.out.print(t[i]+", "); System.out.println(""); } // a metszetet meghatározó metódus public static void kozosResz(int[] k, int[] t1, int[] t2){ int kIndex = -1; // a rövidebb sorozaton végigmegyünk for(int i = 0; i < t1.length; i++){ // megnézzük, hogy benne van-e // az adott elem a másik sorozazban // ha benn van beletesszük a közösbe if(benneVan(t2, t1[i])){ kIndex++; k[kIndex] = t1[i]; } } } // Az uniót meghatározó metódus public static void unioKepzes(int[] u, int[] t1, int[] t2){ // az első sorozatot teljes egészében // beletesszük az unió sorozatába int i; for(i = 0; i < t1.length; i++) u[i] = t1[i]; // az i értéke kilépve a ciklusból egyel nő!!! // végigmegyünk a második tömbön for(int j = 0; j < t2.length; j++) // ha még nincs benne a t1-ben a t2 aktuális eleme if(!benneVan(t1, t2[j])){ // akkor beletesszük az unióba u[i] = t2[j]; i++; } } }

Különbség-képzés tétele Egy A és B halmaz különbségén érjük azt az A\B-vel jelölt halmazt, amelynek elemei A-nak elmei, de B-nek nem.

54. oldal



A feladat megoldása: a kisebbítendő „A” sorozaton végigmegyünk, és ha az aktuális elem nincs benne a B sorozatban, akkor beletesszük a kimeneti (különbség) sorozatba. Algoritmus: //K = H1 \ H2 Különbség(H1: tömb[N], H2: tömb[M], K: tömb[L]) Deklaráció: i, j: egész Különbség kezdet j := 0 Ciklus i := 1-től N-ig Ha H1[i]  H2, akkor j := j + 1 K[j] := H1[i] Ha vége Ciklus vége Különbség vége

A „H1[i]  H2” (nem eleme) elemvizsgálat a tagadása a fentebb (unióképzésnél) megfogalmazott tartalmazás vizsgálatot megvalósító függvénynek. Feladat: Az előző feladatokat bővítve, készítsük el a sorozatok különbségét. (első \ második) Java-kód (program részlet): … public static void main(String[] args) { … int[] minus = new int[20]; // a méret a kisebbítendő elemszáma … // különbség meghatározása kulonbsegKepzes(minus, h1, h2); System.out.println("A különbség képzés elemei:"); lista(minus); } … // h1 - h2 különbség képzése public static void kulonbsegKepzes(int[] m, int[] h1, int[] h2){ int j = 0; for(int i = 0; i < h1.length; i++) if(!benneVan(h2, h1[i])){ m[j] = h1[i]; j++; } }

55. oldal



Rekurzió A rekurzió során a feladat megoldásához úgy jutunk el, hogy találunk egy ismételt egyszerűsítési folyamatot. Ennek a folyamatnak olyannak kell lennie, hogy véges sok lépésben eljussunk egy olyan állapotba, amelynél a megoldás már magától értetődő. Tehát, a problémát visszavezetjük egy egyszerűbb problémára, majd ezt az egyszerűsítést addig végezzük, amíg eljutunk a legegyszerűbb (triviális) esethez. Ezt megoldva, már az eggyel bonyolultabb eset is megoldható, míg végül eljutunk a teljes probléma megoldásához. Például az első N természetes szám összegének kiszámítása, visszavezethető az N-1 összegének meghatározására, amelyhez még hozzáadjuk az N értékét. összeg(N) = összeg(N-1) + N összeg(N-1) = összeg(N-2) + (N-1)

Ezt az egyszerűsítést addig folytatjuk, amíg N=0 legegyszerűbb esetet meg nem találjuk. Ha ezt ismerjük, akkor meg tudjuk oldani az N=1 esetet is. összeg(1) = összeg(0) + 1

Nézzük meg egy példán keresztül, legyen N = 5: összeg(5) összeg(4) összeg(3) összeg(2) összeg(1) összeg(0)

= = = = = =

összeg(4) összeg(3) összeg(2) összeg(1) összeg(0) 0

+ + + + +

5 4 3 2 1

Ez a triviális eset, innen fokozatosan megoldhatók a bonyolultabb esetek is. összeg(1) összeg(2) összeg(3) összeg(4) összeg(5)

= 0 +1 = 1+2 = 3 +3 = 6 +4 = 10 +5 = 15

Rekurzív függvények A rekurzív feladatokat, rekurzív alprogramokkal (eljárás, függvény) oldjuk meg. Beszélhetünk, 

közvetlen rekurzióról, amikor az alprogram saját magát hívja meg, illetve



közvetett rekurzióról, amikor az alprogram, egy másik alprogram által hívódik meg. Az „A” alprogram hívja „B” alprogramot, és „B” hívja „A”-t.

A rekurzív alprogramban szerepelnie kell:

56. oldal

Programozási tételek 


egy egyszerűsítési folyamatnak, amely lépésről-lépésre változik és a triviális esetben végződik,



egy küszöbfeltételnek, amely leállítja az egyszerűsítést.

Az alprogramok hívása során felépül egy hívási lánc, a triviális eset megtalálásáig. Majd ezután a lánc utolsó tagja (triviális eset) visszaadja a vezérlést a hívási lánc utolsó előtti tagjának. Miután megoldotta a saját részproblémáját, az ezt megelőző alprogramra kerül a vezérlés. A részproblémák megoldása a hívási lánc első eleméig folytatódik, amelynek végrehajtása során a teljes feladat megoldódik.7 Minden alprogram hívása során a verembe kerülnek a lokális változók, a paraméterek, és a visszatérési cím. A hívási láncon való visszajutást ez az adatszerkezet segíti. A rekurzió hátránya, hogy a verem egy véges adatszerkezet, ezért a rekurzió mélysége korlátozott. Illetve az

alprogramok

hívása

lassítja

a

feldolgozást.

Előnye

viszont

az

átláthatóbb

programszerkezet. Feladat: Határozzuk meg 1..20 intervallumból választott 10 véletlen egész szám összegét rekurzív algoritmussal. Java-kód: package rekurzivosszegzes; import java.util.Random; public class RekurzivOsszegzes { public static void main(String[] args) { Random rnd = new Random(); int szam; System.out.println("A program megadja 10 véletlenül választott " + "egész szám összegét."); for(int i = 1; i <= 10; i++){ //véletlen szám előállítása 1..20 között szam = rnd.nextInt(20)+1; System.out.print(i+". véletlen szám: "+szam); //rekurzív összegző függvény eredményének kiíratása System.out.println(" -- összege: "+osszegRek(szam)); } } //Az összegzést megvalósító rekurzív algoritmus public static int osszegRek(int n){ if(n == 0) return 0; 7

Juhász István – Programozási nyelvek 1 – Debreceni Egyetem, egyetemi jegyzet, 2001

57. oldal



else return osszegRek(n - 1) + n; } }

A rekurzív összegző függvény az első N természetes szám összegzését végzi. Leállító feltétele az (n==1) eset, ekkor az eredmény 1, egyébként újra hívja magát egyel kisebb értékkel (N-1. Így kialakul egy programhívási lánc, amely az N = 1 esetben leáll. Majd ezek után a függvényhívások fordított sorrendben kiértékelődnek, hozzáadódik az „N.” elem, és végül előáll az eredmény.

Rekurzív és iteratív forma Minden rekurzív feladatnak, van iteratív párja. Feladat: Számítsuk ki egy adott n nemnegatív egész szám összegét iteratív módon. Java-kód: package iterativosszegzes; import java.util.Random; public class IterativOsszegzes { public static void main(String[] args) { Random rnd = new Random(); int szam; System.out.println("A program megadja 10 véletlenül választott " + "egész szám összegét."); for(int i = 1; i <= 10; i++){ //véletlen szám előállítása 1..20 között szam = rnd.nextInt(20)+1; System.out.print(i+". véletlen szám: "+szam); //iteratív összegző függvény eredményének kiíratása System.out.println(" -- összege: "+osszegIter(szam)); } } //Az összegzést megvalósító iteratív algoritmus public static int osszegIter(int n){ int szum = 0; for(int i = 0; i <= n; i++) szum += i; return szum; } }

Iteratív formánál az összegzést végző metódus ciklust használ.

58. oldal



Feladat: Számítsuk ki egy adott n nemnegatív egész szám faktoriálisát (n!). Java-kód: package faktorialis; import java.util.Scanner; public class Faktorialis { public static void main(String[] args) { Scanner be = new Scanner(System.in); System.out.println("Faktoriális"); System.out.print("Szám: "); int szam = be.nextInt(); int n; //-1 végjelig folytatjuk while(szam != -1){ if(szam < 0) System.out.println("Csak nemnegatív számnak van faktoriálisa!"); else { n = faktRek(szam); System.out.println(szam+" faktoriálisa: "+n); } System.out.print("Szám: "); szam = be.nextInt(); } } //Faktoriálist számító metódus iteratív alak public static int fakt(int sz){ int n = 1; if(sz == 0) return 1; else{ while(sz > 0){ n *= sz; sz--; } return n; } } //Faktoriálist számító metódus rekurzív alak public static int faktRek(int sz){ if(sz == 0) return 1; else return sz * fakt(sz-1); } }

59. oldal



Gyorsrendezés (QuickSort) „Osztd meg és uralkodj” elve A gyorsrendezés (quicksort) az egyik leghatékonyabb rendező algoritmus, amely a rekurzióra épül. A rendezés alapja, hogy a sorozatot az elemek cserélgetésével két olyan részre osztjuk, amelynek elemei a sorozat egy kitüntetett eleménél kisebbek, illetve nagyobbak. Majd ezt a módszert alkalmazva a két részsorozatra, végül 1 elemű részsorozatokat kapunk, amelyek már önmagukban rendezettek. A kitüntetett elem lehet például a sorozat középső eleme. Rendezendő: 1. 6, 2, 5, 8, 4, 9, 3

Rendezés: 2. 3. 4. 5. 6. 7.

6, 6, 4, 4, 2, 2,

2, 2, 2, 2, 4, 3,

5, 5, 5, 3, 3 4

8, 3, 3, 5,

4, 9, 3 4, 9, 8 6, 8, 9 6

A rendezett sorozat: 2, 3, 4, 5, 6, 8, 9

A sárgával kiemelt elemek felcserélődnek. Aláhúzással lett jelölve az a kezdeti sorozat, illetve később a részsorozatok, amelyeken belül történik az elemek felcserélése. Az első sorban látható a rendezetlen sorozat. A második sorban a kitüntetett (középső) elem a 8-as. Megvizsgáljuk, hogy tőle balra csak kisebbek vannak-e, illetve jobbra csak nagyobbak. A nem megfelelő elemeket kicseréljük csere(8, 3). A harmadik sorban a 4, 9 egymáshoz képest jó helyen van. Ezután, mivel i > j kilépünk a ciklusból. Két részsorozat (6, 2, 5, 3, 4) és (9, 8) képződik, amelyet az első alapján elkezdünk rendezni. A rendezett számoknál nincs aláhúzás. A 6. sorban újra két sorozat van (2), és (4, 3), a 2 önmagában rendezett, így csak a (4, 3) sorozatot kell rendezni. Az utóbbi két számot felcserélve a sorozat rendezetté válik. A rendezéshez 6 cserére volt szükség. Algoritmus: Gyorsrendezés(Cím T: tömb[1..N] egész, alsó, felső: egész) i, j: egész középső: egész Gyorsrendezés kezdet i:= alsó j:= felső középső:= (alsó + felső) DIV 2 Ciklus Ciklus amíg T[i] < T[középső]

60. oldal



i:= i + 1 Ciklus vége Ciklus amíg T[j] > T[középső] j:= j – 1 Ciklus vége Ha i < j akkor Csere(T[i], T[j]) Ha vége Ha i <= j akkor i:= i + 1 j:= j – 1 Ha vége Ciklus vége Ha i > j Ha alsó < j akkor Gyorsrendezés(T, alsó, j) Ha vége Ha felső > i akkor Gyorsrendezés(T, i, felső) Ha vége Gyorsrendezés vége

61. oldal



Felhasznált és ajánlott irodalom 1. Angster Erzsébet – Objektumorientált tervezés és programozás – Java – 2002, 4KÖR Bt. 2. http://wiki.vmg.sulinet.hu/doku.php?id=informatika:programozas:tetelek – 2015.02. 3. Nagy Gusztáv – Java programozás – v1.3 – 2007 4. Nagy Zsolt – Középiskolai programozás oktatás Pascal nyelven – 2012, saját jegyzet

62. oldal

PROGRAMOZÁSI TÉTELEK. Java nyelven. Informatika Szakközépiskolai képzés. Nagy Zsolt

Recommend Documents