134 lines
3.8 KiB
Plaintext
134 lines
3.8 KiB
Plaintext
1.9:
|
|
|
|
(define (+ a b)
|
|
(if (= a 0) b (inc (+ (dec a) b))))
|
|
|
|
(+ 4 5)
|
|
(if (= 4 0) 4 (inc (+ (dec 4) 5)))
|
|
(inc (+ 3 5))
|
|
(inc (inc (+ 2 5)))
|
|
(inc (inc (inc (+ 1 5))))
|
|
(inc (inc (inc (inc (+ 0 5)))))
|
|
(inc (inc (inc (inc 5))))
|
|
(inc (inc (inc 6)))
|
|
(inc (inc 7))
|
|
(inc 8)
|
|
9
|
|
|
|
Recursive
|
|
|
|
|
|
(define (+ a b)
|
|
(if (= a 0) b (+ (dec a) (inc b))))
|
|
|
|
(+ 4 5)
|
|
(+ 3 6)
|
|
(+ 2 7)
|
|
(+ 1 8)
|
|
(+ 0 9)
|
|
9
|
|
|
|
Iterative
|
|
|
|
|
|
1.10:
|
|
|
|
(define (A x y)
|
|
(cond ((= y 0) 0)
|
|
((= x 0) (+ 2 y))
|
|
((= y 1) 2)
|
|
(else (A (- x 1)
|
|
(A x (- y 1))))))
|
|
|
|
(A 1 10)
|
|
(A 0 (A 1 9))
|
|
(A 0 (A 0 (A 1 8)))
|
|
(A 0 (A 0 (A 0 (A 1 7))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 6)))))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
|
|
(A 0 (A 0 (A 0 (A 0 (A 0 10))))))
|
|
(A 0 (A 0 (A 0 (A 0 12)))))
|
|
(A 0 (A 0 (A 0 14))))
|
|
(A 0 (A 0 16)))
|
|
(A 0 18)
|
|
22
|
|
|
|
(A 2 4) = 16
|
|
(A 3 3) = 16
|
|
|
|
|
|
1.34
|
|
|
|
(define (f g) (g 2))
|
|
|
|
(f f) gives error Error: call of non-procedure: 2. This is because it is expecting the
|
|
second argument to be a procedure (implicitly from the fact that it applies it to 2).
|
|
|
|
|
|
1.35
|
|
|
|
Golden ratio: phi = (1 + sqrt(5))/2
|
|
|
|
Let x' be a fixed point of x |-> 1 + 1/x. Then
|
|
|
|
x' = 1 + 1/x' = (x' + 1)/x'
|
|
x'^2 = x' + 1
|
|
x'^2 - x' - 1 = 0
|
|
|
|
Solutions: (1 +- sqrt(1 + 4)) / 2. So phi is one of the fixed points.
|
|
|
|
|
|
2.64
|
|
|
|
partial-tree parititions the list into a left tree, the node, and a right tree. This
|
|
is done such that the node is of size 1 and the left and right are equal for an odd-sized
|
|
list and left is 1 smaller than right for an even sized list. partial-tree is then called
|
|
on the left and right sub trees. The base case for the recursion is when the left and right
|
|
trees are both of size 0. In this case, partial tree returns a leaf node (i.e. with null
|
|
left and right pointers).
|
|
|
|
Each element of the list is visited once, and for each visit, make-tree is called (which is
|
|
just a call to list, which is assumed to be O(1)). So list->tree is O(n).
|
|
|
|
|
|
2.77
|
|
|
|
It is necessary to call apply-generic for each layer of tagged data. Previously
|
|
there were only generic functions defined for complex data tagged with 'rect or
|
|
'polar. Adding the complex package means we call apply-generic once for the complex
|
|
tag and then again for the 'rect or 'polar tag, using the same real-part, imag-part,
|
|
magnitude and angle functions. This works because these are defined in terms of
|
|
apply-generic, which in turn uses the package definition.
|
|
|
|
For z as in the example,
|
|
(magnitude z)
|
|
(apply-generic 'magnitude z)
|
|
(magnitude ('rectangular 3 . 4))
|
|
(apply-generic 'magnitude ('rectangular 3 . 4))
|
|
(sqrt (+ (square 3) (square 4)))
|
|
5
|
|
|
|
|
|
3.27
|
|
|
|
For i = 0 or 1, (memo-fib i) is O(1). For i > 1, it is n additions. This is because
|
|
for each i, (memo-fib i) is only calculated once. This calculation is O(n) and each subsequent
|
|
lookup is O(1). So, even though (memo-fib i) is called multiple times for each i, only i additions are
|
|
done for each.
|
|
|
|
This scheme will not work if we use (define memo-fib (memoize fib)). The fib procedure is
|
|
defined recursively in terms of itself, and each of the these recursive calls will be evaluated in
|
|
an environment whose enclosing environment is the global environment. This explicitly does not include
|
|
the table of pre calculated results, so we will not get the benefit of this. Defining memo-fib recursively
|
|
in terms of itself means that the recursive calls are evaluated in an environment whose enclosing
|
|
environment is one where memoize has been evaluated, and thus it contains the table. This is critical
|
|
to make the memoization work as required.
|