Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · 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).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Cvičenia 22

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

Šachovnica

Máme danú šachovnicu n x m, na ktorej sú niektoré políčka obsadené figúrkami. Na políčku (i,j) stojí kôň. Na ktoré políčka šachovnice vie preskákať, pričom môže použiť aj viacero ťahov, ale môže chodiť iba po prázdnych políčkach?

  • Použite prehľadávanie do hĺbky 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 visited rozmerov 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)

Šachovnica 2

Pokračujme s príkladom s koňom, ale namiesto prehľadávania do hĺbky použite prehľadávanie do šírky:

  • 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. Umožnite tiež vypísať postupnosť polí, na ktoré kôň pri presune skočí.
  • 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.
  • Prehľadávanie do šírky nájdete v programe pre prednášku 33, trieda ShortestPaths.

Najdlhší cýklus

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.