Čtvrtá série devatenáctého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Zadání úloh

Žádné triky. Žádní falešní sobi.

Zadání čtvrté série devatenáctého ročníku KSP

Milí čtenáři, vzpomínáte si ještě na mne? Jsem detektiv Přesprst a rozhodl jsem se zvěčnit svůj životní příběh. Bohužel se nenašlo nakladatelství, které by o něj mělo zájem, a tak jsem přijal nabídku organizátorů KSP, kteří se rozhodli můj příběh vydat a ukázat na něm, že i běžná detektivní práce vyžaduje nemalé informatické znalosti. Takže, kde jsem to jen skončil…
Seděl jsem v Zamřížově kanceláři a poslouchal jeho výklad o vztazích mafiánů. Nad mým životem se stahovala mračna. Možná by to bylo ještě smutnější, kdyby nad ním slunce už dávno nezapadlo. Zamříž dokončil svou řeč. Chvíli jsme na sebe mlčky hleděli a nastalé ticho rušilo jen tikání nástěnných hodin.
„Takže tu budeme jen tak sedět a čekat, až si pro nás přijdou?“ ozvala se jízlivě Isabela.
Zamříž se zamyslel. Znal jsem tenhle výraz v jeho tváři. Tohle rozhodně nebude procházka růžovým sadem.
„Tohle rozhodně nebude procházka růžovým sadem,“ promluvil nakonec. „Pokud by se nám podařilo prokázat styky se zahraničím, mohli bychom do celé věci zatáhnout Interpol a požádat o posily, ale jinak nevím.“
„Není nic snazšího,“ prohlásila Isabela. „V těch materiálech z jeho trezoru by měl být i soupis zahraničních plateb.“

19-4-1 Finanční toky (8 bodů)

Máme k dispozici kompletní přehled všech plateb mezi jistými podezřelými organizacemi. Tento přehled tvoří orientovaný graf (viz kuchařka 19-3), ve kterém jsou jednotlivé organizace vrcholy a z i do j vede hrana, právě když organizace i převedla peníze na účet organizace j.

Tento graf máme již uložený jako matici sousednosti. Matice sousednosti M má velikost N×N (kde N je počet vrcholů grafu) a na pozici Mij je 1, pokud z i do j vede hrana, a 0 v opačném případě. (Na Mii je vždy nula.)

Navrhněte algoritmus, který v takto zadaném grafu nalezne stok. Stok je vrchol, do kterého vedou hrany ze všech ostatních vrcholů a z něho samotného už žádná hrana nevede.

Uvědomte si, že Přesprstovi a Isabele jde o život, a tak by váš algoritmus měl pracovat opravdu rychle. Navíc můžete předpokládat, že matici sousednosti již máte v paměti, a tak nemusíte připočítávat čas potřebný k jejímu načtení.

Příklad: Graf zadaný maticí

0101
0000
1100
1110

má právě jeden stok – vrchol 2.

„Ano to je ono!“ zajásal Zamříž. „Podívejte, vy dva. Už teď u mě máte metál, ale aby to klaplo, musím vyřídit pár telefonů. Co kdybyste si zatím dali kafe nebo tak něco, a já se o to postarám.“ A se sluchátkem u ucha nám jemně naznačil, abychom prozatím vypadli z jeho kanceláře.
Víčka jsem měl pěkně těžká a kafe bodlo. Chutnalo příšerně, i když v tuhle chvíli mi to bylo úplně jedno. Isabela stála u okna a pozorovala dění na ulici. Z venku se ozval pištivý zvuk pneumatik rychle projíždějícího auta. Přiskočil jsem k ní a trhnutím ji odtáhl od okna.
„Co blázníš,“ stačila ze sebe vypravit, než její slova přehlušila střelba a zvuk tříštícího se skla. Chvíli jsme mlčky hleděli na roztříštěné sklo a rozdýchávali tenhle incident.
„Asi bych ti měla poděkovat,“ prolomila ticho Isabela.
„Řekl bych, že tím jsme vyrovnáni,“ usmál jsem se.
Ze své kanceláře vykoukl Zamříž: „Obvolal jsem několik lidí a dal věci do pohybu. Bohužel náš byrokratický aparát funguje někdy velmi pomalu…“

