2. kodused ülesanded

Üldinfo

Lahenduste esitamise tähtaeg on 14.11. Lahendused saata mailiga kas varmo@cs.ut.ee või nestra@cs.ut.ee (sõltuvalt sellest, millises praktikumi rühmas olete); subjektiks peab olema fpkodu2. Ülesannete eest on võimalik saada kuni 10 punkti. Hilinenud lahenduste korral väheneb punktisumma 20% iga hilinenud nädala kohta. Näiteks, kui lahendus on väärt 10 punkti, aga jõuab meieni 17.11 (so. kolm päeva hiljem), siis on tegelik punktisumma 10 * 0.8 = 8.

Vormistamisest

Kõigi ülesannete lahendused vormistada ühe Haskelli failina. Faili nimi peab olema FPKodu2.hs ning seal defineeritava mooduli nimi FPKodu2. Faili algusse lisada kommentaaridena kõigi rühmaliikmete nimed (rühmas võib olla max. 4 liiget, kusjuures kõigil peab olema sama praktikumi juhendaja) ja maili-aadressid. Kõigi ülesannete korral peavad funktsioonide nimed ja argumentide arv/järjekord vastama täpselt ülesandes esitatule. Lahendused peavad olema loetavad ja piisavalt kommenteeritud (sh. kui kasutate abiprotseduure, siis see mida nad teevad peab olema selgelt välja toodud). Näiteks (FPKodu2.hs):

module FPKodu2 where

---------------------------------------------------------------------
-- FPKodu2.hs
-- Funktsionaalprogrammeerimise meetod - 2. koduülesannete lahendused
--
-- Autorid:
--          Jaan    Tatikas   (tatikas@ut.ee)
--          Salomon Vesipruul (salomon@ut.ee)
---------------------------------------------------------------------

-- 1. ülesanne - Funktsioon delAll kontrollib ...

delAll :: Eq a => a -> [a] -> (Bool,[a])
delAll x xs = ...

