Fppexamkn1 - Лекциите на ФМИ
Fppexamkn1
Първото контролно по ФП за 2010 на КН 2ри курс.
Контролното беше яко, Калин + Трифон + Нишева ни дадоха да ползваме лаптопи и гледмата в Муслата(325) си заслужаваше.
Самите задачи
Не бяха трудни и определено не бяха като предварителното контролно, което беше пуснато в Moodle на предния ден ;)
Да се напише функция (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(&gt; a b) 0 ; ако няма такова
(if(= (remainder (sum-of-digits a) k) 0) a
(min-sum-digit (+ a 1) b k)
Да се напише функция (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(&gt; 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)
Да се дефинира функция (occurrences l1 l2). l1 и l2 са списъци от числа. Функцията да конструира списък с броя на срещанията на всеки от елементите на l1 в l2.
(occurrances (list 1 2 3) (list 1 2 4 1)) -&gt; (2 1 0)
За задачката ще ни трябва помощна функция, която да брои срещанията на даден елемент в списък. Другото е въпрос на имплементация ;) Тази реализация използва опашкова рекурсия (заради която се налага едно обръщане на списъка накрая)
; брои срещанията на elem в list
(define (count elem list)
(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 '()))
Да се дефинира предикат (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))) -&gt; #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))) -&gt; #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(&gt; (- (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))))
page revision: 9, last edited: 23 Nov 2010 23:00