Řešení

19-4-2 Byrokratický aparát (10 bodů)

Při schvalování určité záležitosti postupuje byrokratický aparát následujícím způsobem. Každý úředník má na počátku na svém stole nějaký dokument. Úředník si dokument přečte, orazítkuje a pošle ho dalšímu úředníkovi. Práce všech úředníků končí v okamžiku, kdy mají všichni úředníci na stole dokument, který schvalovali jako první (tzn. celý aparát se vrátí do výchozího stavu).

Aby to nebylo tak jednoduché, jsou zavedena speciální pravidla, komu má úředník předat dál orazítkovaný dokument. Každý úředník i má určeného právě jednoho úředníka f(i), kterému své orazítkované dokumenty předává. Aby se dokumenty nehromadily u některých úředníků, zatímco jiní budou bez práce, dostává každý úředník dokumenty od právě jednoho úředníka. Tedy každý úředník jeden dokument pošle dál a jeden od někoho dostane, a tak má stále stejně práce. A protože úřad je úřad, někteří úředníci klidně mohou orazítkovat tentýž dokument vícekrát.

Navrhněte algoritmus, který pro dané přiřazení úředníků f zjistí, kolik minimálně schvalovacích kroků (více než nula) bude potřeba, aby schvalovací proces skončil, tj. aby každý úředník měl na stole dokument, který schvaloval jako první.

Úředníci jsou očíslování od 1 do N a pravidla předávání dokumentů jsou zadána jako seznam (1 →3, 2→1, … ). Nezapomeňte, že mohou existovat izolovaní úředníci, kteří dokumenty posílají sami sobě (tzn. pravidla i→i).

Příklad: Pro 5 úředníků a pravidla (1→5, 2→4, 3→1, 4→2, 5→3) trvá schvalovací proces 6 kroků.

„Úředního šimla ke cvalu nepřinutíš,“ pokýval jsem smutně hlavou.
Počkali jsme, než se setmělo a pak jsme se společně se Zamřížem a jeho kolegou vydali opatrně dolů na parkoviště. Vypadalo to, že nás nikdo nesleduje. Nasedli jsme do auta a vydali se na cestu. Isabela se schoulila na zadní sedačce a začala podřimovat. Byl to dlouhý den. Víčka mi těžkla a chtělo se mi spát. Projeli jsme kolem známého motorestu, kde nás dnes dopoledne Zamříž vyzvedl. Ale tahle silnice přece vede …
„Kam to jedeme?“ zeptal jsem se.
„Uvidíš,“ usmál se Zamříž. „Už tam skoro jsme.“
Teď to do sebe začínalo zapadat. Přednáška o „pevných vztazích“, střelba na Isabelu i směr naší cesty. Ten prašivý skunk Zamříž mě podrazil. Po tolika letech přátelství!
„Proč?! Pro prachy? Nebo je v tom snad něco jiného?!“
„Neber si to osobně,“ odpověděl Zamříž s klidnou tváří. „Není to jen pro prachy. Je to pro spoustu prachů …“
Dál jsem nečekal. Udeřil jsem ho vší silou a strhl volant. Do rvačky se vložil Zamřížův kolega a nejspíš bych i prohrál, kdyby automobil nesjel z cesty a nenarazil do stromu.
Probral jsem se. Hlava bolela jako střep a ruka také nevypadala dobře. Poplácal jsem Isabelu po tváři, aby se probrala. Zamříž i jeho kolega byli v bezvědomí. Nebyl čas na hrdinství. Buď se probudí a pokusí se nás zabít, nebo přijede policie a přišije nám dvojnásobnou vraždu. Navíc nevím, komu věřit. Sebral jsem Zamřížovi služební zbraň a vytáhl Isabelu z auta.
„Musíme pryč, a honem! Nedaleko odsud je železnice. S trochou štěstí chytíme nákladní vlak.“
Běželi jsme, co nám síly stačily a modřiny dovolily. Ani nevím, jak dlouho nám to trvalo, ale nakonec jsme doběhli k trati. A dokonce jsme měli i štěstí. Ozvalo se houkání a za zatáčkou se objevil nákladní vlak…