Ülesanded

  1. (1 punkt) Funktsioon delAll kontrollib, kas etteantud element esineb listis ning eemaldab kõik selle esinemised:

    > delAll :: Eq a => a -> [a] -> (Bool,[a])
    

    Üks võimalik, kuid ebaefektiivne (vaatab listi läbi kaks korda) selle funktsiooni definitsioon on esitatud järgnevalt:

    delAll x xs = (x `elem` xs, filter (/=x) xs) 
    

    Kasutades standardfunktsiooni foldr, kirjutada funktsiooni delAll efektiivsem definitsioon, mille korral läbitakse list ainult üks kord; so. definitsioon peab olema kujul:

    delAll x xs = foldr f b xs
        where f = ...
              b = ...
    

  2. (1 punkt) Funktsioon countSigns saab argumendiks täisarvude listi ning leiab seal esinevate negatiivsete arvude/nullide/positiivsete arvude koguarvud:

    > countSigns :: [Int] -> (Int,Int,Int)
    

    Üks võimalik, kuid ebaefektiivne (vaatab listi läbi kuus korda) selle funktsiooni definitsioon on esitatud järgnevalt:

    countSigns xs = ( length [x | x <- xs, x < 0]
                    , length [x | x <- xs, x == 0]
                    , length [x | x <- xs, x > 0])
    

    Kasutades standardfunktsiooni foldl, kirjutada funktsiooni countSigns efektiivsem definitsioon, mille korral läbitakse list ainult üks kord; so. definitsioon peab olema kujul:

    countSigns xs = foldl f a xs
        where f = ...
              a = ...
    

  3. (3 punkti) Aafrikas elav babababi hõim kasutab tähestikust ainult tähti A ja B. Sõnade moodustamisel kehtivad järgmised ranged reeglid:

    1. A on sõna.
    2. Kui u ja v on ühepikkused babababi sõnad, siis u+v' ja u+v* on babababi sõnad, kus
      • w' tähistab sõna, mille saame sõnast w tähtede järjekorra vastupidiseks muutmisel,
      • w* on sõna, mille saame sõnast w iga tähe väljavahetamisel vastandtähega (st A-de asendamisel B-de ja B-de asendamisel A-dega),
      • u+v tähistab sõna, mille saame, kui paarituarvulistele positsioonidele paneme järjekorras u tähed ja paarisarvulistele järjekorras v tähed (esimese kodutöö flatZip).
    3. Kõik sõnad on saadavad punktide 1 ja 2 abil.

    Kirjutada funktsioon babababi, mis annab kontrollib kas argumentstring on babababi sõna:

    > babababi :: String -> Bool
    

    Näiteks:

    babababi ""        ==>  False
    babababi "A"       ==>  True
    babababi "B"       ==>  False
    babababi "AA"      ==>  True
    babababi "AB"      ==>  True
    babababi "BA"      ==>  False
    babababi "AAAA"    ==>  True
    babababi "ABAB"    ==>  True
    babababi "AAAB"    ==>  False
    babababi "ABABAB"  ==>  False
    babababi "ABAC"    ==>  False
    

  4. (2 punkti) Tudeng astub sisse õppehoone uksest, mis asub 0-ndal korrusel, ja peab minema eksamile, mis toimub n-ndal korrusel. Asudes mingil n-ndast madalamal korrusel, võib tudeng otsustada minna järgmisele korrusele trepist, et mitte väga kähku kohale jõuda. Kui tal aga jalad on väsinud, võib ta teha otsuse kasutada lifti. Astudes lifti, saab ta järjest sõita ainult pool teed lifti astumise korrusest n-ndani, ei rohkem ega vähem (kui korruseid on jäänud paarituarv, siis sõidab ta liftiga "suurema poole"). Erinevatel korrustel tehtud otsused on üksteisest sõltumatud, st. tudeng võib näiteks pärast liftist väljumist otsustada sinna tagasi minna ja järelejäänud maast veel poole sõita.

    Kirjutada funktsioon tudeng, mis mittenegatiivsel argumendil n leiab võimaluste arvu tudengil jõuda n-ndale korrusele:

    > tudeng :: Int -> Integer
    

    Näiteks:

    tudeng 0     ==>  1
    tudeng 1     ==>  2
    tudeng 2     ==>  4
    tudeng 3     ==>  6
    tudeng 1000  ==>  264830889564
    

    NB! Antud funktsioon on defineeritav alljärgnevate võrdustega:

    tudeng 0 = 1
    tudeng n = tudeng (n-1) + tudeng (n `div` 2)
    
    See definitsioon on aga eksponentsiaalse keerukusega. Teie poolt kirjutatav definitsioon peab olema ruutkeerukusega.

  5. (3 punkti) Kirjutada funktsioon ruudud, mis "joonistab" etteantud mõõtudega ruudustiku (so. stringi, mis väljatrükkimisel on ruudustik):

    > ruudud :: Int -> Int -> Int -> String
    

    Funktsiooni esimene argument on veergude arv, teine argument on ridade arv ning kolmas argument on ühe ruudu külje pikkus. Ruudu horisontaalsed küljed on moodustatud miinusmärkidest ning vertikaalsed küljed püstkriipsudest. Näiteks:

    ruudud 2 3 1 ==> " - -\n| | |\n - -\n| | |\n - -\n| | |\n - -\n"
    ruudud 3 2 2 ==> " -- -- --\n|  |  |  |\n|  |  |  |\n -- -- --\n|  |  | |\n|  |  |  |\n -- -- --\n"
    
    või samad ruudustikud väljatrükituna:
    Main> putStr $ ruudud 2 3 1
     - -
    | | |
     - -
    | | |
     - -
    | | |
     - -
    
    Main> putStr $ ruudud 3 2 2
     -- -- --
    |  |  |  |
    |  |  |  |
     -- -- --
    |  |  |  |
    |  |  |  |
     -- -- --
    
    

    NB! Kõik read peavad olema minimaalse pikkusega; so. enne reavahetuse sümbolit peab alati olema mittetühi sümbol.


Varmo Vene