Prolog 1 - Problém truhláře
Truhlář má dostatek trámů délky D a seznam Xs délek trámů, které potřebuje nařezat. V seznamu Xs se délky mohou opakovat.
Cílem problému je sestavit predikát rezy(+D,+Xs, -N, -Vss), který
- rozdělí požadované délky do skupin, které se mají nařezat z jednoho trámu
- truhlář přitom používá hladový algoritmus, tj. pro každou délku použije první trám, z něhož lze ještě požadovanou délku odřezat
- vrátí celkový počet řezaných trámů N
- a seznam seznamů Vss (délky N), jehož každý prvek reprezentuje dělení jednoho trámu (případný zbytek se neuvádí).
Kód: Vybrat vše
rezy(5,[3,2,2,2,2,1,4], N, V).
N=4, V=[[3,2],[2,2,1],[2],[4]]
- Definujte predikát rezy/4. Definice případných pomocných predikátů prosím opatřete vysvětlujícím komentářem.
- Je některý z vašich predikátů koncově rekurzivní? Pokud ano, vysvětlete, který to je a jaký to má význam. Pokud ne, dal by se některý takto upravit? Odpověď prosím zdůvodněte.[/*]
Je zadán seznam množin Mss. Chceme všemi možnými způsoby vybrat a vrátit v seznamu reprezentanty daných množin v odpovídajícím pořadí s podmínkou, že konkrétní reprezentanti v jednom výběru jsou různí.
Příklad:
Kód: Vybrat vše
reprezentanti([[1],[1,2,3],[1,3,4]], R).
R = [[1,2,3],[1,2,4],[1,3,4]]
- Sestavte predikát reprezentanti(+Mss, -Rss).
- Stručně vysvětlete, proč je vaše definice korektní.
- Je ve vašem programu použit řez (!) ? Jde o řez červený (mění deklarativní význam programu) či zelený (nemění d.v.)? Pokud ne, je řez nezbytný pro definici některého vestavěného predikátu / operátoru, který jste ve vašem řešení použili? Jde o řez červený (mění deklarativní význam programu) či zelený (nemění d.v.)?
Cílem je definovat binární funkci klouzave, která
- obdrží na vstupu posloupnost čísel a přirozené číslo n
- a vrátí posloupnost klouzavých průměrů řádu n, tj. aritmetických průměrů n sousedních prvků.
Kód: Vybrat vše
klouzave [1.5, 2.5, 3.5, 4.5, 5.5] 3
[2.5,3.5,4.5]
- Definujte typovou signaturu funkce klouzave
- Definujte vlastní funkci s explicitním využitím rekurze
- Sestavte alternativní definici, tentokráte bez explicitního použití rekurze, přitom můžete využívat libovolné knihovní funkce z přiloženého seznamu.
- Vyhýbá se alespoň jedna z vašich definic opakovaným výpočtům? Pokud ne, dala by se takto upravit? Zdůvodněte.
- Bude některá z vašich definic fungovat i na nekonečných seznamech? Pokud ano, vysvětlete proč. Pokud ne, dala by se některá z vašich definic takto upravit? Zdůvodněte.
Kód: Vybrat vše
take 5 $ klouzave [1..] 10
[5.5,6.5,7.5,8.5,9.5]
Cílem toho problému je zobecnit funkce foldr / foldl na obecné kořenové stromy.
- Definujte datový typ pro reprezentaci obecných kořenových stromů s ohodnocenými vrcholy:
- snažte se o co nejobecnější definici
- nezapomeňte na reprezentaci prázdného stromu
- Funkce foldl a foldr zobecněte na funkci fold, která bude - namísto seznamu - procházet stromem ve vaší reprezentaci popsané v (a).
- Pomocí funkce fold definujte funkci arita, která vrátí aritu (tj. maximální počet dětí přes všechny vrcholy) zadaného kořenového stromu.
- Pomocí funkce fold definujte funkci pdc, která vrátí průměrnou délku cesty z kořene do listu (tj. součet délek všech cest z kořene do listu / počet listů).