Programovanie, algoritmy, zložitosť 2007

2007/09/23

Oznamy

Úvod a podmienky na zápočet

Projekty

Teoretické cvičenia

Cvičenie 1 (28. 9. 2007)

Úvod k Jave. Triedy a objekty. Objekty majú stav (inštančné premenné) a chovanie (metódy).

Cvičenie 2 (5. 10. 2007)

Vytváranie inštancií. Čo sa deje na halde pri vytváraní objektu. Primitívne dátové typy a polia.

Cvičenie 3 (12. 10. 2007)

Metódy na menenie stavu (gettre a settre) a ich zdôvodnenie. Polia, zoznamy. Špeciálne metódy - toString(), equals(), hashCode().

Cvičenie 4 (27. 10. 2007)

Balíčky ako prostriedok na zmiernenie chaosu v triedach. Preťažené metódy. Konštruktory.

Cvičenie 5 (9. 11. 2007)

Dedičnosť a polymorfizmus na príklade orchestra.

Cvičenie 6 (16. 11. 2007)

Dedičnosť metód - podrobnosti a mechanizmy. Abstraktné triedy a abstraktné metódy. Dedičnosť inštančných premenných. Modifikátory viditeľnosti.

Cvičenie 7 (23. 11. 2007)

Dedenie konštruktorov. Pretypovanie.

Cvičenie 8 (30. 12. 2007)

Písomka

Cvičenie 9 (7. 12. 2007)

Viacnásobná dedičnosť - interfejsy:

Cvičenie 10 (15. 12. 2007)

Výnimky.

Statické metódy.

Praktické cvičenia

Cvičenie 1 (27. 9. 2007)

Domáca úloha (do 3. 10. 2007)

  1. Vyskúšajte si program Hello World.
  2. Vytvorte triedu Maximum, ktorej je možné zasielať postupne celé čísla. Objekt typu Maximum má vrátiť maximálne číslo, ktoré bolo doň vložené od chvíle vytvorenia jeho inštancie.
  3. Vytvorte triedu Palindrom s metódou, ktorá vie pre daný reťazec zistiť, či je to palindrom (teda reťazec, ktorý sa číta rovnako spredu i zozadu). Príklad: reťazec mordnilapejepalindrom.
  4. Vytvorte triedu OperacieSPoliami, ktorá bude reprezentovať prácu s poliami celých čísel:
    1. súčet dvoch polí celých čísel rovnakej dĺžky po zložkách

príklad: [2, 4, 5, 6] + [2, 3, 5, 2] = [4, 7, 10, 8]

2. rozdiel dvoch polí celých čísel rovnakej dĺžky po zložkách

príklad: [2, 4, 5, 6] - [2, 3, 5, 2] = [0, 1, 0, 4]

3. zlepenie dvoch polí celých čísel  (konkatenácia)

príklad: [2, 4, 5, 6] zlep [2, 3, 5, 2] = [2, 4, 5, 6, 2, 3, 5, 2]

Cvičenie 2 a 3 (4. 10. 2007 a 10. 10. 2007)

Študenti sa každý rok zúčastňujú na Prírodovedeckých dňoch. Jednou z disciplín je súťaž v pití piva. Chceme vyrobiť informačný systém, ktorý bude evidovať koľko piva ktorý študent vypil a ktorý zo študentov vypil najviac piva. Súťaž v pití piva prebieha po kolách - každé kolo vypije každý učastník jedno pivo. Každý študent má však alkoholický strop (vypočítaný ako vek študenta + ročník - 15). Keď študent dosiahne alkoholický strop, nemôže v súťaži pokračovať (teda vypadáva).

Navrhnite vhodný objektový model a implementujte vhodné triedy, ktoré budú zodpovedať tomuto informačnému systému - teda budú simulovať súťaž.

Domáca úloha (do 16. 10. 2007)

Cvičenie 4 (17. 10. 2007)

Momentálnym hitom je súťaž Slovensko hľadá SuperStar. Samotné vyraďovanie súťažiacich prebieha pomocou castingov (casting sa koná v jednom meste), kde ho vykonávajú porotcovia (maximálne traja na 1 casting).