Řešení

19-4-3 Naskakování na vlak (11 bodů)

Naskakování na vlak není věc jednoduchá. Přesprst a Isabela jsou navíc celí potlučení, a tak si musí zatraceně dobře rozmyslet, na který vagón naskočí a na který ne. Navíc musí počítat s tím, že se jim nemusí podařit na nějaký vagón naskočit, takže by rádi věděli, jestli se podobný vagón (resp. posloupnost vagónů) vyskytuje ve vlaku víckrát. A tady je příležitost pro vás, abyste se zkoumáním vlaku pomohli.

Vlak si představte jako řetězec délky N, kde každé písmeno představuje jeden vagón (např. U je uhelný vagón, P je poštovní vůz atp.). Dále máte dáno číslo k (k ≤ N) a máte zjistit, kolik navzájem různých podřetězců délky k se v řetězci (tedy ve vlaku) vyskytuje. Zároveň tyto podřetězce a počty jejich výskytů vypište.

Pozor, vlak už se blíží, takže byste to měli spočítat pekelně rychle. Nebojte se k tomu využít znalostí, které načerpáte z aktuální kuchařky, avšak pokud vymyslíte ještě efektivnější a podlejší postup, bodová odměna vás nemine.

Příklad: Pro řetězec (vlak) UPDUPDUDUP a k = 3 jsou nalezené podřetězce

UPD2×
PDU2×
DUP2×
DUD1×
UDU1×

Podařilo se nám naskočit na poloprázdný vagón se dřevem. Nebyl příliš pohodlný, ale hned sousední vagón převážel poštovní zásilky. Uvelebili jsme se mezi balíky a pytlem s dopisy a drncání vlaku nás pomalu ukolébalo.
„Hej! Ty … vstávat!“
Probudil jsem se a zamžoural do světla před sebou. Očividně bylo ráno a vlak už nedrncal. Přede mnou stála postava oblečená v pošťácké uniformě a mířila na nás revolverem.
„Tak pohyb, vy dva!“ zarámusil pošťák a naznačil revolverem, abychom se zvedli. Odvedl nás do malého skladiště poštovních zásilek, které se krčilo hned vedle kolejí.
„Tady počkáte, než vyložím zásilky. Pak uvidíme, co s vámi uděláme.“
Strčil nás dovnitř, zamkl dveře a odešel.
„To je prostě skvělé. Co teď budeme dělat, hm?“ pronesla skoro vyčítavě Isabela a posadila se na poštovní balík.
„Já osobně bych si dal snídani.“
„Cože? Ty bys sis dal …“ rozkřikla se, ale pak se zarazila. Podívala se na mě a rozesmála se na celé kolo. Je zajímavé, jak některé věci přijdou člověku veselé, když je až po uši v průšvihu.
Vykoukl jsem z okénka. Pošťák právě skládal veliký balík na váhu. Chvíli jsem pozoroval, jak si hraje se závažími, když v tom mě napadla spásná myšlenka.
„Hej, pane pošťáku, nechcete s tím pomoct?“

Řešení

19-4-4 Váhy (10 bodů)

Pošťák zápasí s váhami, protože nemají vhodnou sadu závaží. Navrhněte optimální sadu závaží, která bude postačovat na zvážení libovolného předmětu o celočíselné hmotnosti 1 až m kilogramů s přesností na jeden kilogram. Předmět považujeme za odvážený, když se misky vah ustálí v rovnovážné poloze, a pozor – závaží můžete pokládat na obě misky vah.

