Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Cvičenia 23

Z Programovanie
Prejsť na: navigácia, hľadanie

Cieľom tohto cvičenia je precvičiť si prehľadávanie grafu do šírky, hľadanie najdlhších ciest a topologické triedenie.

CV22-graf.png
Úloha A: Odsimulujte prácu prehľadávania do šírky na neorientovanom grafe vpravo ak začneme prehľadávať vo vrchole 0. Predpokladajte, že adjVertices vracia susedov v poradí podľa čísla vrcholu. Uveďte, v akom poradí boli vrcholy vložené do queue a vypíšte výsledné polia dist a prev.
PROG-C24-graf.png

Úloha B: Nájdite všetky topologické usporiadania orientovaného grafu na obrázku vpravo.

Úloha C: Napíšte program, ktorý dostane orientovaný graf a v prípade, že je v grafe cyklus, vypíše ho (ak je cyklov viac, vypíše hociktorý). Odporúčame začať z programu na topologické triedenie pomocou prehľadávania do hĺbky, pričom si pre každý vrchol do poľa uložte, z ktorého iného vrcholu ste ho objavili (podobne ako pole prev pri prehľadávaní do šírky). V momente, keď program nastavuje acyclic=false, by ste mali vedieť nájsť cyklus.

Úloha D: Program na hľadanie najdlhšej cesty z u do v v neohodnotenom grafe zmeňte na hľadanie najdlhšieho cyklu, ktorý začína a končí v danom vrchole v

  • Cyklus je postupnosť vrcholov v_{0},v_{1},...,v_{k} taká, že každé dva za sebou idúce vrcholy v_{i} a v_{{i+1}} sú spojené hranou, v_{0}=v_{k} a žiaden iný vrchol sa v postupnosti neopakuje.

Úloha E: Vráťme sa k príkladu s koňom, ale namiesto prehľadávania do hĺbky použite prehľadávanie do šírky

  • Máme danú šachovnicu n x m, na ktorej sú niektoré políčka obsadené figúrkami. Na políčku (i,j) stojí kôň, ktorý sa pohybuje obvyklým spôsobom, ale môže chodiť iba po prázdnych políčkach.
  • Pre každé prázdne políčko v šachovnici spočítajte, na aký najmenší počet ťahov na neho vie kôň doskákať. Ak naňho vôbec nevie doskákať, vypíšte -1.
  • Použite prehľadávanie do šírky na grafe, v ktorom sú vrcholy jednotlivé políčka a hrany spájajú dvojice voľných políčok, medzi ktorými môže kôň skočiť. Môžete vytvoriť graf v niektorej reprezentácii, alebo to riešiť priamo v matici dist n x m.
  • Šachový kôň môže z pozície (i,j) skočiť na jednu z pozícií (i+2,j+1), (i+2,j-1), (i-2,j+1), (i-2,j-1), (i+1,j+2), (i+1,j-2), (i-1,j+2), (i-1,j-2)
  • Prehľadávanie do šírky nájdete v programe pre prednášku 33, trieda ShortestPaths

Úloha F: Program na hľadanie všetkých ciest dĺžky k z u do v v neohodnotenom grafe zmeňte tak, aby si predpočítal najkratšiu cestu z každého vrcholu do cieľového vrcholu (prehľadávaním do šírky z v) a potom nepokračoval ďalej v prehľadávaní z daného vrchola x, ak už nám v ceste zostáva len nejakých q hrán a najkratšia cesta z x do cieľového vrchola v má dĺžku viac ako q.