Домашно №4 за гр.1 и гр.2
Completion requirements
Due: Monday, 25 January 2016, 12:00 AM
Това е първото и последно домашно на Haskell за студентите, които посещават упражненията на гр.1 и гр.2. Срокът е до края на семестъра, като отново са позволени многократни предавания, за които ще давам обратна връзка. Моля, предавайте всички задачи в един .hs или .lhs файл, без значение от името му.
Зад.1. Да се напише функция primeSqSum, която намира сумата на квадратите на всички прости числа в даден интервал:
primeSqSum 1 10 -> 87 -- 87 = 22 + 32 + 52 + 72
primeSqSum 10 20 -> 940 -- 940 = 112 + 132 + 172 + 192
primeSqSum 24 28 -> 0
Зад.2. Да се напише функция seriesSum, която намира сумата на първите n члена на редицата 1, -1/2, 1/3, -1/4, ...:
seriesSum 3 -> 0.8333... -- 0.8333... = 5/6 = 1 - 1/2 + 1/3
Зад.3. Да се напише функция slice, която взима подсписъка от i-тия до j-тия елемент на даден списък (броейки от 1):
slice 3 7 "abcdefghi" -> "cdefg"
slice 2 5 [1..] -> [2,3,4,5]
Зад.4. Да се напише функция removeNth, която премахва всеки n-ти елемент от даден списък:
removeNth 3 [1..10] -> [1,2,4,5,7,8,10]
Зад.5. Да се напише функцията merge, която слива два сортирани списъка в нов, също сортиран списък:
merge [1,4,8,9] [2,3,5,6,7,10] -> [1,2,3,4,5,6,7,8,9,10]
Заб.: реализирайте класическия алгоритъм за сливане на списъци - решения от типа "merge l1 l2 = sort (l1 ++ l2)" няма да се зачитат!
Бонус1: Да се напише функция mergeSort, която сортира списък по едноименния алгоритъм във време O(nlgn).
Бонус2: Твърдението на Голдбах (Christian Goldbach) гласи, че всяко четно число (освен 2) може да се представи като сбор на две прости числа по поне един начин. Това твърдение е проверено за всички числа до 4х1018 и за целите на това домашно ще го считаме за вярно. Да се напише функция goldbachPair, която връща едно разбиване на четно число на две прости събираеми във вида на наредена двойка:
goldbachPair 8 -> (3,5)
goldbachPair 10 -> (3,7) -- а може и (5,5)
Домашното се води за 5т., като всяка една от двете бонус задачи носи по 20% отгоре.