Aby vám pošťák věřil (a ocenil vás šesti body), musíte také dokázat, že vámi navržená sada závaží je funkční (tedy že s ní umíte zvážit libovolný přípustný předmět). Pokud uvedete i důkaz, že daná sada je optimální (tzn. neexistuje menší sada, která by také byla funkční), přidá vám pošťák 4 body navrch.

Pokud existuje optimálních sad více, stačí najít jednu libovolnou.

Poznámka: Při vážení 1 kg předmětu potřebujeme skutečně jedno kilogramové závaží. Nestačí vzít např. 2 kg závaží a předměty, které jsou lehčí, prostě prohlásit za jednokilové.

Příklad: Pro zadané m = 3 je jedna z možných optimálních sad závaží {1, 2}. Věci o hmotnosti 1 a 2 kilogramy zvážíme přímo, 3 kg odvážíme tak, že dáme obě závaží na opačnou misku než vážený předmět.

Tato sada je optimální, protože menší sada by měla pouze jedno závaží a snadno nahlédneme, že s jedním závažím umíme určit hmotnost pouze u předmětů, které váží stejně, jako závaží samo.

„To je dobré,“ poplácal mě pošťák po zádech. „Nechtěl bys pracovat u nás?“
„No, víš…,“ začal jsem nesměle s podíval se na Isabelu, která seděla na poštovním balíku.
„Nic mi neříkej. Úplně tě chápu,“ mrknul na mě šibalsky. „A teď odsud zmizte, než přijde šéf.“
Vydali jsme se z nádraží do města. K čertu, vždyť jsem ani nevěděl, co je to za město. Ale zůstat tady nemůžeme. Musíme zmizet za hranice. Zběžně jsem si prošacoval kapsy. Jen pár drobáků, navlhlý doutník a zbraň, kterou jsem sebral Zamřížovi.
„Musíme sehnat nějaké peníze a vypadnout ze země,“ nahodil jsem, aby řeč nestála.
„A co chceš dělat?“ podívala se na mě Isabela. „Vykrást banku?“
Rozhlédl jsem se po ulici, ale nikde žádná banka v dohledu. Zato na protější straně ulice jsem zahlédl bar. Nápis nade dveřmi „U Tří Es“ hlásal, že se jedná o nefalšované hráčské doupě.
„A co takhle zkusit štěstí…“

Řešení

19-4-5 Hazardní hra (10 bodů)

Hazardní hráči jsou samozřejmě všemi mastmi mazaní. Nechali Přesprsta vyhrát několik her Pokeru a teď ho chtějí oškubat na jiné, nepříliš známé hře.

Flek

Pravidla jsou následující. Bankéř vyhlásí číslo m, což je shodou okolností částka, o kterou se hraje. Hráči se poté snaží vymyslet, jak co nejrychleji tuto částku vysázet na stůl. Přitom ovšem smí používat pouze předem definované tahy:

Kdo vysází danou částku nejrychleji, vyhrává všechny peníze, které jsou momentálně na stole. Přesprst opravdu potřebuje vyhrát, a tak se neobejde bez vaší pomoci.

Příklad: Pro číslo m = 192 jsou nejrychlejší tahy: +1, +1, *10, -1, *10, +1, +1.

Klidným krokem jsem vyšel ven a přepočítával vyhrané peníze. Isabela na ně užasle zírala. „Jak jsi to dokázal?“
„Stačí mít trochu štěstí a umět počítat,“ usmál jsem se.
Schoval jsem peníze do kapsy a vykročil směrem k nádraží. Ušli jsme sotva pár kroků, když v tom hned vedle nás zastavilo u chodníku policejní auto…

To be continued…

Řešení

19-4-6 Prolog (14 bodů)

Milí znalci a přátelé Prologu,

tentokrát vás čeká velmi zajímavá, ale také náročná kapitola. Dozvíte se něco o negaci v Prologu, ale také o myších, logice, filozofii a jiných nebezpečných věcech.

Jemný začátek – vstup a výstup

Při startu programu je aktuální vstup nastaven z klávesnice, aktuální výstup na obrazovku.

