;===========================ТЕМА 1=============================
;Задача 1. Да се напише функция (min-sum-digit a b k), която намира
;най-малкото от целите числа от a да b, чиято сума на цифрите се дели на k.
;Примаме, че със сигурност има число, чиято сума от цифрите, се дели на k в интервала
(define (min-sum-digit a b k)
(define (sum-digits n)
(define (sum-digits-helper n res)
(if(= 0 n)
res
(sum-digits-helper (quotient n 10)
(+ res (remainder n 10)))))
(sum-digits-helper n 0))
(define (helper i)
(if (= (remainder (sum-digits i) k) 0)
i
(helper (+ i 1))))
(helper a))
(min-sum-digit 10 20 3) ; -> 12
(min-sum-digit 10 20 7) ; -> 16
(min-sum-digit 20 40 3) ; -> 21
(min-sum-digit 110 200 8) ; -> 116
(min-sum-digit 200 300 15) ; -> 249
;Задача 2. Да се напише функция (average f g), която по две числови функции
;f : R → R и g : R → R намира средно-аритметичната функция (f⊕g)(x)=f(x)+g(x)2.
;С помощта на average да се напише функция от по-висок ред (calcprod f n), която
;намира произведението ∏ni=1(f⊕gi)(i), където gi(x) = ix. Използването на
;accumulate е позволено, но не е задължително.
(define (accumulate op null-value term a next b)
(define (helper i res)
(if(> i b)
res
(helper (next i) (op res (term i)))))
(helper a null-value))
(define (average f g)
(lambda (x) (/ (+ (f x) (g x)) 2)))
(define (calcprod f n)
(lambda (x)
(let ((gi (lambda (i) (expt I x))))
(accumulate *
1
(lambda (i) ((average f gi) i))
1
(lambda (i) (+ i 1))
n))))
((calcprod (lambda(i) i) 4) 2) ; -> 180
((calcprod (lambda (i) (* 2 i)) 4) 1) ; -> 121.5
;Задача 3. Да се дефинира функция (occurrences l1 l2). l1 и l2 са списъци от
;числа. Функцията да конструира списък с броя на срещанията на всеки от
;елементите на l1 в l2.
(define (count-occurrences-rec x l)
(cond ((null? l) 0)
((= x (car l) x) (+ 1 (count-occurrences x (cdr l))))
(else (count-occurrences x (cdr l)))))
(define (count-occurrences-it x l)
(define (helper res l)
(cond((null? l) res)
((= x (car l) x) (helper (+ res 1) (cdr l)))
(else (helper res (cdr l)))))
(helper 0 l))
(define (occurrences l1 l2)
(define (count-occurrences-it x l)
(define (helper res l)
(cond((null? l) res)
((= x (car l) x) (helper (+ res 1) (cdr l)))
(else (helper res (cdr l)))))
(helper 0 l))
(define (helper res l)
(if(null? l)
res
(helper (append res (list (count-occurrences-it (car l) l2)))
(cdr l))))
(helper '() l1))
(occurrences '(1 2 3) '( 1 2 4 1 )); -> (2 1 0)
;Задача 4. Да се дефинира предикат (match-lenghts? l1 l2). l1 и l2 са непразни
;списъци от списъци от числа. Ако l1 = (a1 a2 … ak), а l2 = (b1 b2 … bk) ,
;предикатът да връща истина, когато разликите в дължините на всяка двойка
;съответни списъци ai и bi е еднаква.
(define (match-lengths? l1 l2)
(define (helper len l1 l2)
(cond ((null? l1) #t)
((= len (- (length (car l1)) (length (car l2)))) (helper len (cdr l1) (cdr l2)))
(else #f)))
(helper (- (length (car l1)) (length (car l2))) (cdr l1) (cdr l2)))
(match-lengths? '( () (1 2) (3 4 5)) '( (1) (2 3 4) (5 6 7 9))); -> #t,
(match-lengths? '( () (1 2) (3 4 5)) '( () (2 3 4) (5 6 7))); -> #f
(match-lengths? '( () (1 2) (3 4 5)) '( () (2 3 4) (5 6 7))); -> #f
;===========================ТЕМА 2=============================
(define (accumulate op null-value term a next b)
(define (helper i res)
(if(> i b)
res
(helper (next i) (op res (term i)))))
(helper a null-value))
;Задача 1. Да се напише функция (prod-sum-div a b k), която намира
;произведението на всички цели числа от a да b, които имат сума на делителите
;кратна на k.
(define (sum-divisors x)
(accumulate +
x
(lambda (i) (if (= (remainder x i) 0)
i
0))
1
(lambda (i) (+ i 1))
(/ x 2)))
(define (prod-sum-div a b k)
(accumulate *
1
(lambda (i) (if (= (remainder (sum-divisors i) k) 0)
i
1))
a
(lambda (i) (+ i 1))
b))
(prod-sum-div 1 6 2) ; -> 90
;Задача 2. Да се напише функция (average f g), която по две числови функции
;f : R → R и g : R → R намира средно-геометричната функция (f⊗g)(x)=f(x)g(x).
;С помощта на average да се напише функция от по-висок ред (calcsum f n), която
;намира сумата ∑ni=1(f⊗gi)(i), където gi(x) = xi. Използването на accumulate
;е позволено, но не е задължително.
(define (average-geo f g) (lambda (x) (sqrt ( * (f x) (g x)))))
(define (calcsum-geo f n)
(lambda (x)
(let ((gi (lambda (i) (expt I x))))
(accumulate +
0
(lambda (i) ((average-geo f gi) i))
1
(lambda (i) (+ i 1))
n))))
;((calcsum-geo (lambda(i) i) 4) 1) ;-> 10
;Задача 3. (1.25 т.) Да се дефинира функция (duplicates l1 l2). l1 и l2 са
;списъци от числа. Функцията построява списъка от тези числа в l1, които се
;срещат повече от веднъж в l2. ;Пример: (duplicates ‘(1 2 3) ‘(1 2 1 3 2)) -> (1 2)
(define (duplicates l1 l2)
(define (occurs-more-than-once? x l)
(define (helper times l)
(cond ((> times 1) #t)
((null? l) #f)
((= x (car l)) (helper (+ times 1) (cdr l)))
(else (helper times (cdr l)))))
(helper 0 l))
(define (helper res l)
(cond ((null? l) res)
((occurs-more-than-once? (car l) l2) (helper (append res (list (car l))) (cdr l)))
(else (helper res (cdr l)))))
(helper '() l1))
;Задача 4. (1.25 т.) Да се дефинира предикат (image? l1 l2). l1 и l2 са непразни
;списъци с еднакъв брой числа.Ако l1 = (a1 a2 … ak), а l2 = (b1 b2 … bk),
;предикатът да връща истина, когатосъществува такова число x,
;че ai = x + bi ,за всяко i = 1...k.
(define (image? l1 l2)
(define (helper x l1 l2)
(cond ((null? l1) #t)
((= x (- (car l1) (car l2))) (helper x (cdr l1) (cdr l2)))
(else #f)))
(helper (- (car l1) (car l2)) (cdr l1) (cdr l2)))
(image? '(1 2 3) '(4 5 6)) ;-> #t
(image? '(1 2 3) '(1 2 2 )) ;-> #f
(define (image-with-map? l1 l2)
(equal? (map (lambda(i) (+ i (- (car l2) (car l1)))) l1) l2))
(image-map? '(1 2 3) '(4 5 6)) ;-> #t
(image-map? '(1 2 3) '(1 2 2 )) ;-> #f
Малко коментари по решенията:
Тема 1
- Както коментарът в решението правилно забелязва, условието не е съвсем коректно зададено, понеже може да няма такова число в интервала [a; b]. Дадената програма решава задачата: да се намери най-малкото число >= a, чиято сума на цифрите се дели на k. Решението е вярно. Може ли някой да напише рекурсивно решение? А решение, реализирано чрез accumulate? (или filter-accumulate?)
- Решението на average е вярно, но на calcprod е грешно. Връща се функция вместо число.
- Решението е вярно. Някой може ли да го напише с функции от по-висок ред?
- Решението е вярно, примерът в условието беше сгрешен. Отново може да се реализира с функции от по-висок ред.
Тема 2
- Вярно
- Същата грешка като на Тема 1
- Вярно, но прекалено сложно. occurs-more-than-once? може да се напише с foldr или с две последователни прилагания на memq. Итеративната реализация на duplicates налага закачане на елемент накрая, вместо да се реализира рекурсивно, когато ще е по-лесно. Най-лесно, разбира се, е с filter.
- Браво за краткото решение! Може да се реализира и с разширената версия на map, която приема операция на два аргумента и два списъка, като прилага операцията над всеки два съответни елемента на списъка, но по същество се получава същото решение.
;Задача 1. Да се напише функция (min-sum-digit a b k),
;която намира най-малкото от целите числа от a да b, чиято сума на цифрите се дели на k.
(define (filter-accum p? op nv a term b next)
(cond((< b a) nv)
((p? a)(op (term a)(filter-accum p? op nv (next a) term b next)))
(else (filter-accum p? op nv (next a) term b next))
)
)
(define (next k)(+ k 1))
(define (term x) x)
(define (sumdigits n)
(define (helper n sum)
(cond((= 0 (quotient n 10)) (+ sum (remainder n 10)))
(else (helper (quotient n 10) (+ sum (remainder n 10))))
)
)
(helper n 0)
)
(define (min-sum-digit-help a b k)
(define (check num)
(define sumdig (sumdigits num))
(= (remainder sumdig k) 0)
)
(filter-accum check min +inf.0 a term b next)
)
(define (min-sum-digit a b k)
(define m (min-sum-digit-help a b k))
(if (= m +inf.0)
#f
m
)
)
(min-sum-digit 1 40 13) ;->#f
(min-sum-digit 1 40 12) ;->39.0
(min-sum-digit 10 20 3) ; -> 12
(min-sum-digit 10 20 7) ; -> 16
(min-sum-digit 20 40 3) ; -> 21
(min-sum-digit 110 200 8) ; -> 116
(min-sum-digit 200 300 15) ; -> 249
Реализацията е вярна и идеята за filter-accum е добра.
+inf.0 е напълно ненужно, може да се използва просто (+ b 1) за nv.
Sumdigits също може да се реализира с accumulate, макар че ще е малко изкуствено. Като друг вариант на решение, може да не се търси истинската сума, а сума по модул k.