Písemka z Haskellu - 21.5.2010
-
- Matfyz(ák|ačka) level III
- Příspěvky: 115
- Registrován: 13. 9. 2008 21:42
- Typ studia: Informatika Mgr.
- Login do SIS: 80320124
Písemka z Haskellu - 21.5.2010
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í
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í
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Písemka z Haskellu - 21.5.2010
ja sa pokusim spravit nejako ten stromcekJookyn píše: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í
Kód: Vybrat vše
1 1
/ | \ / | \
2 3 4 ~~~ 3 4 2
/ \ / \
5 6 6 5
Pitr2311
- mifeet
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 27. 1. 2010 14:37
- Typ studia: Informatika Ph.D.
Re: Písemka z Haskellu - 21.5.2010
K prvnímu příkladu - pokud se dobře pamatuji, zadání stromu a funkce zahada bylo toto:
Zadaný strom odpovídal definici
Nekonečná DS byla zadaná jako
a za úkol bylo určit, co vrátí take 5 (zahada (stromOd 1))
Moje řešení:
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
Kód: Vybrat vše
strom = Vetev (Vetev (Vetev (List 3) (List 4)) (List 2)) (List 1)
Kód: Vybrat vše
stromOd n = Vetev (List n) (stromOd (n+2))
Moje řešení:
- Typ funkce zahada:
Kód: Vybrat vše
zahada :: BStrom a -> [a]
- zahada strom vrátí seznam [3,4,2,1]
- zahada vrací seznam listů v průchodu zleva doprava (tedy preorder)
- hodnota funkce je [1,3,5,7,9]
- Typ funkce zahada:
Kód: Vybrat vše
prevod :: Integral a => a -> [a] -> a
Kód: Vybrat vše
prevod _ [] = 0 prevod b (x:xs) = x*b^(length xs) + prevod b xs
Kód: Vybrat vše
prevod b xs = foldl (\mezivysledek cislice -> mezivysledek*b + cislice) 0 xs
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]
- to jsem nestihl
Kód: Vybrat vše
data Strom a = Vetev a [Strom a]
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 -}
-
- Matfyz(ák|ačka) level III
- Příspěvky: 115
- Registrován: 13. 9. 2008 21:42
- Typ studia: Informatika Mgr.
- Login do SIS: 80320124
Re: Písemka z Haskellu - 21.5.2010
Dneska odpoledne se mi objevily v grupíčku, bohužel v součtu 57 bodů :-/Návštěvník píše:Mate nekdo uz vysledky ?
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Písemka z Haskellu - 21.5.2010
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?Návštěvník píše:Ja tam mam nevyplneno :/
Pitr2311
Re: Písemka z Haskellu - 21.5.2010
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
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
-
- Matfyz(ák|ačka) level III
- Příspěvky: 115
- Registrován: 13. 9. 2008 21:42
- Typ studia: Informatika Mgr.
- Login do SIS: 80320124
Re: Písemka z Haskellu - 21.5.2010
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í:H8me píše: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.
- 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).
Re: Písemka z Haskellu - 21.5.2010
Diky, tak ako vzdy to bolo ovela jednoduchsie ako som si myslel :]
Cela verzia ak by to niekoho zaujimalo vyzera:
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]