Упражнение, СИ, 17.10
План:
- Преговор - cond, if
- Локални дефиниции
- Модели на оценяване - applicative vs. normal order evaluation; силна и слаба нормализация
- Специални форми
- Линейна, дървовидна и опашкова рекурсия
Интерактивна сесия: REPL.it
Задача 1: Да се напише функция, която взима 3 числа и връща сумата от квадратите на двете по-големи.
; Define a procedure that takes three numbers ; as arguments and returns the sum of the ; squares of the two larger numbers. (define (f a b c) (define (sum-of-squares a b) (+ (* a a) (* b b))) (cond ((and (> a c) (> b c)) (sum-of-squares a b)) ((> a b) (sum-of-squares a c)) (else (sum-of-squares b c))))
Задача 2: Какво изчислява следната функция?
; What does the following function compute? (define (mystery a b) ((if (> b 0) + -) a b))
Задача 3: Как да определим модела на оценяване в нашия интерпретатор?
; How to determine whether the interpreter is using ; applicative-order evaluation or normal-order evaluation: (define (p) (p)) (define (test x y) (if (= x 0) 0 y)) (test 0 (p))
Задача 4: Как да (не) си имплементираме if сами:
; My new 'if' implementation. ; Is there something wrong with it? (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) (define (reciprocal n) (new-if (= n 0) (raise "zero division!") (/ 1 n))) (reciprocal 4)
Задача 5: Да се напишат функции, които пресмятат сумата и произведението на числата от 1 до n.
; Linear recursion (define (sum n) (if (zero? n) 0 (+ n (sum (- n 1))))) (define (fact n) (if (zero? n) 1 (* n (fact (- n 1)))))
Задача 6: Да се напишат итеративни функции, които пресмятат сумата и произведението на числата от 1 до n.
; Tail recursion (define (sum-1 n) (define (sum-iter n s) (if (zero? n) s (sum-iter (- n 1) (+ s n)))) (sum-iter n 0)) (define (fact-1 n) (define (fact-iter n p) (if (zero? n) p (fact-iter (- n 1) (* p n)))) (fact-iter n 1))
Задача 7: Напишете функция, която пресмята n-тото число на Фибоначи.
; Tree recursion (define (fib n) (cond ((zero? n) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
Задача 8: Напишете итеративна функция, която пресмята n-тото число на Фибоначи.
; Fibonacci's tale (or tail) (define (fib-1 n) (define (fib-iter n a0 a1) (cond ((zero? n) a0) ((= n 1) a1) (else (fib-iter (- n 1) a1 (+ a0 a1))))) (fib-iter n 0 1))
Последно модифициране: петък, 21 октомври 2016, 15:10