Navrhnite vhodné triedy a metódy na pridanie súťažiaceho do castingu, na pridanie porotcu do castingu, pričom zabezpečte, aby casting mal naozaj najviac troch porotcov. Použite gettery a settery a privátne inštančné premenné.

Na všetkých triedach definujte metódu toString().

Cvičenie 5 (24. 10. 2007)

Porotca slúži v castingu na to, aby odfiltroval nevhodných súťažiacich. V skutočnej SuperStar existuju určite nejaké striktné kritéria na filtrovanie súťažiacich, my sa však obmedzíme na to, že každý porotca bude súťažiacich vyhadzovať náhodne. (Každý porotca pri vyhadzovaní súťažiaceho si vygeneruje náhodné číslo, ktoré určí, či súťažiaci prešiel alebo nie).

Dopracujte do porotcu metódu na vyhadzovanie súťažiacich. Dopracujte do castingu metódu, ktorá odfiltruje súťažiacich v danom castingu tak, že súťažiaci prejde postupne každým porotcom a pokiaľ ho schvália všetci porotcovia, ostáva v súťaží naďalej.

Skúste nahadzovať do castingu náhodný počet súťažiacich a simulovať chovanie porotcov.

Domáca úloha (do 7. 11. 2007)

Cvičenie 6 + 7 (8. 11. 2007 + 15. 11. 2007)

Firma Známosti s.r.o. chce vytvoriť systém pre vyhľadávanie optimálnych partnerských dvojíc. Kandidáti, ktorí sa chcú registrovať v systéme, musia poskytnúť meno, vek, pohlavie a záľuby.

Navrhnite a implementujte metódy pre registráciu človeka v systéme a vyhľadávanie optimálneho partnera pre daného človeka. Zvážte použitie viacparametrových konštruktorov, a preťažených metód.

Domáca úloha (do 28. 11. 2007)

Implementujte kompletný informačný systém. Odporúčaná stratégia na vyhľadávanie partnerov je nasledovná: každému z partnerov v systéme priradíme bodové ohodnotenie. Za kompatibilné pohlavie priradíme 3 body, za kompatibilný vek (najviac o tri roky starší a najviac o tri roky mladší) 1 bod a za spoločné záľuby (aspoň dve spoločné záľuby) 2 body.

Cvičenie 8 + 9 (22 + 29. 11. 2007)

V rovine sa nachádzajú geometrické útvary - štvorce, obdĺžniky a kružnice. Nájdite dva najvzdialenejšie útvary, pričom vzdialenosť rátame ako vzdialenosť ťažísk. Údaje o útvaroch načítavajte do roviny zo súboru.

Použitie triedy java.io.Scanner je na samostatnej stránke.

Cvičenie 10 (6. 12. 2007)

Do roviny pridáme nový geometrický útvar - bod. Navyše, pre ostatné geometrické útvary dodáme možnosť zafarbiť sa a vyrátať svoj obsah.

Doimplementujte príslušné metódy a zabezpečte, aby rovina vedela zistiť súčet obsahov všetkých svojich útvarov. (Pre jednoduchosť predpokladáme, že útvary sa neprekrývajú).

Cvičenie 11 (13. 12. 2007)

Dopracujte interface, ktorý reprezentuje zafarbiteľný útvar. Zabezpečte, aby štvorce a kruhy boli zafarbiteľné nejakou farbou. Do roviny dopracujte metódu, ktorá zráta obsah zafarbiteľných útvarov.

Vytvorte triedu, ktorá načíta zo súboru dáta o útvaroch a vráti ich ako zoznam geometrických útvarov. Odchytávajte korektne vyhodené výnimky.

Cvičenie 12 (20. 12. 2007)

Zabezpečte, aby metóda pre načítavanie útvarov hádzala výnimku ChybaPriNačítavaníException. Táto výnimka nech má konštruktory zdedené od triedy Exception.

Táto výnimka nech sa hádže aj pri nekorektných alebo chýbajúcich dátach k útvaru.

Domáca úloha

Zašlite hotový projekt s geometrickýcmi útvarmi z predošlých cvičení.

Praktické cvičenia (pondelok)

Cvičenie 5 (29. 10. 2007)

