Zkouška 27.9.2016 (Dvořák+Hric)

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
gpp

Zkouška 27.9.2016 (Dvořák+Hric)

Příspěvek od gpp »

Poslední termín tohohle roku, i tak napíšu zadání pro další generace.

Prolog:
1) problém dvou loupežníků

2) seznamy s hvězdičkou.. jestli se za hvězdičku dá něco doplnit a seznamy se pak rovnají - na fóru je zadání několikrát
[*,5,7,7] a [1,2,*,7] vrátí true
[3,*,5,7,7] a [1,2,*,7] vrátí false


Haskell:
3)zadaný je seznam [(a,a,a)] - body ve třídimenzionálním prostoru a z nich se mají vybrat ty, pro které neexistuje žádný bod, který je ve všech třech souřadnicích neostře menší.
z něčeho takového: [(1,2,0), (0,2,2), (1,0,2), (0,2,4), (1,2,3)]
se mělo udělat toto: [(1,2,0), (0,2,2), (1,0,2)]

4)byl zadán strom jako:
data NT a = N a [NT a]

a) napsat datový konstruktor N
řešení je: N :: a -> [NT a] -> NT a

b) takový strom projít a k vrcholům dopsat pořadí navštívení postorder
ocisluj :: NT a -> NT (a,Int)




Velký příklad:
Multikomoditní tok - což je v orientovaném grafu s ohodnocenými hranami mnoho toků. Na vstupu je zadaný graf a komodity -> jednotlivé toky - mají Jméno, Zdroj, Stok, Objem ("objem" je velikost chtěného toku ze zdroje do stoku pro danou komoditu). Úlohou bylo uspokojit všechny komodity nebo grafem protlačit co největší objem komodit.
(prý jsme si to měli představit jako železniční síť a jednotlivé komodity jsou třeba vlaky... z jednoho města jich tolik chceme dostat jiného)
Jednou hranou grafu může protékat více komodit, ale jejich součet nesmí být větší kapacita hrany.

--------------------------------
řešení 1)
rozdel([], [], []).
rozdel([X|Xs], [X|S1], S2):-rozdel(Xs, S1, S2).
rozdel([X|Xs], S1, [X|S2]):-rozdel(Xs, S1, S2).

secti([], 0).
secti([X|S], N) :- secti(S, N1), N is N1+X.

loupeznici(S, R1, R2):-rozdel(S, R1, R2), secti(R1, N1), secti(R2, N2), N1=:=N2.
% R1 a R2 jsou výsledné seznamy loupežníků
% prý by bylo lepší napsat sčítání hned při rozdělování.


--------------------------------
částečné řešení 2) vrací jen true/false, pak se ještě musí spojit ta delší část ze seznamů před hvězdičkou s delší částí z obou seznamů za hvězdičkou

% ořezat seznamy zepředu a zezadu, když jsou prvky stejné (X)
stejne(S1, S2):-zepredu(S1, S2, V1, V2), zezadu(V1, V2, W1, W2).

zepredu([X|Xs], [X|Ys], V1, V2):-zepredu(Xs, Ys, V1, V2).
zepredu([*|Xs], [Y|Ys], [*|Xs], [Y|Ys]).
zepredu([X|Xs], [*|Ys], [X|Xs], [*|Ys]).

zezadu(S1, S2, Z1, Z2):-reverse(S1, V1), reverse(S2, V2), zepredu(V1, V2, W1, W2), reverse(W1, Z1), reverse(W2, Z2).

--------------------------------
částečné řešení 3)
vyradit:: Ord a => (a,a,a) -> [(a,a,a)] -> Bool
vyradit _ [] = False --nevyrazovat
vyradit (x,y,z) ((a,b,c):seznam) = x>a || y>b || z>c || vyradit (x,y,z) seznam --chtěl to po mě, aby to rovnou vracelo Bool z booleovských hodnot

->pak už se jen projedou všechny body ze seznamu a zanechají se ty, co jsou False ve funkci vyradit.


--------------------------------
řešení 4) Doteď nevím, jak to pořádně udělat. Docela mě řešení zajímá. Nebyli jsme to schopni vymyslet. Ani lidé, co sdíleli nějaké svoje příklady, tuto úlohu nevyřešili.

Jestli někdo ví 4), tak prosím přidejte odpověď :)
hihi

Re: Zkouška 27.9.2016 (Dvořák+Hric)

Příspěvek od hihi »

cau neco jsem vymyslel, je to dvojita rekurze a neni to moc prehledny (mozna to neni ani dobre), ale treba to nekomu pomuze

Kód: Vybrat vše

_go :: [b] -> [Strom a] -> ([b], [Strom (a,b)])
_go xs [] = (xs, [])
_go xs (s:ss) = 
    let 
        (r,  str ) = _zip xs s --poradi tady tech dvou radku urcuje jestli jde o prefix nebo postfix 
        (rr, strs) = _go  r ss
    in 
        (rr, (str:strs))
                

_zip :: [b] -> Strom a -> ([b], Strom (a,b))
_zip (x:xs) (Strom a ch) = (rems, Strom (a,x) $ newStrs)
    where 
        (rems, newStrs) = _go xs ch
_zip xs _ = (xs, Nil)


label :: Strom a -> Strom (a,Int)
label = snd . (_zip [1..])
Odpovědět

Zpět na „PRG005 Neprocedurální programování“