Základní jednotkou, kterou můžete načíst nebo vypsat, je term. Predikát read(T) načte celý aktuální term (číslo, znak, řetězec, struktura) a unifikuje ho do proměnné T. Predikát write(T) vypíše term T. Pokud je v termu T zunifikovaná proměnná, vypíše se místo ní její hodnota.

Pokud chcete číst a vypisovat znaky, použijte predikáty:

get0(Z)přečte znak
get(Z)přečte znak a ignoruje přitom řídící znaky
put(Z)vypíše znak (nevypisuje řídící znaky)
tab(N)vypíše N mezer
nlnový řádek

Příklad:

?-write('Zadej zvire: '), read(Zvire), write(Zvire).
Zadej zvire: kachna.
kachna
Zvire = kachna
Yes

Příklad: Tento predikát vypíše seznam, každá položka bude na novém řádku:

vypis([]).
vypis([H|T]) :- write(H), nl, vypis(T).

Pozor: Vstup a výstup je tak trochu neprologovský – jistě víte, že když Prolog splňuje nějaký predikát p, postupně splňuje jednotlivé predikáty v jeho těle. Pokud nějaký z nich neuspěje, Prolog „zapomene“ dosud provedené predikáty z těla p a hledá na dalších řádcích jiná těla splňovaného predikátu p. U vstupů a výstupů ale nejde „zapomenout“ už provedenou hodnotu. Pokud tedy nějaký predikát vypíše něco na obrazovku, zůstane to vypsané i tehdy, když ten predikát nakonec neuspěje.

Filozofické zastavení

Narozdíl od klasických programovacích jazyků, které přesně popisují algoritmus na řešení dané úlohy, Prolog se snaží vyřešit problém pomocí matematické logiky. Každá klauzule (řádek programu) odpovídá nějaké výrokové formuli. Příkladem výrokové formule je formule „a & b → c“. Prologovský program je tedy množinou klauzulí, každá klauzule má svůj význam, který vyjadřuje nějaká logická formule. Pokud vezmeme všechny logické formule, které odpovídají všem klauzulím programu, dostaneme význam programu. Když pochopíme, že prologovký program je vlastně souborem logických formulí, mezi kterými je „a zároveň“, všimneme si, že v Prologu nezáleží na pořadí jednotlivých klauzulí, ani na pořadí jednotlivých predikátů v jejich tělech.

Bylo by hezké, kdyby fungovala představa čistě logického jazyka, ve kterém nezáleží na pořadí vyhodnocování predikátů, ale bohužel to tak nejde. S takovým jazykem bychom toho mnoho nenaprogramovali, takže se musíme uskromnit.

Opouštíme ideály – predikát řezu

Jistě už jste přemýšleli nad tím, jak se v Prologu udělá negace a proč jsme si ji ještě neukázali. Abychom prologovskou negaci byli schopni vytvořit, vysvětlíme si nejprve predikát řezu.

Predikát řezu slouží k vyjádření negace a zrychlení prologovských programů. Značí se vykřičníkem „!“. Názornou představu o predikátu řezu si můžeme udělat už z jeho názvu – pokud použijeme řez v nějaké větvi výpočtu, řez zakáže použít další možné větve tohoto výpočtu, tedy zakáže další backtrackování. Nejlepší bude příklad:

a(X) :- b(X), !, c(X).
a(X) :- d(X).

Prolog zde zkouší splnit první řádek. Pokud se splní predikát b(X), dojdeme k predikátu řezu. Ten okamžitě uspěje, ale přitom zakáže nový vstup do predikátu, ve kterém se nachází, tedy nesmíme už znovou zkoušet splnit predikát a(X). Pokud tedy neuspěje následující predikát c(X), Prolog už díky řezu v prvním řádku nesmí zkoušet další možnost v druhém řádku. Odřezali jsme tedy druhou větev výpočtu. Kdyby v prvním řádku nebyl operátor řezu, Prolog by zkoušel splnit nejprve první řádek, a kdyby se mu to nepovedlo, skočil by hned na druhý tak, jak to známe.