Momentálnym hitom je súťaž Slovensko hľadá SuperStar. Samotné vyraďovanie súťažiacich prebieha pomocou castingov (casting sa koná v jednom meste), kde ho vykonávajú porotcovia (maximálne traja na 1 casting).

Navrhnite vhodné triedy a metódy na pridanie súťažiaceho do castingu, na pridanie porotcu do castingu, pričom zabezpečte, aby casting mal naozaj najviac troch porotcov. Použite gettery a settery a privátne inštančné premenné. Na všetkých triedach definujte metódu toString().

Porotca slúži v castingu na to, aby odfiltroval nevhodných súťažiacich. V skutočnej SuperStar existuju určite nejaké striktné kritéria na filtrovanie súťažiacich, my sa však obmedzíme na to, že každý porotca bude súťažiacich vyhadzovať náhodne. (Každý porotca pri vyhadzovaní súťažiaceho si vygeneruje náhodné číslo, ktoré určí, či súťažiaci prešiel alebo nie).

Dopracujte do porotcu metódu na vyhadzovanie súťažiacich. Dopracujte do castingu metódu, ktorá odfiltruje súťažiacich v danom castingu tak, že súťažiaci prejde postupne každým porotcom a pokiaľ ho schvália všetci porotcovia, ostáva v súťaží naďalej.

Skúste nahadzovať do castingu náhodný počet súťažiacich a simulovať chovanie porotcov. Údaje o súťažiacich (meno a vek) načítavajte zo súboru, údaje o porotcoch (meno a koeficient náhodnosti) z iného súboru.

Triedy nech prináležia nejakému balíčku so zmysluplným názvom.

Cvičenie 6, 7 (5. 11 + 12. 11. 2007)

V rovine sa nachádzájú rôzne geometrické útvary - štvorce, trojuholníky a kruhy. Navrhnite a implementujte triedy a metódy, ktoré umožnia spočítať obsah všetkých útvarov nachádzajúcich sa v rovine.

Poznámky

Domáca úloha: Navrhnite a implementuje triedy riešiace danú úlohu. Načítavajte objekty geometrických útvarov zo súboru a pridávajte ich do roviny. Zvoľte si vhodnú reprezentáciu objektov v súbore, odporúčaná je nasledovná:

Cvičenie 7 + 8 (21. 11 + 26. 11. 2007)

Firma Prachy s.r.o. chce zarobiť na kurzových machináciách s použitím internetu. Ich cieľom je prejsť kurzové lístky viacerých bánk a zisťovať pre každú menu najvýhodnejší kurz pre predaj a nákup devíz.

Vytvorte informačný systém, ktorý obíde kurzové lístky bánk a zistí pre každú z mien najnižšiu cenu pre predaj a najvyššiu cenu pre nákup valút. Kurzové lístky sa môžu nachádzať buď na Internete alebo môžu byť načítané zo súboru.

Príkladom kurzového lístka je Národná banka, http://www.nbs.sk/KL/EXKL/AKT_EXKL.XML

Funkčné požiadavky:

Vytvorte triedy KurzovýLístok, Mena, Banka, Systém. V triede Systém vytvorte metódy načítaj(Banka banka, File file) a načítaj(Banka banka, URL adresa), ktorými načítate údaje o kurzovom lístku pre danú banku zo súboru, resp. z URL adresy. Metódy nech hádžu výnimku KurzovýLístokException.

Cvičenie 9 (10. 12. 2007)

