Pátá série devatenáctého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 7. květen 2007. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

Kam s tou hromadou sněhu?

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

V tu chvíli nám došlo, že nemáme co ztratit, a bezhlavě jsme se rozběhli nejbližší uličkou pryč.
„Dáš si ten koblížek s jahodovou polevou nebo s čokoládou?“ zeptal se první policista vystupující z auta.
A myslíš „Když já nevim… Jé, hele koukej, to je sranda, jak někteří lidé pořád pospíchají,“ funěl při vylézání z auta jeho parťák. „A víš ty co? Koupíme oba nebo radši tři, kdyby se nějaký cestou k autu ztratil,“ zachroptěl blaženě si hladíce bachor.
Po mnoha uběhnutých metrech a úhybných manévrech jsme konečně dotěrné policisty setřásli. Ale nemohli jsme si ale být jisti, že v pronásledování nepokračují, a tak jsme se rozhodli použít MHD k co nejrychlejšímu úprku z tý pasti, kde jsme se právě ochomejtali, do přístavu. Jenže život není vždycky fér, takže ač jsme byli jistě nejbohatší ve městě, naše zásoba mincí do automatu na jízdenky byla poněkud skrovná. Schválně si zkuste za tisícidolarovku koupit jízdenku s omezenou přestupností na dvě pásma!


19-5-1 Útěk (10 bodů)


Vaším úkolem bude najít co nejrychlejší cestu z počáteční pozice do cílové takovou, že nebude dražší, než obnos v mincích, který máte k dispozici.

Vstupní data budou vypadat následovně: na prvním řádku budou čtyři čísla $ (čti dolárek), N, S a C, kde $ značí obnos, který nesmíte překročit, N počet autobusových linek ve městě a S a C jsou počáteční a cílová stanice.

Následuje N řádků, přičemž každý řádek popisuje právě jednu linku. Každá linka a je popsána číslem K, což je počet stanic, kterými linka projíždí, a K trojicemi ve tvaru číslo zástávky, čas odjezdu (který se shodou okolností rovná i času příjezdu) a celková cena cesty z první zastávky linky. Zastávky jsou vypsány v takovém pořadí, v jakém jimi autobus projíždí. Každá linka jede jednou denně a všechny časy odjezdu, které jí popisují, patří do jednoho dne (čili žádná linka nejede „přes půlnoc“). Cena cesty mezi dvěma zastávkami na stejné lince je rozdíl jejich položek celková cena cesty z první zastávky linky.

Přesprst a Isabela jsou na začátku ve stanici S brzo, velmi brzo ráno (pro potřeby algoritmu v 0:00 hodin). Jejich úkolem je dostat se co nejdříve do stanice C. Najděte tedy takovou cestu pomocí MHD, která stojí nejvýš $ dolárků a přitom se Přesprst a Isabela dostanou do C co nejdřív. Pokud se do půlnoci do stanice C dostat nejde nebo každá cesta do C stojí víc než $ dolárků, vypište odpovídající zprávu.

Příklad: Pro vstup

50 3 1 5
2 1 8:00 0 5 8:20 60
4 1 8:05 0 2 8:10 25 3 8:18 50 5 8:22 60
4 1 8:06 0 4 8:12 10 3 8:16 20 5 8:26 35
je nejlepší cesta následující: linkou 3 na stanici 3, přestoupit na linku 2 a jet až do stanice 5. Cena této cesty je 30 dolárků.

Proč zrovna přístav? To semeniště hříchu? V hlavě se nám (především Isabele) začal rodit plán, jak z téhle pakárny vyváznout se zdravou kůží. Bohužel jediná loď plující na tichomořské ostrovy byla vedena gramotným kapitánem, a tak se o nás doslabikoval v novinách, že prcháme před zákonem.
„Pěkný zákon, zavrčel jsem,“ ale nebylo mi to nic platné. Trval na tom, že chce přesně polovinu našeho těžce nabytého majetku.

Řešení


19-5-2 Nesnadné dělení (10 bodů)


Najít přesné rozdělení bankovek na polovinu ale není vůbec snadné, zvlášť když mezi nimi jsou i falešné, např. dvěstěčtyřicetikoruna nebo třitísícetřistatřicetřikoruna.

Na vstupu se vyskytuje počet bankovek N a pak N přirozených čísel menších než nějaké přirozené číslo M. Vaším úkolem je rozdělit všechny bankovky na dvě stejně hodnotné části, nebo vypsat, že to není možné. Pokud je takových dělení víc, postačí nám libovolné.

