Форум за въпроси

Решения на примерни задачи за контролно 1

Решения на примерни задачи за контролно 1

by Диан Тодоров -
Number of replies: 3
;===========================ТЕМА 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



In reply to Диан Тодоров

Re: Решения на примерни задачи за контролно 1

by Трифон Трифонов -

Малко коментари по решенията:

Тема 1

  1. Както коментарът в решението правилно забелязва, условието не е съвсем коректно зададено, понеже може да няма такова число в интервала [a; b]. Дадената програма решава задачата: да се намери най-малкото число >= a, чиято сума на цифрите се дели на k. Решението е вярно. Може ли някой да напише рекурсивно решение? А решение, реализирано чрез accumulate? (или filter-accumulate?)
  2. Решението на average е вярно, но на calcprod е грешно. Връща се функция вместо число.
  3. Решението е вярно. Някой може ли да го напише с функции от по-висок ред?
  4. Решението е вярно, примерът в условието беше сгрешен. Отново може да се реализира с функции от по-висок ред.

Тема 2

  1. Вярно
  2. Същата грешка като на Тема 1
  3. Вярно, но прекалено сложно. occurs-more-than-once? може да се напише с foldr или с две последователни прилагания на memq. Итеративната реализация на duplicates налага закачане на елемент накрая, вместо да се реализира рекурсивно, когато ще е по-лесно. Най-лесно, разбира се, е с filter.
  4. Браво за краткото решение! Може да се реализира и с разширената версия на map, която приема операция на два аргумента и два списъка, като прилага операцията над всеки два съответни елемента на списъка, но по същество се получава същото решение.
In reply to Трифон Трифонов

Re: Решения на примерни задачи за контролно 1

by Моника Спасова -

;Задача 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

In reply to Моника Спасова

Re: Решения на примерни задачи за контролно 1

by Трифон Трифонов -

Реализацията е вярна и идеята за filter-accum е добра.

+inf.0 е напълно ненужно, може да се използва просто (+ b 1) за nv.

Sumdigits също може да се реализира с accumulate, макар че ще е малко изкуствено. Като друг вариант на решение, може да не се търси истинската сума, а сума по модул k.