PoslednaRozcvicka, obsahujúcu statickú metódu
boolean najdiIndexy(int[] a, int c), ktorá pre dané pole a[] zistí, či existujú také dva indexy i a j, že súčet čísel
od a[i] po a[j] je presne hodnota c.
Vymyslite algoritmus s prinajhoršom kvadratickou časovou zložitosťou (teda O(n2)). Za horšiu časovú zložitosť bude primerane menej bodov.
V istej krajine majú ortonormálnu súradnicovú sústavu; os x smeruje na východ, os y na sever. Poloha každého mesta je určená dvojicou súradníc. Na rozdiel od súradníc však v krajine úplne chýbajú cesty. Vláda preto rozhodla, že postaví jednu priamu cestu vedúcu zo západu na východ. Polohu tejto cesty treba zvoliť tak, aby súčet vzdialeností jednotlivých miest od tejto cesty (priamky) bol čo najmenší.
Vytvorte triedu Cesta s metódou
double najlepsiaCesta(double[] x, double[] y),
ktorá dostane ako vstup súradnice všetkých miest v krajine
(x[i], y[i] sú súradnice i-tého mesta)
a vráti y-ovú súradnicu jednej z možných najlepších ciest.
Vo vyskumnom ustave musia do Vianoc stihnut kopu projektov. Kazdy projekt treba riesit istu dobu, pracuje na nom jediny vedec. V jednej chvili moze vedec pracovat len na jednom projekte a pocas celeho obdobia nesmie riesit viac ako dva projekty. Celkovo moze jeden vedec venovat projektom nanajvys 10 dni. Vasou ulohou je zistit, kolko najmenej vedcov treba zamestnat, aby sa vsetky projekty stihli.
Vytvorte v subore Rozcvicka.java triedu Rozcvicka s metodou
public static int pocetVedcov(String filename).
Tato metoda dostane ako argument nazov suboru. V tomto subore je v prvom riadku
prirodzene cislo udavajuce pocet projektov (nanajvys miliarda) a v druhom riadku
su uvedene doby trvania jednotlivych projektov udane v dnoch. Tieto doby su
reprezentovane realnymi cislami, oddelenymi od seba medzerou. Doby su v danom
subore usporiadane od najkratsej po najdlhsiu.
Navratovou hodnotou metody pocetVedcov() je minimalny pocet vedcov, ktorych treba zamestnat. Rozumne osetrite vynimky, ktore mozu vzniknut pri praci so suborom.
Spravne riesenia budu ohodnotene podla casovej zlozitosti pouziteho algoritmu:
class Faktor {
private int cislo;
private int pocetVlakien;
private String vystupnySubor;
public Faktor(int cislo, int pocetVlakien, String vystupnySubor) {
this.cislo = cislo;
this.pocetVlakien = pocetVlakien;
this.vystupnySubor = vystupnySubor;
}
}
Doplňte do triedy Faktor metódy
pridajDelitela(int n) - na koniec vystupneho suboru prida dalsi riadok s cislom n.spusti() - spusti paralelne vyhladavanie delitelov cisla cislo. Metoda pouzije presne pocVlakien.
Kazde vlakno musi byt instanciou tej istej triedy (nazvime ju napr. Pocitadlo). Mozete predpokladat, ze pocetVlakien < cislo.
Ak niektoré vlákno nájde deliteľa, zapíše ho do súboru pomocou metódy pridajDelitela.SpajacSuborov, ktora bude obsahovat nasledovne metody:
static void spojSubory(String outputFile, String[] files) - spoji textove subory vo files do jedneho suboru v tvare:
pocetSubor nazovSuboru1 pocetRiadkov1 obsahSuboru1 nazovSuboru2 pocetRiadkov2 obsahSuboru2 ...
static void rozspojSubory(String inputFile) - "rozpakuje" subor inputFile, ktory je vo vyssie uvedenom formate. Ak subor nie je vo zvolenom formate vyhodte vynimku InvalidFileFormatException.
Ak sa subor neda citat alebo nejde vytvorit cielove subory vyhodte vynimku IOException
static void spojRekurzivne(String outputFile, String[] files) - rovnako ako spojSubory, akurat pole files moze obsahovat aj adresare - v takom pripade treba spojit vsetky subory v adresary a jeho podadresaroch.
Na prechadzanie adresarov mozete pouzit triedu File - File.isDirectory(), File.list(), File.listFiles(), File.mkdirs()...
PrintableToFile obsahujuci metodu void printToFile(String filename);.
Ďalej definujte výnimku CanNotLoadException ako potom triedy Exception a
vytvorte interface LoadableFromFile obsahujuci metodu void loadFromFile(String filename) throws CanNotLoadException;.
Interface LoadableFromFile nech rozsiruje interface PrintableToFile.
Napiste triedu Publikacia, ktora implementuje LoadableFromFile a obsahuje nasledovne atributy a metody:
String nazovint rokString[] autoriString[] text - riadky textu (kazdy riadok je jeden prvok v poli)printToFile(String filename) - ulozi vsetky atributy do suboru tak, aby ich bolo mozne nacitat metodou loadFromFileloadFromFile(String filename) - nacita atributy zo suboruPublikacia(String filename) - nacita zo suboru vsetky udaje, nezabudnite osetrit vynimkyKniznica, ktora implementuje LoadableFromFile a obsahuje nasledovne atributy a metody:
String nazovKniznicePublikacia[] publikacieprintToFile(String filename) - ulozi vsetky publikacie do samostatnych suborov a tiez vytvori subor so zoznamom tychto suborov a nazvom knizniceloadFromFile(String filename) - na vstupe dostane subor so zoznamom publikacii a postupne naplni pole publikacie publikaciami z tohto zoznamuprivate char[][] mapa, ktora reprezentuje dvojrozmernu mapu;
jednotlive policka mapy su zem 'z' alebo voda 'v'. Tato trieda by mala mat nasledujuce metody:
Mapa(char [][] mapa), ktory si vytvori vlastnu kopiu mapy danej ako argument a referenciu na tuto kopiu ulozi do this.mapa;
boolean containsGarden() -- tato metoda vrati true, ak mapa obsahuje stvorec velkosti 2x2,
v ktorom vsetky policka su zem, inak vrati false;
boolean isReachable(int x1, int y1, int x2, int y2) -- vrati true prave vtedy, ked existuje cesta
z policka so suradnicami (x1,y1) na policko so suradnicami (x2,y2);
cela cesta vratane zaciatku a konca musi lezat na zemi
a kazde jej dve po sebe iduce policka musia mat spolocnu stranu (nestaci roh).
public class Automat {
public int[] stavy; // pociatocny stav je 0
public char[] symboly;
public int akceptacnyStav;
public String[] pravidla;
/*prechodove pravidla automatu - kazdy prvok pola je v tvare
"cislo_stavu;znak;novy_stav"
(napr. "1;a;2" znamena ze na symbol a v stave 1 prejde do stavu 2)*/
public int aktStav = 0;
public Automat(int[] stavy,char[] symboly,int acekptacnyStav,String[] pravidla) {
//inicializuje globalne premenne podla premennych zo vstupu
//ak sa v tabulke pravidiel nachadza symbol, ktory nie je
//v mnozine symbolov, konstruktor vypise na standardny vystup chybu
}
public boolean overCiAkceptuje(String slovo) {
//vrati true ak automat slovo akceptuje, inak false;
//zaroven na standardny vystup vypisuje priebeh simulacie,
// t.j. dvojice (aktualny stav a symbol).
}
}
Trieda Automat moze obsahovat aj ine neverejne metody.
Dalej naprogramujte triedu Rozcvicka1, ktora bude obsahovat metodu public static void main(String args[]) a odsimuluje automat pre jazyk a^nbc^m na slove aaaabccc.
Mozete vyuzit triedy Arrays na pracu s polami. Na pracu s tabulkou pravidiel mozete pouzit metodu split() triedy String.
public class MojePole {
public int[] obsah;
public MojePole(int dlzka) {
/*konstruktor, ktory vytvori nove pole obsah dlzky "dlzka"
s hodnotami od 1 po "dlzka"*/
}
public void pridajPrvky(MojePole a) {
/*vytvori nove pole obsah, ktore bude obsahovat
povodne prvky pola obsah a za nimi prvky obsahu a*/
}
public void prenasobPrvky(int x) {
//prenasobi kazdy prvok pola cislom x
}
public void vymazPrvky(MojePole a) {
/*vytvori nove pole obsah, v ktorom budu
povodne prvky z pola obsah okrem tych, ktore su v obsahu a*/
}
public void vypisMa() {
/*vypise prvky pola obsah oddelene medzerou a ukoncene
novym riadkom na standardny vystup*/
}
}
Dalej vytvorte triedu Rozcvicka2 s metodou public static void main(String[] args), ktora len vyuzitim triedy MojePole (a jej instancii)
vypise na standardny vystup "1 3 5 7 9 1 3 5 7 9".