Příklad: Pro N=7 a bankovky (1,3,6,1,5,2,2) je vhodným rozdělením například (2, 3, 5) a (1, 1, 2, 6). Pro N=3 a bankovky (3333,240,240) takové rozdělení neexistuje.

Hamtyham Plavba na lodi SUBMARINE probíhala celkem klidně. Nebyli jsme zřejmě sami, kdo se s kapitánem musel rozdělit o polovinu poctivého výdělku, takže o nás bylo pečováno jako v bavlnce. Ale jinak jsme se na lodi celkem nudili, i když mořská nemoc nám plavbu zajímavě zpestřila.
Přesto šlo na palubě uniknout šedi všedního dne – šlo o hru Hamtyhamtyhamtyaťmámvícnežtamty. Její pravidla jsou následující.

Řešení


19-5-3 Hamtyhamtyhamty (10 bodů)


Pokud náhodou neznáte pravidla, což je opovrženíhodné, přinášíme vám jejich popis. Máme posloupnost 2N čísel a dva hráče. V každém kroku si hráč vybere jedno číslo na libovolném konci posloupnosti a to odebere. Vyhraje ten, kdo má na konci větší součet. Pokud jsou oba součty stejné, jedná se o remízu.

Vaším úkolem je najít strategii pro prvního hráče takovou, aby vyhrál vždy, když je to možné. V opačném případě musí alespoň remizovat. Asi není třeba zdůrazňovat, že alespoň malý náznak důkazu správnosti vaší strategie je nezbytnou součástí řešení.

Příklad: Pro posloupnost (10,100,3,1) odebere první hráč jedničku, druhý cokoliv, načež první vezme 100 a tím zjevně vítězí.

Dodnes si nedokážu vysvětlit, proč Isabela pokaždé vyhrála. Ona to sice vysvětlovala tím, že od manžela leccos pochytila, ale stejně si myslím, že to bylo pouze začátečnické štěstí. Zajisté chápete, že mě ta hloupá hra brzy omrzela.
A tak když nás i hraní na letadlo na přídi přestalo bavit, zašel jsem z kapitána vymámit alespoň část našich peněz. Neúspěšně ovšem. Zato se mi dostalo pojednání o tom, jak lze absenci kvalitního vybavení nahradit jeho množstvím a, cituji, „důftipem.“

Řešení


19-5-4 Lodní mrazáky (10 bodů)


O co vlastně šlo? Typický lodní mrazák je vlastně takový zásobník. To znamená, že potraviny je možno přidávat pouze navrch a opět pouze z vrchu odebírat.

Pro kuchaře je to ale docela nepříjemné, protože chtějí vařit vždy z co nejstarších potravin (které jsou úplně naspodu mrazáku). Kuchařům by vyhovovala místo zásobníku fronta, kam by se potraviny přidávaly navrch a odebírat by šly jenom odspodu.

Máte k dispozici několik mrazáků, čili několik zásobníků, a chcete simulovat frontu, tj. musíte umět vyřizovat požadavky vlož potravinu (vloží „navrch“) a vydej potravinu, která byla vložena nejdříve (vydá „odspodu“). Smíte používat pouze několik mrazáků, čili vkládat a vyndavat z nich potraviny. Pokud nějakou potravinu vyndáte, musíte ji do nějakého mrazáku vrátit dřív, než vyndáte libovolnou jinou potravinu.

Kapitán po vás chce, aby tato simulace fronty byla co nejrychlejší. Požaduje, aby vyřízení N frontových požadavků zabralo nejvýš O(N) pomocných zásobníkových operací (vyndání a vložení potraviny z mrazáku do mrazáku).

Poznámka: Mrazáků můžete použít jenom konstantně mnoho, řekněme nejvýše 5. Snažte se jich ale použít co nejméně.

Hintík: Všimněte si vychytralé kapitánovy formulace. Nechce, aby jedna frontová operace použila konstantně mnoho pomocných zásobníkových operací. Nejspíš se může stát, že několik frontových operací použije velké množství pomocných zásobníkových operací. Nicméně ostatní frontové operace pak musí být rychlé. Celkově nesmí být na N frontových požadavků použito více než O(N) pomocných zásobníkových operací.