Operátor řezu lze použít dvěma způsoby:

1. Operátor řezu jako tzv. zelený řez, ten nemění význam programu, pouze ho urychluje tím, že uřezává neperspektivní větve zbytečné pro výpočet, ale program by fungoval i bez něj.

2. Operátor řezu jako tzv. červený řez, kterým změníme průběh vyhodnocování programu.

Příklad zeleného řezu:

V tomto příkladu chceme slít dohromady dvě setříděné posloupnosti tak, aby výsledná posloupnost byla setříděná. Například z posloupností [1,3,5] a [2,4,6] dostaneme [1,2,3,4,5,6].

slij([X|A],[Y|B],[X|C]) :- X=<Y, !, slij(A,[Y|B],C).
slij([X|A],[Y|B],[X,Y|C]) :- X=Y, !, slij(A,B,C).
slij([X|A],[Y|B],[Y|C]) :- Y=<X,slij([X|A],B,C).
slij(A,[],A).
slij([],B,B).

Operátor řezu v prvních dvou řádcích se dá chápat jako rada – pokud je například X=<Y, nemá cenu zkoušet, jestli je X=Y nebo Y=<X, protože víme, že to vždy bude nepravda. Operátor řezu zde tedy interpreteru říká, že pokud uspělo X=<Y, ostatní větve už by neuspěly.

Příklad červeného řezu:

Červený řez se často používá v predikátech, které při prvním spuštění dají dobrý výsledek, ale při odmítnutí středníkem nebo při znovuzavolání jiným predikátem by mohly začít dávat nesmysly. Příkladem je třeba tento predikát, který má odstranit všechny výskyty prvku X v predikátu Sezn:

odstran(_,[],[]).
odstran(X,[X|Y],Z) :- odstran(X,Y,Z).
odstran(X,[Q|Y],[Q|Z]) :- odstran(X,Y,Z).

Prohlédněte si tuto konverzaci s interpreterem Prologu:

?-odstran(b,[a,b,c],Vysl).
Vysl = [a, c] ;
Vysl = [a, b, c] ;
No

To ale není správné chování. Na odmítnutí středníkem měl Prolog reagovat okamžitým No., protože [a,b,c] není přece původní seznam s vymazaným prvkem b. Problém je v tom, že po odmítnutí uživatelem zkouší Prolog jiné možnosti, jak splnit predikát odstran, a použije třetí variantu odstran i v případě, že X=Q. Tuto chybu odstraníme tím, že přidáme operátor řezu do druhého řádku, čímž zakážeme případné použití třetího řádku v případě, že X=Q:

odstran(_,[],[]).
odstran(X,[X|Y],Z) :- !, odstran(X,Y,Z).
odstran(X,[Q|Y],[Q|Z]) :- odstran(X,Y,Z).

Jiný příklad: Chceme vložit do seznamu prvek, pokud tam ještě není:

vloz(A,Sezn,Sezn) :- prvek(A, Sezn), !.
vloz(A,Sezn,[A|Sezn]).

Predikát fail

Predikát fail má jedinou funkci – okamžitě si vynutí selhání. Tedy napíšeme-li predikat :- fail, tento predikát nikdy neuspěje. Na první pohled se může zdát trošku divné, proč bychom mohli potřebovat takový predikát, ale ve skutečnosti je to jeden z nejužitečnějších predikátů v Prolog, protože ho potřebujeme pro negaci.

Negace

Jak už jsme prozradili, negaci v Prologu tvoříme pomocí řezu. Ukážeme si tedy definici vestavěného predikátu not(A), který uspěje, pokud neuspěje A.

not(A) :- A, !, fail.
not(A).

Predikát not(A) se nejprve pokusí splnit cíl A. Pokud se A splní, zakážeme zkoušet další větve výpočtu a přikážeme predikátu selhat. Pokud se cíl A nesplní, Prolog zastaví vyhodnocování tohoto řádku, tudíž se nedostaneme ani k operátoru řezu, takže nezakážeme další větev, která se automaticky splní.

