6. sada domácich zadaní

Najneskorší termín odovzdania: 7.4.2019 (nedeľa) o 21:00
Odovzdávané súbory: NajdiSlovo.java, Vyskrtavacka.java, Rebus.java, Tabulka.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, časť 1)

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.

public class NajdiSlovo {

    public NajdiSlovo(String slovo, int hashCode) {

    }

    public String najdiRiesenie() {

    }
}
[$[Get Code]]

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

System.out.println(new NajdiSlovo("jetook", "je to ok".hashCode()))
[$[Get Code]]

Vyškrtávačka (2 body, časť 1)

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 (313), 3 (313 alebo 313), 13 (313), 31 (313), 33 (313). 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).

public class Vyskrtavacka {

    public Vyskrtavacka(int cislo) {

    }

    public Set<Integer> generuj() {

    }
}
[$[Get Code]]

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, časť 2)

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: 

123456789 100
123456789 99
12344321 325
111222333 22
[$[Get Code]]

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. 

11
17
3
60
[$[Get Code]]

Úžasná Allison (max. 12 bodov, časť 2) - pre fajnšmekrov

Nedávno ma zaujala jedna časť TV show zo série Penn&Teller s názvom Úžasná Allison:

Nie, nezaujal ma trik, vďaka ktorému sa je možné "dozvedieť sa" myslené a neskôr napísané číslo, ale prezentácia tohto triku. Myslené číslo sa neodhalí ihneď, ale Allison toto číslo skryje do 16 čísel v tabuľke 4x4 (viac vo videu). Určite sa vám po prezretí videa v hlave vynoria otázky (ak nie, tak sa tak aspoň chvíľu tvárme):

  • Existuje pre ľubovoľné dvojciferné číslo X väčšie ako 25 také vyplnenie tabuľky, že príslušné súčty budú práve X? Alebo existuje len pre nejaké X?
  • Prečo X musí byť aspoň 25? Je táto podmienka nevyhnutná?
  • Naučila sa Allison pre každé X ako vyplniť tabuľku? Alebo je tam nejaký vzor/algoritmus ako vyplniť tabuľku, aby súčty vyšli X?
  • Tabuľka by mala vyzerať nejako náhodne. Existuje také vyplnenie tabuľky, že všetky čísla sú rôzne? Ak nie, dá sa trebárs vyžadovať, aby každé číslo sa opakovalo najviac 2 razy? Alebo 3 razy?

Úloha: Analyzujte možnosti vyplnenia tabuľky v tomto triku. Ako rozumné sa zdá začať s vytvorením programu, ktorý pre zadané číslo X nájde jedno (alebo viaceré?) vyplnenia tabuľky kladnými nenulovými číslami, že príslušné štvorice čísel majú súčet presne X. Uvažujeme tieto štvorice:

  • 4 riadky,
  • 4 stĺpce,
  • obe uhlopriežky,
  • čísla v rohoch mriežky,
  • čísla v každom podštvorci s rozmermi 2 x 2 (je 9 takých podštvorcov).

Je to menej štvoríc a aj iné štvorice ako bolo v show - kvôli zjednodušeniu. Pri iných videách sa dá vidieť, že Allison tiež od niektorých štvoríc upustila: https://www.youtube.com/channel/UCUSEn9drforS2TNfeSK5RVA/videos

Odovzdajte:

  1. Doimplementovaný súbor Tabulka.java s triedou Tabulka:
public class Tabulka {
        // Privatne instancne premenne a pomocne privatne metody pridajte podla
        // uvazenia.

        /**
         * Konstruktor: musi byt bezparametrovy
         */
        public Tabulka() {

        }

        /**
         * Metoda, ktora pre zadane cislo vrati tabulku 4 x 4, ktorej sucty
         * uvazovanych stvoric su presne x. Tato metoda bude na kazdej instancii
         * volana prave raz.
         */
        public int[][] vytvorPreCislo(int x) {
                return null;
        }
}
[$[Get Code]]
V triede Tabulka implementujte čo najefektívnejšiu metódu vytvorPreCislo, ktorá pre zadané celé číslo medzi 25 a 99 vráti 2D pole s rozmermi 4x4 vyplnené kladnými nenulovými celými číslami pričom:
  • súčet všetkých uvažovaných štvoríc je presne x a
  • žiadne číslo sa v tabuľke nenachádza viac ako 2 razy.
Ak požadované vyplnenie tabuľky neexistuje, metóda nech vráti null.
Trieda Tabulka je kontrolovaná evaluátorom. Pri efektívnej implementácii môžete využiť výsledky analýzy (ak analýza nejaké užitočné vlastnosti, použite ich pri implementácii tejto triedy).
  1. Akékoľvek zdrojové kódy, ktoré ste vytvorili za účelom analýzy úlohy.
  2. Písomnú správu, z ktorej je jasné, ako ste postupovali pri riešení - mal by to byť report, na základe ktorého by hodnotiteľ vedel zistiť, ako ste postupovali, kvôli čomu ste vytvárali jednotlivé programčeky, ktorých zdrojové kódy prikladáte. Zároveň správa by mala obsahovať nejaké závery - napr. odpovede na niektoré otázky naznačené v úvode.

Riešenia, ktoré nebudú obsahovať všetky 3 požadované časti, nebudú hodnotené (ak "akékoľvek podporné zdrojové kódy" tvorí len trieda Tabulka, nemusíte v rámci tejto druhej časti odovzdávať nič ďalšie).