Utolsó módosítás: 2016.10.05.
A feladatok megoldásában használjuk a láthatósági módosítókat (public, private)!
Írjunk egy math.Matrix osztályt, melyben néhány mátrixműveletet valósítunk meg! Ezek az alábbiak:
A plus() osztályszintű metódus paraméterül vár két kétdimenziós tömböt, melyeket összeadja. Az eredményt egy harmadik tömbben adja vissza.
Az \(A\) és a \(B\) mátrix \(C\) összegét megkapjuk a \(C_{ij} = \sum_{k=0}^{n} A_{ik} + B_{kj}\) kiszámításával minden \(i\), \(j\)-re.
Haladóknak. Hasonlóan a plus() metódushoz, készítsünk egy multiply() metódust, mely paraméterül vár két kétdimenziós tömböt, és a szorzás eredményét egy új tömbben adja vissza!
Az \(A\) és a \(B\) mátrix \(C\) szorzatát megkapjuk a \(C_{ij} = \sum_{k = 0}^n A_{ik} \times B_{jk}\) kiszámításával minden \(i\), \(j\)-re.
Készítsünk egy util csomagban található IntList osztályt, mely egészekből álló listát valósít meg tömbbel! Legyen
Egy egészeket tartalmazó tömb adattagja.
Egy konstruktora, mely nem vár paramétert.
Egy konstruktora, mely egy másik IntList-et vár paraméterül. A paraméterbeli tömböt használjuk inicializálásra, a tartalmát le kell másolni elemről-elemre.
Az IntList mérete mindig pont akkora, hogy el tudja tárolni a számokat. Tehát add() hatására megnő eggyel, míg remove() hatására összemegy eggyel. Az új, nagyobb vagy kisebb tömb előállításához használjuk a java.utils.Arrays.copyOf() statikus metódust!
Az IntList rendelkezzen az alábbi metódusokkal:
size(), mely megadja az eltárolt egészek számát.
get(), mely visszaadja az első számot.
get(), mely visszaadja az adott indexen tárolt egész számot (túlterhelt változat).
add(), mely egy egész számot szúr be a lista végére.
add(), mely egy egész számot egy megadott pozícióra szúr be (túlterhelt változat).
toString(), mely szöveggé alakítja a listát. Az elemek vesszővel elválasztva szerepelnek a szövegben.
fromString() statikus metódus, mely szövegből készít listát. A szövegben a számokat szóközzel elválasztva adjuk meg. Amennyiben nem sikerült a számok kiolvasása a szövegből, adjunk vissza null-t. Például jó paraméter az 1 3 5 szöveg.
Szorgalmi feladat. Valósítsuk meg az alábbi metódusokat is.
set(), mely egy adott indexen lévő számot felülír egy megadott számmal.
remove(), mely eltávolítja az utolsó elemet.
remove(), mely eltávolítja az adott indexen található számot, és visszaadja az eltávolított számot (túlterhelt változat).
indexOf(), mely visszaadja egy paraméterül kapott egész első előfordulásának indexét. Ha az egész nincs a listában, adjunk vissza \(-1\)-et.
concat(), mely a lista végére fűz egy másik IntList-et.
Írjunk programot, mely sorokat olvas be a szabványos bemenetről, amíg tud! Ezután fordított sorrendben írja ki a sorokat a szabványos kimenetre! A sorok eltárolására használjuk a java.util.LinkedList<A> osztályt!
Megjegyzés:
A parancssorban (Linuxon) Ctrl-C vagy (Windowson) Ctrl-Z kombinációval tudjuk jelezni a programnak, hogy nincs több sor, amelyet be kellene olvasnia.
Annak eldöntésére, hogy van-e még beolvasásra váró sor, használjuk a java.util.Scanner osztály hasNextLine() metódusát! A következő sort a nextLine() metódussal tudjuk beolvasni.
Szorgalmi feladat. Írjunk programot, mely beolvas egy sort a szabványos bemenetről, és eldönti, hogy benne szereplő zárójelek kiegyensúlyozottak vagy sem! Például a "[()]{}{[()()]}" bemenetre logikai igazat kell visszaadnia, de a "[()" vagy a "[)]" bemenetre már hamisat.
Megjegyzés: használjunk egy vermet, például a java.util.Stack osztályt.
Haladóknak. Készítsük el a util.IntTree osztályt, mely egész számokat rendezetten tároló bináris fát megvalósít meg! A fa minden csúcsának nulla, egy vagy két gyermeke lehet és legfeljebb egy szülője. Ha egy csúcsnak nincs szülője, úgy az a csúcs a fa gyökere.
A láncolást egy-egy IntTree objektumra mutató referenciákkal oldjuk meg, melyek egy csúcs bal és jobb oldali gyerekére mutatnak. Emellett minden csúcs egy egész számot is tárol.
Valósítsuk meg az alábbi műveleteket az IntTree osztályon belül:
Konstruktor, mely egy int értékből létrehoz egy egyelemű fát, a gyökerében a megadott int értékkel.
insert(), mely beszúr egy int értéket a fába. Ha a szám kisebb, mint az aktuális csúcsban tárolt szám, akkor a bal oldali részfába szúrjuk be (rekurzívan). Ha nagyobb vagy egyenlő, akkor a jobb oldali részfába szúrjuk be (szintén rekurzívan). Ha nincs bal vagy jobb oldali részfa, ahova beszúrnánk, akkor hozzunk lérte egy új csúcsot a beszúrandó számmal.
contains(), mely eldönti, hogy egy paraméterként kapott szám megtalálható-e a fában (rekurzívan). Ha nem találtuk még meg és a kapott szám kisebb, mint az aktuális csúcsban tárolt, úgy a bal oldali részfában keresünk tovább, különben pedig a jobb oldaliban.
toArray(), mely egy int értékekből álló tömbben adja vissza a fában eltárolt értékeket. A tömbben először a bal oldali részfában tárolt elemek legyenek, majd a gyökérben tárolt elem, végül a jobb oldali részfában tárolt elemek. A tömbben a számok rendezettek lesznek. Ezt a bejárást hívják inorder bejárásnak.
toString() metódus, mely a fában tárolt értékek felsorolását adja vissza szövegként.
Készítsünk programot, mely egész számok sorozatát rendezi a bináris fa segítségével! A program sorban bekér egész számokat, melyeket beszúrja a fába. Ha elfogytak a számok, úgy a fa inorder bejárásával megkapjuk a rendezett sorozatot. Írjuk is ki a képernyőre a rendezett sorozatot!
Haladóknak: írjunk programot a Josephus-probléma megoldására! A probléma szerint \(n\) ember szörnyű helyzetbe kerül az ellenséggel vívott háborúban, és csapdába esik egy barlangban. Mivel nem akarnak fogságba esni, ezért úgy döntenek, hogy sorban végeznek magukkal. Így tehát leülnek egy körben (\(0\)-tól \(n-1\)-ig számozott pozícióban), és körbe haladva minden \(m.\) ember végez magával, egészen addig, míg csak egy ember marad. Azonban a híres matematikus, Josephus nem akar részt venni ebben az őrültségben, így kigondolja, hova kell ülnie, hogy utolsónak életben maradjon.
Írjunk programot, mely bekéri \(n\) számot, majd sorban kiírja, milyen pozíción ülő emberek végeztek magukkal, és segít Josephusnak, hogy hová üljön hogy életben maradjon! Kezdetben minden második ember végez magával (\(m = 2\)).
Általánosítsuk a programunkat, hogy tetszőleges \(m\) számra működjön!