Vytvorte pomocnú triedu, ktorá bude vedieť spracovávať kurzový lístok vo formáte Národnej banky (http://www.nbs.sk/KL/EXKL/AKT_EXKL.XML). Vytvorte metódy, ktoré načítajú z kurzového lístka

Užitočné metódy triedy String

	"janko komár".indexOf("ko")

Výsledkom je 3 (prvýkrát sa ko vyskytuje od štvrtého znaku, teda od tretieho indexu)

"hamburger".substring(4, 8)

vráti urge.

char znak = "hamburger".charAt(3);

vráti znak b.

int dlzka = "hamburger".length()

Výsledkom je 9.

boolean b = "myšlienka".startsWith("myš");

vráti true.

Cvičenie 10 (17. 12. 2007)

V rovine sa nachádzajú geometrické útvary – štvorce, obdĺžniky a kružnice.

Dopracujte interface, ktorý reprezentuje zafarbiteľný útvar. Zabezpečte, aby štvorce a kruhy boli zafarbiteľné nejakou farbou. Do roviny dopracujte metódu, ktorá zráta obsah zafarbiteľných útvarov.

Vytvorte triedu, ktorá načíta zo súboru dáta o útvaroch a vráti ich ako zoznam geometrických útvarov. Odchytávajte korektne vyhodené výnimky.

Domáca úloha

Zašlite hotový projekt s geometrickýcmi útvarmi z predošlých cvičení.

Konvencia o zasielaní domácich úloh

Domáce úlohy je potrebné zasielať na e-mail cvičiaceho skomprimované v archíve ZIP. Archív musí mať názov typu priezviskoPoradovéČísloTýždňa.zip a musí obsahovať zdrojové (.java) súbory. Skompilované (.class) súbory nie je potrebné prikladať.

Príklad: zadanie pre siedmy týždeň semestra zaslané študentom Mrkvičkom: mrkvicka7.zip.

V predmete (subject-e) mailu uveďte text DU PAZ1c.

Domáce úlohy nespĺňajúce mennú konvenciu nebudú akceptované.

Odkazy

Syntaktické rozdiely medzi Pascalom a Javou

Jednoduchý program Ahoj svet

program AhojSvet;
begin
  writeln('Ahoj svet');
end.

public class AhojSvet
  public static void main(String[] args) {
    System.out.println("Ahoj svet");
  }
}

for cyklus

program DU;
  var i:integer;
begin
  for i:=1 to 20 do begin
    writeln('Budem si pisat domace ulohy');
  end;
end.

public class AhojSvet
  public static void main(String[] args) {
    for(int i = 0; i < 20; i++) {
      System.out.println("Budem si pisat domace ulohy");
    }
  }
}

Podmienky

if (a = 25 or b < 25) and (a > b) then begin
  writeln('Podmienka splnena');
end 
else begin
  writeln('Podmienka nesplnena');
end;

if( (a == 25 || b < 25) && (a > b)) {
  System.out.println("Podmienka splnena");
} else {
  System.out.println("Podmienka nesplnena");
}

Cyklus while

a := 25;
while a >= 0 do begin
  writeln(a);
  a := a - 1;
end;

int a = 25;
while(a > 0) {
  System.out.println(a);
  a--;
}

Procedurálne programovanie

program rovnica;

function diskriminant(a,b,c:integer):integer;
begin
  diskriminant := (b * b) - (4 * a * c);
end;

procedure korene(a,b,c:integer);
  var d:integer;
begin
  d:=diskriminant(a,b,c);
  writeln( (-b + sqrt(d)) / (2 * a) );
  writeln( (-b - sqrt(d)) / (2 * a) );
end;

begin
  korene(2, 15, 5);
end.

public class Rovnica {
  public static int diskriminant(int a, int b, int c) {
    return (b * b) - (4 * a * c);
  }

  public static void korene(int a, int b, int c) {
    int d = diskriminant(a, b, c);
    System.out.println( (-b + Math.sqrt(d)) / (2 * a) );
    System.out.println( (-b - Math.sqrt(d)) / (2 * a) );
  }

  public static void main(String[] args) {
    korene(2, 15, 5);
  }
}

Písomka

Vágny príklad

Firma Vox Populi si chce nechať vytvoriť informačný systém pre prieskum verejnej mienky založený na hlasovaní. Každý prieskum verejnej mienky obsahuje otázku a množinu odpovedí; účastník hlasovania potom následne odpovedá na otázku zvolením jednej z možných odpovedí.

Príkladom prieskumu verejnej mienky môže byť otázka: Myslíte si, že SuperStar je zmanipulovaná? s možnými odpoveďami:

Samotné hlasovanie môže prebiehať viacerými formami (SMSkou, mailom, faxom, pohľadnicou atď.) a je neanonymné: pre každý hlas chceme mať identifikáciu odosielateľa.

