Písemka z Haskellu - 21.5.2010

[Jookyn]

1. (10 bodů)
Byl zadán datový typ pro Binární stromy, něco jako
data Strom a = List a | Vrchol (Strom a) (Strom a)
tzn, bez hodnoty ve vnitřních uzlech. Pak tam byla funkce zahada (pokud jsem to měl dobře, tak vracela seznam hodnot listů v pre-order průchodu, ale na přesný znění si už nevzpomenu), úkolem bylo určit:

a) typovou signaturu funkce zahada
b) co vrátí aplikace funkce na nakreslený strom
c) slovy popsat co funkce dělá
d) napsat výstup funkce, která tam byla nadefinovaná (vyskytovaly se tam nějaký nekonečný datový struktury, z toho se bralo prvních 5 prvků atd, docela jednoduchý)

2. (10 bodů)
Funkce pro převod čísla v číselné soustavě o daném základu na číslo v desítkové soustavě

Příklady:
prevod 2 [1,1,1,0]
14
prevod 64 [1,63]
127

a) napsat typovou signaturu
b) napsat funkci prevod pomocí rekurze
c) napsat funkci prevod pomocí použití jedné z funkcí - map, filter, foldl, foldr
d) napsat funkci prevod pomocí stručných seznamů, ale bez použití funkcí z c)

3. (15 bodů)
Úkolem bylo nadefinovat funkci
gen n str, která vracela množinu všech slov, která vznikla záměnou n písmen z řetězce str, množina navíc měla být seřazená podle abecedy (ale nevim, jestli podle klasický, nebo podle tý co vracela funkce abeceda).

K dispozici byla funkce abeceda, která vracela seznam možných písmen.

Příklad:
abeceda
["a","b","c"]

gen 1 "aac"
["aaa","aab","abc","acc","bac","cac"]

4. (15. bodů)
Dva zakořeněné stromy (obecné - ne binární, s hodnotou ve všech uzlech) a,b jsou ekvivalentní, pokud existuje ve stromu b permutace podstromů (a jejich postromů... - rekurzivně do hloubky), taková že je shodná se stromem a. Snažil jsem se to napsat nějak zjednodušeně, ale nevim, jestli se mi to povedlo . Z příkladu to bylo jednoduše vidět, ale strom sem moc čitelně nedostanu...

a) napsat datovou strukturu pro reprezentaci takových stromů
b) napsat funkci ekviv, která zjistí, zda dva zadané stromy jsou ekvivalentní

[Pitr2311]

4. (15. bodů)
Dva zakořeněné stromy (obecné - ne binární, s hodnotou ve všech uzlech) a,b jsou ekvivalentní, pokud existuje ve stromu b permutace podstromů (a jejich postromů... - rekurzivně do hloubky), taková že je shodná se stromem a. Snažil jsem se to napsat nějak zjednodušeně, ale nevim, jestli se mi to povedlo . Z příkladu to bylo jednoduše vidět, ale strom sem moc čitelně nedostanu...

a) napsat datovou strukturu pro reprezentaci takových stromů
b) napsat funkci ekviv, která zjistí, zda dva zadané stromy jsou ekvivalentní

ja sa pokusim spravit nejako ten stromcek

Kód: Vybrat vše

           1                                            1         
       /   |   \                                    /   |   \     
    2      3      4            ~~~               3      4      2  
         /   \                                 /   \       
        5     6                               6     5      

snad je to aspon priblizne jasne, ako ta ekvivalencia mala vyzerat

[mifeet]

K prvnímu příkladu - pokud se dobře pamatuji, zadání stromu a funkce zahada bylo toto:

Kód: Vybrat vše

data BStrom a = List a | Vetev (BStrom a) (BStrom a)
zahada x = zahada' x []
  where
	zahada' (List l) = (l:)
	zahada' (Vetev l p) = zahada' l . zahada' p

Zadaný strom odpovídal definici

Kód: Vybrat vše

strom = Vetev (Vetev (Vetev (List 3) (List 4)) (List 2)) (List 1)

Nekonečná DS byla zadaná jako

Kód: Vybrat vše

stromOd n = Vetev (List n) (stromOd (n+2))

a za úkol bylo určit, co vrátí take 5 (zahada (stromOd 1))

Moje řešení:

1. 1. Typ funkce zahada:

      Kód: Vybrat vše

      zahada :: BStrom a -> [a]

   2. zahada strom vrátí seznam [3,4,2,1]
   3. zahada vrací seznam listů v průchodu zleva doprava (tedy preorder)
   4. hodnota funkce je [1,3,5,7,9]