Po zbytek plavby se už nic význačného nestalo, jenom jsem po kapitánově přednášce značně omezil množství zkonzumované potravy, což se pozitivně projevilo na mé postavě.
Nakonec jsme přistáli u malebného ostrůvku GREENLAND. Naštěstí i po kapitánově zásahu nám zbylo dost peněz na vybudování šestnáctipokojové luxusní chatrné chýše v retro havaj stylu s výhledem na moře – kam taky jinam, že? A když teď tak po letech koukám na Isabelu a našich deset dětí, myslím, že ta její návštěva u mě v kanceláři byla to nejlepší, co mě mohlo potkat. A jí vlastně taky…

Řešení


19-5-5 Praktická úložka (10 bodů)


Milí účastníci a účastnice, po dlouhém přemýšlení a debatování jsme se rozhodli, že pro vás připravíme malé překvapení. KSP byl vždy čistě teoretickým seminářem, ve kterém šlo především o algoritmicky správné řešení a na implementaci nebyl kladen velký důraz. V tomto trendu chceme samozřejmě pokračovat, avšak s malou výjimkou. Jako pátou úložku této série jsme pro vás připravili praktický test, který prověří vaši programátorskou zručnost.

V praktické úložce nemusíte vaše řešení vůbec popisovat, nebo jakkoli komentovat, ale zato musíte odladit funkční program, který danou úlohu vyřeší. Odevzdávat budete pouze zdrojový kód, a to přes speciální webovou aplikaci CodEx (The Code Examiner) . Přihlašovací jméno a heslo do CodExu je totožné s přihlašovacím jménem a heslem do webového submitovátka, které již znáte řadu let. Pokud nemáte dosud zřízený účet na submitovátko, musíte se nejprve zaregistrovat.

Opravování probíhá tak, že CodEx převezme váš zdrojový kód, zkompiluje ho a následně jej pustí na sadu testovacích dat. Každý test má navíc nastaven časový a paměťový limit, který vaše řešení nesmí překročit. Za úspěšně vyhodnocené testy dostanete body a celkový součet bodů ze všech testů tvoří hodnocení vašeho řešení.

Vzhledem k tomu, že je velice obtížné napsat perfektní řešení na první pokus, budete mít pokusů více (detaily se dozvíte přímo v CodExu). Do výsledku se vám bude počítat nejlepší odevzdané řešení.

Aby byla úloha pokud možno co nejspravedlivější pro všechny, můžete odevzdávat pouze zdrojové kódy napsané v jazycích Pascal a C. Příznivcům ostatních jazyků se omlouváme, ale není v našich silách rozumně testovat i jiné jazyky (zvláště pak některé exotické, nebo interpretované).

Další podrobnosti a technické detaily můžete nalézt přímo v CodExu. Pokud byste měli jakékoli dotazy, technické potíže apod., obraťte se na známou adresu KSP, případně na diskusní fórum. Rovněž bychom velice rádi znali váš názor na zavedení praktické úložky do KSP, zda se vám (ne)líbí, návrhy na vylepšení atd. V případě, že se letos osvědčí, zařadili bychom ji v příštím ročníku „naostro“. Přejeme hodně zábavy při řešení…

Zadání:

Je dána posloupnost celých čísel P1, P2, …, PN. Čísla Pi a Pj jsou v inverzi, pokud i < j a zároveň Pi > Pj. Inverze je tedy porucha ve vzestupném uspořádání posloupnosti. Vašim úkolem je zjistit, kolik inverzí posloupnost obsahuje.

Vstup je uložen v textovém souboru cisla.in, kde na prvním řádku je číslo N a na druhém řádku následuje N celých čísel v desítkovém zápisu oddělených mezerami. Počet inverzí vypište na standardní výstup.

Čísla mohou být i záporná a vejdou se do 32-bitového integeru (int v Céčku, LongInt v Pascalu). Čísel v posloupnosti je maximálně 100 000 a počet inverzí se vejde do 32-bitového integeru. Vstupní soubor se vejde do operační paměti (i několikrát).

Příklad: Pro soubor cisla.in:

5
4 5 3 1 2
vypište na standardní výstup 8.

Řešení


19-5-6 Prolog (13 bodů)


Milí ProloGuru,

vítejte u pátého, posledního dílu seriálu o Prologu.

Zjednodušíme si život – seznamy výsledků

Protože už máte za sebou své programátorské začátky, dozvíte se za odměnu o třech užitečných predikátech, které za vás udělají spoustu práce: findall, bagof a setof. Jejich použití si vysvětlíme na příkladu.

