Примерни задачи за изпит
Вариант А
Задача 1. (Haskell/Scheme) Да се построи функция approximate f l, където l е непразен списък от едноместни числови функции, а f е едноместна числова функция. Резултатът от функцията да е едноместна числова функция на аргумент x, която дава стойността h(x) на тази фунция h от списъка l, за която числото h(x)-f(x) е най-малко по абсолютна стойност.
Пример: Ако fn = approximate (\x->x) [(\x->x*x), (\x->x+1)], то fn 0.5 -> 0.25, а fn 2 -> 3
Задача 2. (Haskell/Scheme) Да се напише функция iterator l f, която проверява дали всеки елемент на списъка от числа l, без първия, се получава от предишния чрез едноместната числова функция f.
Пример:
iterator [ 3, 4, 5 ] (+1) → True
iterator [ 1, 2, 4 ] (+1) → False
Задача 3. (Scheme) Да се дефинира функция cousins, която за дадено двоично дърво от цели числа и даден възел на дървото намира всички възли, които са негови братовчеди, т.е. имат общ дядо/баба с дадения възел. Да се опише избраното представяне на дървото и да се напише как се представя дървото от примера на дъската.
Задача 4. (Haskell) Батерия се описва с типа type Battery = (Int, Double), като наредената двойка задава капацитета на батерията във ватчасове и цена. Да се напише функция bestBattery :: [Battery] -> Int -> Double, която по даден списък от батерии и капацитет k намира цената на най-евтината батерия, която има капацитет поне k.
Пример: bestBattery[(10, 0.50), (25, 1.10), (30, 1.5), (32, 1.3), (40, 1.6)] 28 → 1.3
Вариант Б
Задача 1. (Haskell/Scheme) Нека L = [x1,x2 ,…,xn] е списък от цели числа, като всички xi са различни помежду си. Казваме, че L представя целочислената функция f, ако f(xi)=xi+10 за 1≤i≤n и f(x) = 0 за x∉{x1,..,xn}. Да се дефинира функцията listToFunction L, която по даден списък L връща функцията, която той представя.
Пример:
f = listToFunction [1,2,3]
f 3 -> 13, f 1 -> 11, f 8 -> 0
Задача 2. (Haskell/Scheme) Нека L = [(x1,y1),(x2,y2),…,(xn,yn)] е списък от двойки от цели числа, като всички xi са различни помежду си. Казваме, че L представя двуместния предикат p, ако p(xi,yi) = True за 1≤i≤n и p(x,y)=False за всички други комбинации от аргументи. Да се дефинира функцията listToPredicate L, която по даден списък L връща предиката, който той представя.
Пример:
p = listToPredicate [(1,2),(2,3),(3,8)]
p 1 2 -> True, p 2 3 -> True, p 5 8 -> False
Задача 3. (Scheme) Да се дефинира функция twoCousins, която за дадено двоично дърво от цели числа проверява дали в дървото съществува поне един възел, който има точно два братовчеда (братовчедите на даден възел имат общ дядо/баба с този възел възел).
Задача 4. (Haskell) Шоколадова вафла се описва с типа type Waffle = (Int, Double), като наредената двойка задава енергийното съдържание в килокалории и цената на вафлата. Да се напише функция healthiestWaffle :: [Waffle] -> Double -> Int, която по списък от вафли и налична сума s намира килокалориите на вафлата с възможно най-малко енергийно съдържание, която струва най-много s. Пример: healthiestWaffle [(524, 0.45), (526, 0.80), (515, 0.60), (567, 0.50), (573, 0.35)] 0.50 → 524