6. sada domácich zadaní

Najneskorší termín odovzdania: 17.4.2016 (nedeľa) o 21:00
Odovzdávané súbory: 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

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: 

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 (12 bodov) - 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 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).