2. 1. Kód: Vybrat vše

      prevod :: Integral a => a -> [a] -> a

   2. Kód: Vybrat vše

      prevod _ [] = 0
      prevod b (x:xs) = x*b^(length xs) + prevod b xs

   3. Kód: Vybrat vše

      prevod b xs = foldl (\mezivysledek cislice -> mezivysledek*b + cislice) 0 xs

   4. Kód: Vybrat vše

      prevod b xs =
        let delka' = length xs - 1
        in sum [ x * (b^(delka'-n)) | n <- [0..delka'], let x = xs !! n]

3. to jsem nestihl

4. 1. Kód: Vybrat vše

      data Strom a = Vetev a [Strom a]

   2. Kód: Vybrat vše

      ekviv :: Eq a => Strom a -> Strom a -> Bool
      ekviv (Vetev a xs) (Vetev b ys)
        | a /= b = False
        | length xs /= length ys = False
        | otherwise = (not.null) [ps | ps <- permutace ys, ekviv' xs ps]
        where
      		ekviv' xs ys = all (\(x,y) -> ekviv x y) (zip xs ys)
      		
      		permutace [] = [[]]
      		permutace xs = [(y:ps) | (y,ys) <- (vyber xs), ps <- permutace ys]
      			where
      				vyber [x] = [(x,[])]
      				vyber (prvni:zbytek) = (prvni,zbytek) : map (\(x,xs)->(x,prvni:xs)) (vyber zbytek)
      				{- vyber xs vrátí seznam všech dvojic (x,xs'), kde x
      				   je jeden prvek xs a xs' jsou ostatní prvky -}

[Návštěvník]

Mate nekdo uz vysledky ?

[Jookyn]

Mate nekdo uz vysledky ?

Dneska odpoledne se mi objevily v grupíčku, bohužel v součtu 57 bodů :-/

[Návštěvník]

Ja tam mam nevyplneno :/

[Pitr2311]

Ja tam mam nevyplneno :/

tiez sa mi tam objavil riadok pre Haskell ale zostal prazdny, aj ked som na pisomke bol... znamena to, ze este nemaju opravene vsetky pisomky, alebo mam radsej zacat spamovat Hrica s Dvorakom?

[H8me]

Zdravim,
viem ze je uz trocha pozde, ale nemohol by niekto naznacit riesenie k trojke, snazim sa to spravit v ramci priprav na skusku ale jedine co viem spravit je ze si vygenerujem jednotlive n-tice ktore chcem zamenit. Na ich miesta vsak neviem nijak rozumne dosadit nove znaky.

Dik, za help

[Jookyn]

Zdravim,
viem ze je uz trocha pozde, ale nemohol by niekto naznacit riesenie k trojke, snazim sa to spravit v ramci priprav na skusku ale jedine co viem spravit je ze si vygenerujem jednotlive n-tice ktore chcem zamenit. Na ich miesta vsak neviem nijak rozumne dosadit nove znaky.

Nevim, jestli moje řešení je ideální (ale musel jsem za něj mít minimálně 10 bodů), ale dělal jsem to rekurzivně, tak že výsledná (zatim neseřazená množina) byla sjednocení:
- první písmeno jsem ponechal a doobměnil k němu n písmen ze zbytku
- první písmeno jsem zaměnil postupně za ostatní písmena v abecedě a dogeneroval k tomu slova obměněná o n-1 písmen

Takže ta hlavní část vypadala zhruba takhle:

gen (x:xs) n = [x:y | y <- gen xs n] ++ [z:y | y <- gen xs (n-1) , z <- abeceda, x /= z]

K tomu je ještě potřeba nadefinovat dno rekurze a potom odřezat slepé větve (kdy je potřeba obměnit víc písmen než je délka slova).

No a nakonec jsem to celý seřadil, napsal jsem si vlastní quicksort, kterej respektoval pořadí abecedy, tak jak jí vracela funkce abeceda (možná to ani nebylo nutné, ale pro jistotu jsem to dělal).

[H8me]

Diky, tak ako vzdy to bolo ovela jednoduchsie ako som si myslel :]
Cela verzia ak by to niekoho zaujimalo vyzera:

Kód: Vybrat vše

gen s 0 = [s]
gen [] _ = []
gen (x:xs) n = [x:y | y <- gen xs n] ++ [z:y | y <- gen xs (n-1) , z <- abeceda, x /= z]