IB002 - 3. sada domácich úloh
Úloha je určená pre študentov sem. skupín IB002/05, IB002/06. Každý, kto má túto skupinu
riadne zapísanú, je povinný odovzdať vypracované obidva príklady. Študenti, ktorí nepatria do
týchto skupín môžu úlohu odovzdať a majú nárok na opravenie, nie však na bonusové body.
Termín odovzdania: 21.5. do 5:21
Zpôsob odovzdania: elektronicky do odovzdávarne v ISe (pdf dokument formátu A4) alebo
papierovo na cvičeniach F. Štefaňáka. Nezabudnite i v elektronickej verzii uviesť meno a UČO.
Vypracovanie ako dvojica: Úlohy je možné vypracovať ako dvojica. Dvojica odovzdáva len
jedno riešenie podpísané oboma menami. Body dostanú obaja z dvojice. Každý príklad je
hodnotený samostatne, je teda možné vytvoriť rozdielne páry pre prvý a druhý príklad.
Hodnotenie: Za výborne vypracované riešenia môžete získať až jeden bod za príklad. Za
neodovzdaný príklad, za riešenie, ktoré je extrémne nedostatočné (prázdny papier) a za opisovanie
naopak 2 body za príklad strácate.
Príklad 1
Jožko dostal hlad a poprosil Aničku, aby mu išla spraviť sendvič. Anička sa spočiatku
zdráhala, pretože je emancipovaná žena, ale potom jej Jožko sľúbil, že za každý krok do kuchyne
jej zaplatí korunu. Napíšte algoritmus pre Jožka, ktorý nájde najkratšiu cestu do kuchyne, aby
musel Aničke platiť čo najmenej.
Plán ich obrovského víkendového domu máme vo forme grafu (V, E), kde vrcholy reprezentujú
miestnosti a hrany priamy prechod medzi nimi. Hodnotiaca funkcia k : E → N určuje počet
krokov, ktoré zaberie prechod medzi miestnosťami. Anička s Jožkom sú v obývačke j ∈ V ,
kuchyňa je označená k ∈ V .
Príklad 2
Mário prehľadáva zámok, v ktorom je niekde uväznená princezná. Nevedel ju nikde nájsť, ale
nakoniec natrafil aspoň na mapu. Je to štvorcová sieť, kde sú steny označené X a všetky ostatné
polia ako o. Keď sa na plán pozrel, hneď mu bolo jasné, prečo ešte princeznu nenašiel. V zámku
sa nachádzajú aj miestnosti, do ktorých sa normálne nedostane, pretože nemajú žiadny vchod.
Princezná musí teda byť v jednej z nich. Napíšte Máriovi algoritmus, ktorý zistí presný počet
takýchto tajných miestností.
Plán má rozmery n×n. Môžete tiež predpokladať, že všetky okrajové polia na pláne sú označené
o. Nezabudnite určiť časovú zložitosť algoritmu.