Máme fakta o chovatelích a jejich zvířatech:

chova(petr,leguan).
chova(pavel,sklipkan).
chova(petr,krajta).
chova(petr,pirana).
chova(jan,sklipkan).

Predikát findall můžeme použít k tomu, abychom zjistili o zadaném člověkovi, jaká zvířata chová:

?-findall(Zvire,chova(petr,Zvire),Zvirata)
      Zvirata = [leguan, krajta, pirana]

Predikát findall(Term, Cíl, Seznam) totiž vytvoří seznam Seznam z takových termů Term, že splňují daný Cil. Tedy v našem případě jsme zadali jako Term proměnnou Zvire a jako cíl predikáty, ve kterých vystupuje petr jako chovatel a Zvire jako chované zvíře. Predikát findall našel tudíž všechny proměnné Zvire takové, které splňují cíl chova(petr,Zvire), tedy zvířata chovaná petrem a vytvořil z nich seznam Zvirata.

Predikát findall tedy vytvoří seznam všech dostupných řešení. Kdybychom se tedy zeptali následovně:

?-findall(Zvire,chova(Chovatel,Zvire),Zvirata).

dostaneme tento seznam všech dostupných řešení: [leguan, sklipkan, krajta, pirana, sklipkan], což nemusí být přesně to, co bychom si představovali. Můžeme proto použít predikát bagof, který dává výsledky postupně pro každého chovatele:

?-bagof(Zvire, chova(Chovatel,Zvire),Zvirata).
      Chovatel = petr
      Zvirata = [leguan, krajta, pirana] ;
      Chovatel = pavel
      Zvirata = [sklipkan] ;
      Chovatel = jan
      Zvirata = [sklipkan] ;
      No

Jinak pokud bychom zavolali bagof jako v přecházejícím případě, tj. bagof(Zvire,chova(petr,Zvire),Zvirata), dostali bychom stejný výsledek jako s findall.

Predikát setof se chová jako bagof, ale ve výsledném seznamu se každý term smí vyskytovat pouze jednou. K tomu, aby setof dokázal vyloučit opakující se hodnoty, výsledný seznam se třídí, tím se opakující se hodnoty dostanou k sobě a setof nechá jenom jeden výskyt. Na výstupu je pak seznam také setříděný.

Databáze v Prologu

Na prologovský program se můžeme podívat také z jiného úhlu – program v Prologu pro nás může být jakási „databáze“ faktů. Dosud jsme vám ale (z pedagogických důvodů) utajili, že do prologovské databáze lze přidávat nové klauzule za běhu, případně je zase odebírat. Můžeme si tedy ukládat i něco jako „globální proměnné“.

Novou klauzuli (resp. fakt) můžeme do databáze uložit predikátem assert(K). Přitom platí, že proměnná K už musí být unifikovaná s nějakou klauzulí – pozor, zdůrazňujeme unifikovaná s klauzulí, tedy například s zena(petronela). Pokud je proměnná K již unifikovaná, predikát assert(K) okamžitě uspěje a K se uloží na konec databáze.

Příklad:

Máme následující program v Prologu:

jidlo(spagety).
jidlo(vdolecky).

Je samozřejmé, ze kdybychom se zeptali

?-jidlo(zelenina).

odpoví nám Prolog No.

Představme si, že bychom se ale v průběhu programu nějak dozvěděli, že zelenina je opravdu jídlo, například by nám to někdo zadal z klávesnice. Bez databáze bychom byli v zapeklité situaci, protože jak víme, Prolog by okamžitě po opuštění daného predikátu na zeleninu zapomněl. My to můžeme vyřešit v průběhu programu jednoduše:

read(Novejidlo), assert(jidlo(Novejidlo)).

Od tohoto okamžiku máme v databázi Prologu další druh jídla, který nám zadal uživatel (ať je to třeba zelenina):

?-jidlo(zelenina).
      Yes

Zatím jsme si ukázali použití predikátu assert pro ukládání faktů. Na začátku jsme ale slíbili, že si pomocí něj můžeme uložit klauzuli, tedy i pravidlo. To skutečně jde, ale musíme při tom být opatrní. Pravidlo je při ukládání potřeba opatřit závorkami:

?-assert((pravidlo:-cil(X)))

