Zadanie 6

Najneskorší termín odovzdania: 2.4.2023 (nedeľa) o 18:00
Odovzdávané súbory: NajdiSlovo.java, Vyskrtavacka.java, Rebus.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód

Hashovačka (3 body)

Každý objekt v Jave má metódu hashCode, ktorá vráti číselný otlačok obsahu objektu. Platí, že objekty s rovnakým obsahom majú rovnaký hash kód.

Z reťazca sa vytratili medzery, no našťastie máme uložený jeho hash kód. Vaša úloha je nasledovná: Do zadaného reťazca bez medzier doplňte medzery tak, aby výsledný reťazec mal rovnaký hash kód ako pôvodný reťazec s medzerami. Medzi každú dvojicu susedných znakov môžete doplniť nanajvýš jednu medzeru (inými slovami v pôvodnom slove medzery neboli na začiatku ani na konci a žiadne 2 medzery neboli susedné).

Vytvorte triedu NajdiSlovo a v nej metódu najdiRiesenie, ktorá pre zadaný reťazec bez medzier a hash kód (parametre konštruktora) nájde taký reťazec, ktorý vznikne doplnením medzier do zadaného reťazca a jeho hash kód bude rovnaký, ako bol zadaný. Ak taký reťazec neexistuje, metóda nech vráti null.


1
2
3
4
5
6
7
8
9
10
public class NajdiSlovo {

    public NajdiSlovo(String slovo, int hashCode) {

    }

    public String najdiRiesenie() {

    }
}

Poznámka: Svoju implementáciu môžete otestovať aj takto:


1
System.out.println(new NajdiSlovo("jetook", "je to ok".hashCode()))

Vyškrtávačka (2 body)

Uvažujme ľubovoľné prirodzené číslo a jeho zápis v desiatkovej sústave. Predpokladajme, že tento zápis neobsahuje cifru 0. Vyškrtávaním cifier (aspoň jednej ale nie všetkých cifier) v tomto zápise vieme dostať zápisy rôznych iných čísel. Napr. z čísla 313 vieme vyškrtávaním cifier dostať čísla 1 (3 1 3), 3 (3 1 3 alebo 3 1 3), 13 (3 1 3), 31 (3 1 3), 33 (3 1 3). Vytvorte triedu Vyskrtavacka a v nej metódu generuj, ktorá vráti množinu všetkých (rôznych) čísel, ktoré vieme dostať vyškrtávaním cifier z desiatkového zápisu zadaného čísla cislo (parameter konštruktora).


1
2
3
4
5
6
7
8
9
10
public class Vyskrtavacka {

    public Vyskrtavacka(int cislo) {

    }

    public Set<Integer> generuj() {

    }
}

Poznámka: Tým, že vyškrtávame aspoň jednu cifru ale nie všetky, vo výslednej množine budú čísla väčšie alebo rovné ako 1 a zároveň ostro menšie ako cislo.

Matematický rébus (5 bodov)

Igor našiel v jednom časopise takýto matematický rébus:

Vložte medzi niektoré cifry čísla 123456789 znamienko + alebo - tak, aby výsledok vytvoreného výrazu bol 100.

Igor ako skúsený riešiteľ rébusov rýchlo našiel riešenie: 100 = 123 - 45 - 67 + 89. Vtedy si ale Igor položil ďalšiu otázku. Koľko rôznych riešení má táto úloha?

Vytvorte pre Igora program, ktorý bude zisťovať, počet rôznych riešení rébusu. Program bude čítať vstup z textového súboru s názvom rebusy.txt:

1
2
3
4
123456789 100
123456789 99
12344321 325
111222333 22

Formát súboru je taký, že každý riadok predstavuje jeden rébus ako dve medzerou oddelené čísla. Prvé číslo (nanajvýš 15-ciferné) predstavuje postupnosť cifier a druhé číslo predstavuje požadovaný výsledok po vložení znamienok + a - do tejto postupnosti.

Program nech vytvorí výstupný súbor PoctyRieseni.txt, ktorý bude obsahovať pre každý rébus celkový počet jeho riešení – pre i-ty rébus bude počet jeho riešení zapísaný v i-tom riadku.

1
2
3
4
11
17
3
60