То задание по Парадигмам программирования (Scheme), которому было посвящено видео. Полные исходные коды решения, а также текст самих задач.
1) Write Scheme expressions that express the following algebraic formulae.
a. (a * 2) + (5 / 9) * (6 – b)
b. 5 * 6 + (a + (3 – (6 * 2)))
3 * (x + y) * (y * 7)
2) Define a procedure that takes four numbers as arguments and returns the sum of the squares of the smallest and largest numbers. For example, (smallest-largest-squares 1 2 4 3) => 17
3) Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluations or normal-order evaluation. He defines the following two procedures:
(define (p) (p))
(define (test x y)
(if (= x 0)
He then evaluates the expression:
(test 0 (p))
What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will Ben observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form ‘if’ is the same for both evaluation schemes: The predicate expression is evaluated first, and the result determines whether do evaluate the consequent or the alternative expression.
4) Given the following procedures:
(define (increment a) (+ a 1))
(define (decrement a) (- a 1))
(define (add% a b)
(if ( = b 0)
(add% (increment a) (decrement b))))
Write a procedure (add-negative a b) that uses only increment and decrement to add the integers a and b assuming b is negative. Then write a non-recursive procedure (add-integer a b) that uses add% and add-negative to add any pair of integers together. Using the substitution model, illustrate the process generated by evaluating (add-integer 2 3).
5) We can perform integer multiplication by means of repeated addition. The following multiplication procedure assumes that our language can only add (not multiply).
(define (multiply a b)
(if (= b 0)
(+ a (multiply a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operation double, which doubles an integer, and halve, which divides an (even) integer by 2. Write these two new functions, and using them design a multiply procedure (do not use Scheme’s multiply) that uses a logarithmic number of steps.
6) A function f is defined by the rule that f(n) = n if n <= 5 and f(n) = f(n-1) + 3f(n-3) + 5f(n-5) if n >5. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of iterative process.
7) Write a recursive procedure that computes the sum of the odd digits of a non negative integer. For example, (sum-digits 1258) => 6
8) Simpson’s Rule is an accurate method of numerical integration. Using Simpson’s Rule, the integral of a function f between a and b is approximated as
h/3[ y0 + 4y1 + 2y2 + 4y3 + 2y4 + .... + 2yn-2 + 4yn-1 + yn]
where h = (b-a)/n, for some event integer n, and yk = f(a + kh). Increasing n increases the accuracy of the approximation. Define a procedure that takes arguments f, a, b, and n and returns the value of the integral, computed using Simpson’s Rule. In one of your tests, use your procedure to integrate a cube function between 0 and 1 (with n = 100 and n = 1000). (The exact value of the integral of cube between 0 and 1 is 1/4.
9) The NumbersRUs Corporation marks each of its cartons with a numeric code to indicate that number of items of each type inside the carton. The code consists of an unlimited number of triple digits. Each triple consists of two digits specifying the type of item, followed by one digit specifying the number of that item. There can be any number of different items. For example, 128934 specifies that there are 8 items of type 12 and 4 items of type 93. Write the recursive procedure (count-of-items code type) that returns the number of items of kind type specified in code. Return -1 if there are no items of that type. Note, 159158157 specifies that there are 24 type15 items.