Dále si povíme, jak odstranit klauzuli z databáze. Slouží k tomu predikát retract(K). Predikát retract(K) odstraní z databáze první klauzuli, která je celá unifikovatelná s K. Když voláme predikát retract(K), musí K obsahovat nějaký term, který má aspoň hlavu (název termu), aby Prolog věděl, co má smazat:

?-retract(jidlo(zelenina))

Od této chvíle už zelenina není jídlo.

Dalším užitečným predikátem pro práci s databází je predikát retractall(H). Tento predikát smaže z databáze úplně všechny klauzule, jejichž hlava se unifikuje s termem H, tedy například:

?-retractall(jidlo(_)).

smaže veškeré jídlo z databáze.

Nakonec jedno velmi důležité upozornění. Aby vaše hrátky s databází mohly fungovat, musíte na začátek programu Prologu říct, které predikáty budete za běhu ukládat a odebírat. To se udělá takto:

:- dynamic(jidlo/1).% Nezapomeňte na „:–“

Tímto říkáte Prologu, že jednoparametrový (proto /1) predikát jídlo bude dynamický.

Poznámka: Zápis predikát/počet_argumentů je obecný a používá se, pokud chceme označit, popsat, identifikovat nějaký predikát. Tento popis je totiž jednoznačný, žádné dva predikáty nemůžou mít zároveň stejné jméno a stejný počet argumentů.

Repeat-until v Prologu

V minulém dílu jsme se seznámili s predikátem řezu. Ukážeme si, jak s jeho pomocí naprogramovat cyklus repeat-until. V Prologu existuje nulární predikát repeat, který vždy okamžitě uspěje, a to i při návratu. Cyklus repeat-until tedy můžeme napsat pomocí predikátu repeat a predikátu řezu ! takto:

repeat, Cil1, Cil2, ..., PosledniCil, Podminka, ! .

Jistě vidíte, co se v tomto cyklu děje. Predikát repeat uspěje hned napoprvé, poté se splňují cíle, nakonec Podminka. Pokud podmínka neuspěje, predikát repeat zaručí nové zkoušení cyklu, pokud Podminka uspěje, následující predikát řezu zakáže další cyklení.

Rozdílové seznamy

Naším cílem bude vymyslet reprezentaci seznamů tak, abychom v ní mohli provést zřetězení seznamů rychleji než lineárně, tedy jinak, než že bychom brali prvky z prvního seznamu jeden po druhém a postupně je připojovali k druhému seznamu. Ukážeme si strukturu, která je příkladem neúplně definovaných datových struktur. Neúplně definovaná datová struktura je struktura, která obsahuje nějakou volnou proměnnou, která ještě nebyla s ničím unifikována.

Vezmeme si seznam [a,b,c]. Takový seznam má v původní reprezentaci prvky a, b, c. Mohli bychom ho také zapsat takto: [a,b,c|[]]. My teď uděláme jen a pouze to, že místo závěrečného prázdného seznamu [] dáme nějakou volnou, neunifikovanou proměnnou, třeba L. Abychom s ní ale mohli pracovat, aniž bychom celý seznam museli projít a zjistit, jakou volnou proměnnou seznam končí, „uložíme“ si ji ještě „bokem“ – formálně to zapíšeme jako [a,b,c|L]-L (zvídaví čtenáři nechť vědí, že jsme místo mínus mohli použít i jiné operátory; operátor zde nemá svůj normální význam, slouží jenom k uložení volné proměnné „vedle“ seznamu). Tento seznam je sice trošku divný, ale pořád ještě obsahuje prvky a, b, c. A k čemu je to dobré?

Vezměme si takové seznamy dva (například [a,b,c|X]-X a [d,e|Y]-Y) a budeme je chtít zřetězit. Čeho chceme dosáhnout? Chceme za X dosadit druhý seznam [d,e|Y] a získat tak seznam [a,b,c,d,e|Y]-Y. Stačí tedy napsat pravidlo:

zretez(A-B, B-C, A-C).

a při volání do něj dosadíme

zretez([a,b,c|X]-X, [d,e|Y]-Y, Vysl).

Pojďme detailně sledovat, co se kam dosadí. Pojedeme po řádku zleva doprava. Nejprve se unifikuje A za [a,b,c|X], pak se za B dosadí odečtené X, které je ještě pořád volné! Tedy B = X a pořád v nich ještě nic není. Ale teď přijde kouzlo. V dalším argumentu se B unifikuje s [d,e|Y], ale protože B = X, tak v A máme místo dříve volného X najednou [a,b,c,d,e|Y]. Poslední unifikace jenom dává výsledný seznam do pořádku, tedy říká: Vysl je A-Y, tedy Vysl je [a,b,c,d,e,f|Y]-Y.

