Fppexamkn1

Първото контролно по ФП за 2010 на КН 2ри курс.

Контролното беше яко, Калин + Трифон + Нишева ни дадоха да ползваме лаптопи и гледмата в Муслата(325) си заслужаваше.

Самите задачи

Не бяха трудни и определено не бяха като предварителното контролно, което беше пуснато в Moodle на предния ден ;)

Вариант Б

Задача 1

Да се напише функция (min-sum-digit a b k), която намира най-малкото от целите числа от a до b, чиято сума на цифрите се дели на k.

Решението тук е ясно - трябва ни функция, която да смята сумата от цифрите на дадено число.

(define (sum-of-digits n)
 (
   if(= n 0) 0
     (+ (remainder n 10) (sum-of-digits (quotient n 10))) ; remainder = %, quotient = / (делене с остатък, целочислено делене)
 )  
)

(define (min-sum-digit a b k)
  (
    if(> a b) 0 ; ако няма такова
      (if(= (remainder (sum-of-digits a) k) 0) a 
         (min-sum-digit (+ a 1) b k)
         )
  )  
)

Задача 2

Да се напише функция (average f g), която по две числови функции f:R->R и g:R->R намира средно-аритметичната функция (f + g) (x) = (f(x) + g(x)) / 2 . С помощта на average да се напише функция от по-висок ред (calcprod f n), която намира произведението $\displaystyle\prod_{i=1}^n\((f + g{i})(i)$, където $g{i}(x) = i^{x}$

Тази задача беше най-трудната от цялото контролно.
Функцията average трябва да върне ламбда, която да смята средното аритметично на f и g. Ако познаваш ламбдите, това няма да ти е проблем :) Кода е следния :

(define (average f g)
(
 lambda(x)(/ (+ (f x) (g x)) 2)
  )  
)

Врътката на върната ламбда е, че като извикате (average f g) се връща функция, която след това може да бъде изпълнена така : ((average f g) x)

Втората част от задачата е просто да знаете как да използвате вече написаната функция.

(define (calcprod f n)
   (define (calcprod-inner f n i result)
     (if(> i n) result
     (calcprod-inner f n (+ i 1) (* result ((average f 
                                                     (lambda(x) (expt i x)
                                                     )) i)) ; викаме върната ламбда функция с аргумент i и умножаваме резултата с полученото
     ))
   )
  (calcprod-inner f n 1 1)
)

Задача 3

Да се дефинира функция (occurrences l1 l2). l1 и l2 са списъци от числа. Функцията да конструира списък с броя на срещанията на всеки от елементите на l1 в l2.
Пример :

(occurrances (list 1 2 3) (list 1 2 4 1)) -> (2 1 0)

За задачката ще ни трябва помощна функция, която да брои срещанията на даден елемент в списък. Другото е въпрос на имплементация ;) Тази реализация използва опашкова рекурсия (заради която се налага едно обръщане на списъка накрая)

; брои срещанията на elem в list
(define (count elem list)
  ( if(null? list) 0
      (if(= (car list) elem) (+ 1 (count elem (cdr list)))
         (+ 0 (count elem (cdr list)))

         )
  )
)

(define (occurances l1 l2)
  (define (occur-inner l1 l2 result)
    (if(null? l1) result
       (occur-inner (cdr l1) l2 (cons (count (car l1) l2) result))

       )  
  )
  (reverse (occur-inner l1 l2 '()))  
)

Задача 4

Да се дефинира предикат (match-lengths? l1 l2). l1 и l2 са непразни списъци от списъци от числа. Ако l1 = (a1 a2 … ak), а l2 = (b1 b2 … bk), предикатът да връща истина, когато разликите в дължините на всички двойки съответните списъци ai и bi са еднакви.
Пример :

(match-lengths? (list (list) (list 1 2) (list 3 4 5)) (list (list 1) (list 1 2 3) (list 3 4 5 6))) -> #t
(match-lengths? (list (list) (list 1 2) (list 3 4 5)) (list (list 1) (list 1 2 3) (list 3 4 5 6 7))) -> #f

Задачката може да има множество реализации.
Ето една, която използва вътрешна функция и аргумент, за да държи дължината, която трябва да се спазва

(define (len list)
(if(null? list) 0
   (+ 1 (len (cdr list)))
   )  
)

(define (match-lengths? l1 l2)
  (define (match-inner l1 l2 const-len)
    (
     if(null? l1) #t
     (if(> (- (len (car l1)) (len (car l2))) const-len) #f
       (match-inner (cdr l1) (cdr l2) const-len))
     )
  )
  (match-inner (cdr l1) (cdr l2) (- (len (car l1)) (len (car l2))))  
)