Firma Vox Populi chce pre daný prieskum zisťovať rôzne štatistiky: koľko ľudí sa zúčastnilo, koľko hlasov prišlo pre danú možnosť a pod. Navrhnite pre tento informačný systém triedy, uveďte a slovne popíšte ich inštančné premenné a metódy. Zvážte a odôvodnite použitie dedičnosti (ak si myslíte, že dedičnosť je potrebná, slovne to zdôvodnite; ak si myslíte, že potrebná nie je, zdôvodnite to tiež).

Implementujte metódu (t. j. napíšte kód v programovacom jazyku), ktorá zistí počet účastníkov hlasujúcich cez SMS. Uveďte aj triedu a relevantné inštačné premenné (v prípade, že ich metóda používa). Inak povedané, napíšte fragment triedy a úplnú implementáciu uvedenej metódy.

Naimplementujte tester (t. j. napíšte kód v programovacom jazyku) s metódou main(), v ktorej ukážete príklady použitia vami navrhnutého informačného systému a tried (predpokladajte, že všetky metódy všetkých tried už máte implementované). V testeri ukážte použitie minimálne 5 metód používaných v triedach informačného systému.

Oprava kódu

Programátor Jozef ťahá v práci už dva týždne šestnásťhodinové nadčasy, čo sa neblaho prejavuje na kvalite kódu, ktorý produkuje. Nižšie je uvedená trieda Kniha, ktorú napísal v noci o pol tretej. Opravte po ňom všetky syntaktické a logické chyby, ktoré nájdete v jeho kóde.

Ak vidíte akékoľvek priestor na vylepšenie, uveďte ho.

Testové otázky

  1. Majme riadok
int[] x = new int[25];

Ktoré z tvrdení budú platiť po vykonaní tohto riadku?

A. x[24] je 0

B. x[24] je nedefinovaná

C. x[25] je 0

D. x[0] je null

E. x.length je rovné 25

  1. Majme triedu
public class Trieda {
  float rátaj(float a, float b) { }
  // sem príde metóda
}

Ktorá z nasledovných metód by môže byť uvedená v triede namiesto komentára a prečo? A. int rátaj(int a, int b)

B. float rátaj(float a, float b)

C. float rátaj(float c, float d)

D. float rátaj(int a, int b, int c)

  1. Majme nasledovné triedy (každá v samostatnom súbore):
public class Rodič {
  public void metóda(int i) {
    System.out.print("Rodič "
      + i);
  }
}
public class Dedič extends Rodič {
  public void metóda(int j) {
    System.out.print("Dedič " + j);
  }
  public void metóda(String s) {
    System.out.print("Mám " + s);
  }
  public static void main(
    String args[]) {
    Rodič b1 = new Rodič()
    Rodič b2 = new Dedič();
    b1.metóda(5);
    b2.metóda(6);
  }
}

Aký výsledok sa vypíše po spustení metódy main() v triede Dedič?

A. Rodič 5Rodič 6

B. Dedič 5Dedič 6

C. Dedič 5Rodič 6

D. Rodič 5Dedič 6

E. Mám 5Mám 6

  1. Majme nasledovnú triedu
public class Test extends Rodič {
  public Test(int j) {   }
  public Test(int j, int k) { 
    super(j, k);
  }
}

pričom Rodič je trieda z predošlého príkladu. Ktoré z uvedených konštrukcií je možné použiť na vytvorenie inštancie triedy Test?

A. Test t = new Test();

B. Test t = new Test(1);

C. Test t = new Test(1, 2);

D. Test t = new Test(1, 2, 3);

  1. Čo sa stane pri pokuse o kompiláciu nasledovných tried a po spustení triedy Zebra?

A. Trieda Zviera sa neskompiluje kvôli chybe.

B. Trieda Zebra sa neskompiluje kvôli chybe.

C. Všetko sa skompiluje správne. Po zavolaní konštruktora triedy Zviera sa vypíše chybové hlásenie.

D. Všetko sa skompiluje správne. Po zavolaní konštruktora triedy Zebra sa vypíše chybové hlásenie.

E. Všetko sa skompiluje správne a spustí sa správne.

class Zviera {
  float váha;
  Zviera(float váha) {
    this.váha = váha;
  }
}
class Zebra extends Zviera {
  public static
  void main(String[] args) {
    Zviera a = new Zviera(222.2f);
    Zebra z = new Zebra();
  }
}
>> Home