Jelikož unifikace proměnná-term (čili dosazení do proměnné) je konstantní, získali jsme způsob, jak napojit dva seznamy za sebe v konstantním čase.

Převod z „normální“ reprezentace na rozdílový seznam je ale lineární, takže pokud chceme využívat tento rychlý způsob zřetězení, musíme si seznamy převést do rozdílové reprezentace na začátku, a pak s nimi počítat jako s rozdílovými po celou dobu.

Nakonec si ukážeme, jak na sebe obě reprezentace převést:

%preved(NormSezn, RozdSezn)
preved([],X-X) :- var(X).% var(X) uspěje, je-li X
% volná neunif. prom.
preved([H|Puvodni], [H|Nove]-Prom) :- var(Prom),
    prevod(Puvodni, Nove-Prom).

Co tento prográmek dělá: Postupným odtrháváním hlavy dojede až na konec seznamu, kde vytvoří nový prázdný rozdílový seznam X-X pomocí predikátu var(X). Predikát var(X) uspěje, pokud X je volná, neunifikovaná proměnná, my ho zde naopak používáme na vytvoření nové volné, neunifikované proměnné. Potom se vracíme z rekurze zpátky a odtrhané hlavy seznamu předřazujeme před nový rozdílový seznam.

Závěr a rozloučení

Tímto se s vámi loučíme a doufáme, že se vám programovací jazyk Prolog líbil.

Kvíz

♠ Máme tento program: zvire(sklipkan).

Co se stane, zavoláme-li: ?-assert(pirana).

  1. Syntaktická chyba.
  2. Dojde k běhové chybě.
  3. Zacyklí se.
  4. Přidá zvíře piraňa.
  5. Vloží se nulární predikát pirana.
  6. No.

♠ Co bude výsledkem dotazu:

?-repeat, assert(p(a)), fail.
  1. Syntaktická chyba.
  2. Dojde k běhové chybě.
  3. Vloží jedno p(a) do databáze a odpoví Yes.
  4. Vloží jedno p(a) do databáze a odpoví No.
  5. Nevloží nic a odpoví No.

Soutěžní úložky

1. Nejkratší program (2 body): Napište co nejkratší program v Prologu (co do znaků), který pro zadaný (nesetříděný) seznam přirozených čísel a zadané číslo K najde v seznamu nejmenší číslo X takové, že X > K, tedy číslo, které je shora nejblíž hodnotě K. Nehodnotí se rychlost, ale délka programu.

Příklad: Pro seznam [3,8,1,10,4] a číslo 5 má program vrátit 8.

2. Fronta (4 body): Navrhněte datovou reprezentaci fronty a napište predikáty, které umí zjistit, jestli je fronta prázdná, odebrat prvek ze začátku fronty a přidat prvek na konec fronty. Všechny operace musí být opravdu konstantní, takže žádné triky ve stylu mrazáků :–)

3. Expertní systém (7 bodů): Jako vrchol svého prologovského programátorského umění zkuste naprogramovat jednoduchý expertní systém. Budeme programovat hru "Mysli si zvíře". Uživatel hry si myslí zvíře a program se snaží vhodnými otázkami, na které uživatel odpovídá „ano“ a „ne“, uhádnout o jaké zvíře se jedná, případně konstatovat, že takové zvíře nezná.

Expertní systém se skládá ze dvou částí:

  1. Databáze, což je soubor obsahující všechna existující zvířata, všechny možné otázky typu ano/ne („Je to savec?“, „Žere maso?“) a pro každé zvíře též správné odpovědi na všechny otázky. Formát souboru si vymyslete sami. Soubor musí jít načíst do interpretru Prologu pomocí ?-['databaze.pl'].
  2. Program v Prologu, který klade uživateli otázky typu ano/ne a rozhodne, která zvířata (nemusí to být také žádné) odpovídají zadaným odpovědím. Program předpokládá, že databáze je již načtená v interpreteru Prologu, takže se celý expertní systém používá následujícím způsobem:
    ?-['databaze.pl'].
    ?-['program.pl'].
Who is that?

Cílem není napsat perfektní expertní systém (nezkoušíme vás z biologie), ale zúročit všechny vaše znalosti programování v Prologu.

Řešení