Praktikumi harjutusülesandeid

  1. Kirjutada funktsioon sumList, mis leiab täisarvude listi summa.

    > sumList :: [Integer] -> Integer
    

    Näiteks:

    sumList [1..10]   ==>   55
    sumList [3,1,2]   ==>   6
    sumList [2]       ==>   2
    sumList []        ==>   0
    


  2. Kirjutada funktsioon minList, mis leiab täisarvude listist minimaalse elemendi.

    > minList :: [Integer] -> Integer
    

    Näiteks:

    minList [1,2,0,5]   ==>   0
    minList [1..10]     ==>   1
    minList [5]         ==>   5
    


  3. Kirjutada funktsioon remSpace, mis etteantud stringi algusest eemaldab kõik tühisümbolid.

    > remSpaces :: String -> String
    

    Näiteks:

    remSpaces "  ab c  d"      ==>   "ab c  d"
    remSpaces "\n\tab c  d"    ==>   "ab c  d"
    remSpaces "ab c  d"        ==>   "ab c  d"
    


  4. Kirjuta funktsioon lastElem, mis väljastab etteantud listi viimase elemendi.

    > lastElem :: [a] -> a
    

    Näiteks:

    lastElem [1]      ==>   1
    lastElem [1,2,3]  ==>   3
    lastElem [1..10]  ==>   10
    


  5. Kirjuta funktsioon takeLast, mis väljastab listist etteantud arv viimast elementi.

    > takeLast :: Int -> [a] -> [a]
    

    Näiteks:

    takeLast 4 [1..10]   ==>   [7,8,9,10]
    


  6. Pythagorase kolmik on positiivsete täisarvude kolmik (x,y,z), mille korral kehtb x^2 + y^2 = z^2. Kirjuta funktsoon triads, mis leiab kõik Pythagorase kolmikud mille komponendid on vahemikus [1..n].

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

    Näiteks:

    triads 4   ==>  []
    triads 5   ==>  [(3,4,5)]
    triads 10  ==>  [(3,4,5),(6,8,10)]
    triads 20  ==>  [(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)]
    


  7. Positiivne täisarv on täiuslik, kui ta võrdub oma kõigi tegurite (välja arvatud arv ise) summaga. Kirjuta funktsioon perfect, mis leiab kõigi täiuslike arvude listi etteantud piirini.

    perfect :: Int -> [Int]
    

    Näiteks:

    perfect 500   ==>   [6,28,496]
    


  8. Kirjutada funktsioon shuffle, mis saades argumendiks listi, paigutab selle elemendid ringi selliselt, et esimene element läheb esimeseks, viimane teiseks, teine kolmandaks, tagant teine neljandaks, jne.

    > shuffle :: [a] -> [a]
    

    Näiteks:

    shuffle []      ==>  []
    shuffle [1]     ==>  [1]
    shuffle [1,2]   ==>  [1,2]
    shuffle [1,2,3] ==>  [1,3,2]
    shuffle [1..4]  ==>  [1,4,2,3]
    shuffle [1..5]  ==>  [1,5,2,4,3]
    


  9. Kirjutada funktsioon bins, mis väljastab kõik võimalikud antud pikkusega binaarsed arvud (sümbolitest '0' ja '1' koosnevate stringidena).

    > bins :: Int -> [String]
    

    Näiteks:

    bins 0  ==>  [""]
    bins 1  ==>  ["0","1"]
    bins 2  ==>  ["00","01","10","11"]
    bins 3  ==>  ["000","001","010","011","100","101","110","111"]
    


  10. Kirjutada funktsioon gaps, mis väljastab kõik võimalikud argumentlistist ühe elemendi eemaldamised.

    > gaps :: [a] -> [[a]]
    

    Näiteks:

    gaps []      ==>  []
    gaps [1]     ==>  [[]]
    gaps [1,2]   ==>  [[2],[1]]
    gaps [1..4]  ==>  [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]
    


  11. Kirjutada funktsioon splitBy, mis saab argumentideks predikaadi ja listi ning väljastab kaks listi, milles esimeses on kõik need argumentlisti elemendid millel predikaat on täidetud ning teises ülejäänud elemendid.

    > splitBy :: (a -> Bool) -> [a] -> ([a],[a])
    

    Näiteks:

    splitBy (>5) [1..10]         ==>  ([6,7,8,9,10],[1,2,3,4,5])
    splitBy (>5) [7,2,3,5,9,7,4] ==>  ([7,9,7],[2,3,5,4])
    splitBy (>5) [2]             ==>  ([],[2])
    splitBy (>5) []              ==>  ([],[])
    


  12. Milline on failis ListSort.lhs toodud funktsiooni verSlowSort keerukus parimal juhul?


  13. Astendamise naiivne algoritm on järgmine:

    pow :: Integer -> Integer -> Integer
    pow x 0     = 1
    pow x (n+1) = x * pow x n
    

    Kasutades jaga ja valitse tehnikat, realiseerige astendamise arvutamiseks efektiivsem algoritm.


  14. Kirjutada funktsioon segments, mis tükeldab argumentlisti mittekahanevate segmentide listiks.

    > segments :: Ord a => [a] -> [[a]]
    

    Segmendid peavad olema maksimaalse võimaliku pikkusega (ehk segmentide arv peab olema minimaalne). Näiteks:

    segments []               ==>  []
    segments [1]              ==>  [[1]]
    segments [3,4,5,5,1,2,3]  ==>  [[3,4,5,5],[1,2,3]]
    segments [1,2,3,4]        ==>  [[1,2,3,4]]
    segments [4,3,2,1]        ==>  [[4],[3],[2],[1]]
    


  15. Failis ListSort.lhs toodud merge-sort algoritmi realisatsioon on alati keerukusega n*log n. Algoritmi on võimalik modifitseerida selliselt, et parimal juhul (kui argumentlist on järjestatud) oleks keerukus lineaarne. Selleks tükeldame argumentlisti kõigepealt mittekahanevate segmentide listiks (kasutades eelmises ülesandes realiseeritavat funktsiooni segments) ja seejärel "sulatame" segmendid funktsiooni mergeall abil paarikaupa kokku nii et järjestus säiliks, kuni kogu list on sorteeritud. Seega modifitseeritud merge-sort on defineeritav kui:

    > msort :: Ord a => [a] -> [a]
    > msort = mergeall . segments
    

    Kirjuta funktsioon mergeall kasutades "jaga ja valitse" tehnikat.

    > mergeall :: Ord a => [[a]] -> [a]
    

    NB! Funktsiooni mergeall keerukus halvimal juhul peab olema n * log n.


  16. Lahendada krüptoaritmeetiline ülesanne:

           yks
           yks
         +kolm
         -----
          viis
    

    Tuleb leida toodud ülesande kõikvõimalikud lahendused. Iga lahendus on kujul [i,k,l,m,o,s,v,y]; so. täisarvude list, mille esimesene element vastab tähele i, teine tähele k jne. Iga täht tähistab erinevat numbrit ning sõnade esimesed tähed (so. y, k ja v) ei tohi olla nullid.

    Lahenduse "skelett" ja lahendite väljatrükkimiseks vajalikud funktsioonid on toodud moodulis Puzzle.lhs, mis "piltide" kostrueerimiseks kasutab moodulit Pictures.hs.


Varmo Vene