Vidíte, že bez operátoru řezu a bez fail bychom toto chování neuměli přikázat.

Příklad: Opět chceme vložit do seznamu prvek, pokud tam ještě není:

vloz(A,Sezn,[A|Sezn]) :- not(prvek(A, Sezn)).
vloz(A,Sezn,Sezn) :- prvek(A,Sezn).

Kvíz

♠ Máme následující konstrukci:

p(X,Y) :- X > Y, !, fail.
p(X,Y) :- write(X), tab(1).
p(X,Y) :- X1 is X + 1, p(X1,Y).

Co se stane, zavoláme-li:

?-p(3,6),fail.

Odpověď: Jedná se o poněkud šílený zápis for cyklu. Vypíše se 3 4 5 6.

♠ Máme konstrukci:

p :- !, p.

Co udělá dotaz:

?-p.

Odpověď: Zacyklí se.

♠ Máme predikát:

nacti_jmeno(Jmeno) :- write('Zadej jmeno: '),
      read(Jmeno).

Co se stane po následující konverzaci:

?-nacti_jmeno(Jmeno).
Zadej jmeno: Kleofac

Odpověď: Interpret vypíše nějakou volnou proměnnou, protože Kleofac není řetězec, ale proměnná. Začíná totiž velkým písmenem.

Soutěžní úložky

Důležité upozornění: Všechna řešení musí vracet smysluplná řešení i při opětovném volání, např. odmítání středníkem.

1. Lednice (3 body) Myši opět chystají útok na vaši lednici. Myší útok je samozřejmě potřeba dobře naplánovat, a proto myši vyslaly zvěda, který má za úkol zjistit zásoby v lednici. Lednice je zadána jako seznam potravin, které se mohou opakovat. Myši by potřebovaly program, který dostane na vstupu ledničku jako seznam potravin a jednu konkrétní potravinu, a vypíše, kolikrát se daná potravina v lednici vyskytuje.

Příklad:

Pro lednici [syr, maslo, syr, cibule, syr, syr] a potravinu syr by měl program odpovědět 4.

2. Myší spartakiáda (3 body) Vážení a vážené, myši, myšáci a myšáčata! Vítejte na myší spartakiádě! Jako první číslo vystupují bílé a černé myši v čísle „Myší obrazec“! Jak vidíte, na cvičišti se nachází N soudků. Na každém soudku smí stát právě jedna myš, buď černá nebo bílá. Myši se nyní vystřídají tak, že na N soudcích vytvoří všechny možné barevné kombinace černé a bílé.

Dokážete napsat program, který vypíše na obrazovku všechny možné kombinace myší?

Příklad:

Pro 2 soudky jsou možné obrazce: bb, bč, čb, čč.

Pro 3 soudky jsou možné obrazce: bbb, bbč, bčb, bčč, čbb, čbč, ččb, ččč.

3. Myš v bludišti (5 bodů) Myši se rozhodly skoncovat s nejstrašnější noční myší můrou, kterou je dostat se do myšího bludiště. Poprosily vás o program, který by dokázal najít východ z bludiště. Myší bludiště vypadá tak, že máte pokoje očíslované celými čísly 1,2,3,4,...,N a mezi některými pokoji vede chodba a mezi některými nevede. Technické detaily nechaly myši na vás. Vymyslete vlastní rozumnou reprezentaci bludiště. Myši vám poskytnou plán bludiště ve vaší reprezentaci, startovní pokoj myši a cílový pokoj myši. Váš program by měl najít libovolnou (ne nutně nejkratší) cestu z bludiště nebo odpovědět, že cesta neexistuje.

Hint: Přečtěte si KSP kuchařku o grafech.

4. Oprava (3 body) Najděte chybu v tomto predikátu, popište, proč nefunguje, a opravte jej. Nejdůležitější je podrobný popis a příklad vstupu, na kterém predikát nefunguje.

minimum(X,Y,X) :- X =< Y, !.
minimum(X,Y,Y).

Řešení