Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Cvičenia 17

Z Programovanie
Prejsť na: navigácia, hľadanie

Index riadkov

Na prednáške sme mali program, ktorý pomocou HashMap<String,Integer> spočítal počty výskytov slov na vstupe. Teraz chceme zmenenú verziu tohto programu, ktorá vypíše zoznam slov a pre každé slovo zoznam čísel riadkov, na ktorých sa toto slov nachádza. Slová budú usporiadané podľa abecedy, riadky vzostupne. Ak je slovo na riadku viackrát, uvedie sa toto číslo iba raz. Odporúčame použiť TreeMap<String,TreeSet<Integer>>.

Príklad vstupu a výstupu (vstup sú prvé tri riadky):

jeden dva tri jeden
jeden styri tri

Slovo dva sa vyskytuje na riadkoch: 1
Slovo jeden sa vyskytuje na riadkoch: 1 2
Slovo styri sa vyskytuje na riadkoch: 2
Slovo tri sa vyskytuje na riadkoch: 1 2

Kostra programu:

import java.util.*;
import java.io.*;  
public class Prog {
   public static void main(String[] args) throws IOException {

       //TODO: VAS KOD NA INICIALIZACIU MAPY TU

	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	int lineNumber = 0;  // pocitadlo cisel riadkov
	while (true) {
            // nacitame riadok do retazca
            String line = in.readLine();
            // skoncime, ked uzivatel zada prazdny riadok 
	    // alebo ked prideme na koniec vstupu (null)
            if (line == null || line.equals("")) { 
                break;
            }
	    lineNumber ++;

	    // inicializujeme scanner, ktory rozlozi riadok na slova
	    Scanner scanner = new Scanner(line);
	    while(scanner.hasNext()) {
		String word = scanner.next();
		// TODO VAS KOD NA SPRACOVANIE SLOVA TU

	    }
        }

	// TODO: VAS KOD NA VYPIS VYSLEDKU TU
   }
}

Metódy equals, hashCode, compareTo

Napíšte triedu Zlomok, ktorá bude implementovať zlomok s celočíselným čitateľom a menovateľom.

  • Triede spravte konštruktor a preťažte equals tak, aby správne testovala rovnosť zlomkov a hashCode tak, aby bol konzistentný s equals.
  • Vaša trieda by tiež mala implementovať interface Comparable s bežným porovnaním zlomkov podľa veľkosti.
  • Prekryte aj metódu toString aby vrátila reťazec typu "a/b"
  • Skúšajte zlomky vkladať do TreeSet a HashSet a skontrolujte, že dostávate správne výsledky.
  • Pre jednoduchosť môžete predpokladať, že čitateľ aj menovateľ sú kladné a že nedôjde k pretečeniu rozsahu čísla typu Integer pri aritmetických operáciách.
  • Môže sa vám zísť Euklidov algoritmus na nájdenie najväčšieho spoločného deliteľa:
    // ratame nsd(a,b)
    while(b != 0) {
        int x = a % b;
        a = b;
        b = x;
    }
    // vysledok je v premennej a

Generické statické metódy

  • Napíšte generickú statickú metódu prienik, ktorá dostane dve SortedSet (s tým istým typom prvkov E) a vráti SortedSet obsahujúcu ich prienik, t.j. prvky, ktoré sa nachádzajú v oboch.
    • Použite algoritmus podobný na merge, pričom sa posúvate dvoma iterátormi (iterátory pre SortedSet vracajú prvky v utriedenom poradí).
    • Potrebujete si tiež pamätať aktuálny prvok z každej množiny, lebo po volaní next sa už späť k tomu istému prvku nedostanete.

Metóda remove

Trieda ArrayList (ale aj LinkedList a iné triedy implementujúce List) má dve metódy s menom remove, ale s iným typom parametra

  • remove(int index) zmaže prvok na pozícii index
  • remove(Object o) zmaže prvý výskyt prvku o

