Zkouska 29.6.2010

[DarkTemplar]

Ahoj,

prosim, mohl by jste sem nekdo dat zadani z dnesni zkousky z Neproceduralka 29.6 a kdyztak i nejake to reseni.
Diky.

[vlastagf]

Hodim sem alespon zadani.

Prolog 1.)
Je zadany graf a cesta grafem. Je treba definovat predikat, ktery postupne vrati vsechna Hamiltonovska prodlouzeni cesty grafem. (cili cesta pres vsechny vrcholy) Reprezentace dat neni pevne dana.

Prolog 2.)
Prevod formuli z DNF do CNF. Spojky and, or a not definovat jako operatory.

Haskell 1.)
Definovat funkci, ktera overi, ze zadana posloupnost je Grayuv kod. Coz je posloupnost binarnich cisel "stejne delky", kde sousedni cisla se lisi maximalne o jeden bit, vcetne prvniho a posledniho cisla a jejich pocet je 2^n.

Kód: Vybrat vše

[0,0], [0,1], [1,1], [1,0]

Haskell 2.)
Vymyslet strukturu binarniho stromu, ktery v listech uchovava jeden typ hodnot a ve vrcholech druhy typ hodnot. Substituovat za typ v listech a napsat funkci, ktera ocisluje listy ve stromu od 1 zprava.

Kód: Vybrat vše

BinStrom a b = List a | Vrchol (BinStrom a b) b (BinStrom a b)
a funkce bude vracet treba
List (a,Int)

[srlok]

Tady je moje reseni na ten haskell 2, neni uplne idealni ale funguje mi

Kód: Vybrat vše

data Btree a = Nil | Node a (Btree a) (Btree a)
         deriving (Show, Eq)

numleaves :: Btree a -> Int
numleaves Nil = 0
numleaves (Node _ Nil Nil) = 1
numleaves (Node _ l r) = (numleaves l) + (numleaves r)

markleaves :: Btree a -> Btree (a,Int)
markleaves Nil = Nil
markleaves (Node a l r) = markleavesr (Node a l r) 1

markleavesr :: Btree a -> Int -> Btree (a,Int)
markleavesr Nil _ = Nil
markleavesr (Node a Nil Nil) n = (Node (a,n) Nil Nil)
markleavesr (Node a l r) n = (Node (a,0) lm rm) where
                                 lm = markleavesr l cntr
                                       where cntr = n + numleaves r
                                 rm = markleavesr r n