ФП (И+КН.1+избираема) 2022/23

Задача 1. Едно естествено число наричаме свършено, ако е с 2 по-малко от сумата на всичките си делители по-малки от него.

а) (3 т.) Да се реализира функция done?, която проверява дали дадено число е свършено.

б) (7 т.) Да се реализира функция sum-almost-done, която по подадени естествени числа a и b намира сумата на всички числа в интервала [a; b], които са по-близко до свършено число, отколкото до краищата на интервала.

Примери:

(done? 20) → #t
(done? 28) → #f

(sum-almost-done 5 24) → 153 ; сумата на числата от 13 до 21

Задача 2. (10 т.) Разглеждаме стекова машина, която представя паметта си като списък от числа и символи и приема списък от инструкции, които интерпретира по следния начин:

• ако поредната инструкция е число или символ, то се добавя на върха на стека
• ако поредната инструкция е функция, тя се прилага над всички числа в стека (допуска се, че функцията приема само един параметър), променяйки стойностите им в стека
• ако поредната инструкция е наредена двойка от операция (двуместна функция) и число n, то горните две числа на стека се изваждат и обратно на върха на стека се записва резултат от прилагането на операцията над тях. Прилагането се повтаря до изчерпване на стека или достигане до символ, но не повече от n пъти.
• всички останали инструкции се игнорират.

Да се реализира функция run-machine, която връща като резултат списък, представящ паметта на машината след последователно обработване на всички инструкции. Първоначално машината се инициализира с празен стек.

Пример:

(run-machine (list 1 'x 4 'a 9 16 25 sqrt 6))                       → (6 5 4 3 a 2 x 1)
(run-machine (list 1 'x 4 'a 9 16 25 sqrt 6 (cons + 2) (cons * 5))) → (45 a 2 x 1)

Задача 3. (10 т.) Казваме, че един списък е подсписък на друг, ако елементите на първия списък се срещат непосредствено последователно във втория. Например, '(2 4) не е подсписък на '(1 2 3 4 5), но '(2 3 4) е. Казваме, че един списък от числа a се мажорира от списъка b, ако двата списъка са с еднаква дължина n и a_i ≤ b_i за всяко i ∈ [0; n). Списък от списъци ll наричаме мажорен, ако е вярно, че l_i се мажорира от подсписък на l_i+1 за всеки два съседни списъка l_i и l_i+1 в ll.

Да се реализира функция is-major?, която проверява дали даден списък от списъци от числа е мажорен.

Примери:

(is-major? '((1 3) (4 2 7) (2 5 4 3 9 12))) → #t
(is-major? '((1 3) (4 2 7) (2 5 3 3 9 12))) → #f

Бонус: (5 т.) Да се реализира функция find-longest-major, която намира най-дългия мажорен подсписък на даден списък от списъци от числа.

Забележка: използването на всички стандартни функции в R5RS, както и на функциите accumulate, accumulate-i, filter, foldr, foldl, foldr1, foldl1 е позволено, но не е задължително.

(define (accumulate op nv a b term next)
  (if (> a b) nv
      (op (term a) (accumulate op nv (next a) b term next))))

(define (accumulate-i op nv a b term next)
  (if (> a b) nv
      (accumulate-i op (op nv (term a)) (next a) b term next)))

(define (filter p l)
  (cond ((null? l) l)
        ((p (car l)) (cons (car l) (filter p (cdr l))))
        (else (filter p (cdr l)))))

(define (foldr op nv l)
  (if (null? l) nv
      (op (car l) (foldr op nv (cdr l)))))

(define (foldl op nv l)
  (if (null? l) nv
      (foldl op (op nv (car l)) (cdr l))))

(define (foldr1 op l)
  (if (null? (cdr l)) (car l)
      (op (car l) (foldr1 op (cdr l)))))

(define (foldl1 op l)
  (foldl op (car l) (cdr l)))