Úloha:

  • Zistite experimentovaním, ktorá z metód remove sa vykoná v nasledujúcom kóde.
  • Zmeňte kód tak, aby sa zavolala opačná forma metódy remove.

Pozor, podobná zámena metód môže byť zdrojom zákernej chyby v programe.

import java.util.ArrayList;
public class Prog {
    public static void main(String[] args) {
        Integer[] tmp = {3,2,1};
        ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(tmp));
        System.out.println("Pred remove:" + a);
        a.remove(1);
        System.out.println("Po remove: " + a);

    }
}

Riešenie Index riadkov

import java.util.*;
import java.io.*;  
public class Prog {
   public static void main(String[] args) throws IOException {

       Map<String,TreeSet<Integer>> map = new TreeMap<String,TreeSet<Integer>>();

	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	int lineNumber = 0;  // pocitadlo cisel riadkov
	while (true) {
            // nacitame riadok do retazca
            String line = in.readLine();
            // skoncime, ked uzivatel zada prazdny riadok 
	    // alebo ked prideme na koniec vstupu (null)
            if (line == null || line.equals("")) { 
                break;
            }
	    lineNumber ++;

	    // inicializujeme scanner, ktory rozlozi riadok na slova
	    Scanner scanner = new Scanner(line);
	    while(scanner.hasNext()) {
		String word = scanner.next();
                TreeSet<Integer> wordOccurences;
                if (map.containsKey(word)) {
                    wordOccurences = map.get(word);
                } else {
                    wordOccurences = new TreeSet<>();
                    map.put(word, wordOccurences);
                }
                wordOccurences.add(lineNumber);
	    }
        }

        map.forEach((key, value)
            -> System.out.println(key + " " + value));
   }
}


Riešenie Zlomok


public Zlomok(int citatel, int menovatel) {
        
        super();
        
        this.citatel = citatel;
        this.menovatel = menovatel;
        
        int nsd = vypocitajNsd();
        this.zakladCitatel = citatel / nsd;
        this.zakladMenovatel = menovatel / nsd;
    }

    /*
     * Metoda, ktora danemu zlomku zrata nsd
     */
    private int vypocitajNsd() {
        int a = this.citatel;
        int b = this.menovatel;
        while (b != 0) {
            int x = a % b;
            a = b;
            b = x;
        }
        return a;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Zlomok) {
            Zlomok other = (Zlomok) o;
            return ((this.zakladCitatel == other.getZakladCitatel()) && 
                    (this.zakladMenovatel == other.getZakladMenovatel()));
        }
        return false;
    }

    /*
     * Metoda vracia 1 ak tento zlomok je vacsi ako argument,
     * 0, ak sa rovnaju, -1 inak
     * (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(Zlomok other) {
        
        if (this.equals(other)) {
            return 0;
        }
        double myValue = ((double) this.zakladCitatel) / this.zakladMenovatel;
        double otherValue = ((double) other.getZakladCitatel()) / other.getZakladMenovatel();
        if (myValue > otherValue) {
            return 1;
        }
        return -1;
    }

    @Override
    public int hashCode() {
        return this.zakladCitatel * 31 + this.zakladMenovatel;
    }

    public int getZakladCitatel() {
        return zakladCitatel;
    }

    public int getZakladMenovatel() {
        return zakladMenovatel;
    }

    
    public static void main(String[] args) {
        
        Set<Zlomok> zlomky = new HashSet<Zlomok>();
        
        zlomky.add(new Zlomok(1, 2));
        zlomky.add(new Zlomok(2, 4));
        System.out.println(zlomky.size()); // 1
        
        zlomky.add(new Zlomok(2, 5));
        System.out.println(zlomky.size()); // 2
        
        System.out.println(zlomky.contains(new Zlomok(1, 2))); // true
        System.out.println(zlomky.contains(new Zlomok(3, 6))); // true
        System.out.println(zlomky.contains(new Zlomok(3, 7))); // false
    }
}