Warning: file_put_contents(): Only 0 of 10 bytes written, possibly out of free disk space in /var/web/h/heller.christian/htdocs/www.plomlompom.de/PlomWiki/plomwiki.php on line 287
SolutionsSICP
PlomWiki: Zur Start-Seite Suche Letzte Änderungen (Feed) Letzte Kommentare (Feed)
Impressum Datenschutz-Erklärung

SolutionsSICP

Ansicht Bearbeiten Anzeige-Titel setzen Versions-Geschichte Seiten-Passwort setzen AutoLink-Anzeige ein-/ausschalten

My solutions to the exercises in SICP

Exercises for chapter 1.1

Exercise 1.1

10 
12 
8 
3 
6 
undefined 
undefined 
19 
#f 
4 
16 
6 
16 

Exercise 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5) ) ) ) ) (* 3 (- 6 2) (- 2 7) ) ) 

Alternative formatting:

(/ (+ 5 
      4 
      (- 2 
         (- 3 
            (+ 6 
               (/ 4 
                  5 
               ) 
            ) 
         ) 
      ) 
   ) 
   (* 3 
      (- 6 
         2 
      ) 
      (- 2 
         7 
      ) 
   ) 
) 

Exercise 1.3

The exercise didn't say what to do if all three numbers are equal, or two numbers are equal and one is bigger. I decided to return #f in that case.

(define (a-smaller-b-and-c a b c) (and (< a b) (< a c) ) ) 
(define (square a) (* a a)) 
(define (sum-of-two-squares a b) (+ (square a) (square b) ) ) 
(define (sum-of-squares-of-largest a b c) 
        (cond 
          ( (a-smaller-b-and-c a b c) (sum-of-two-squares b c) ) 
          ( (a-smaller-b-and-c b c a) (sum-of-two-squares c a) ) 
          ( (a-smaller-b-and-c c a b) (sum-of-two-squares a b) ) 
          (#t #f) 
        ) 
) 

Exercise 1.4

a-plus-abs-b returns the sum of a and the absolute value of b. It does so by choosing either + or - as the operator on the two operands a and b, + if b greater zero and therefore positive, and - otherwise.

Exercise 1.5

In normal-order evaluation, p will not by evaluated by the interpreter. In applicative-order evaluation, it will. The latter spells trouble, for p is defined as nothing but a reference to itself, recursively. According to the evaluation rules defined so far, evaluating p should send the interpreter into an infinite loop.

Exercise 1.6

At first, I could not come up with any reason why srqt should not work as before. I then tested the new code in my Scheme interpreter (does that count as cheating?) and got a "No memory!" error. That meant something was working differently (and fatally so).

I reasoned that something like in 1.5 was happening: some kind of recursion having to do with the evaluation order. But my reasonings did not get much closer to a solution. Surely consequent expressions in the cond special form should only be evaluated conditionally, even in applicate-order evaluation? I then got (this surely counts as cheating!) some hints by a friend: new-if may encapsulate cond, but it is not cond. If new-if is called on any operators, those operators are therefore evaluated first by ordinary applicate order before being put to use in the encapsulated cond statement.

In other words: Evaluation of the special form if may leave out evaluation of clauses the condition for which is not met. But the clauses of new-if are evaluated completely, no matter whether they get put to use, if applicate-order evaluation is the rule. Calls to a sqrt that uses new-if therefore lead to an infinite loop.

Exercise 1.7

Failure of good_enough? for very small numbers:

> (sqrt 4) 
2.000000093 
> (sqrt 0.04) 
0.2006099041 
> (sqrt 0.0004) 
0.03540088256 

What happens here is good_enough? returning #t too early. With x 0.001 or smaller, this happens for any guess the square of which is below 0.001, no matter how precise it is in the digits further to the right. Furthermore, the smaller x, the more improve converges towards merely dividing guess by 2 during its first runs. Only few such divisions are needed to make guess fall below the root of 0.001. As a result, sqrt on x below 0.001 converges towards a single value the smaller x becomes: 0.03125, or the first guess of 1.00 divided by 2 as often as necessary (five times) to have it fall below the root of 0.001.

Failure of good_enough? for very large numbers:

> (sqrt 40000000000000000) 
200000000 
> (sqrt 4000000000000000000) 
2000000000 
> (sqrt 400000000000000000000) 

(At this point, the interpreter freezes.)

The value 400000000000000000000 confuses all kinds of operations. If put into good_enough?, for example, with the start guess of 1.00, the sub-expression (- (square guess) x), evaluated first to (- 1.00 400000000000000000000), evaluates not to -399999999999999999999 as expected, but rather to -9.223372037e+18. The probable explanation is that the interpreter only works sanely for values the binary machine representations of which fit into 64 bit. Greater values overflow.

The failure on small numbers is repaired by following the good_enough? redefinition proposed in the exercise text; the failure on large numbers is not:

(define (good-enough? guess x) 
        (< (prop-diff guess (improve guess x)) 
           0.001)) 
(define (prop-diff-a-greater-b a b) 
        (/ 1 
           (/ a 
              (- a b)))) 
(define (prop-diff a b) 
        (cond ((> a b) (prop-diff-a-greater-b a b)) 
              ((< a b) (prop-diff-a-greater-b b a)) 
              (#t 0))) 

Exercise 1.8

(define (average x y) (/ (+ x y) 2)) 
(define (abs x) (if (< x 0) (- x) x)) 
(define (square x) (* x x)) 
(define (prop-diff-a-greater-b a b) (/ 1 (/ a (- a b)))) 
(define (prop-diff a b) 
        (cond ((> a b) (prop-diff-a-greater-b a b)) 
              ((< a b) (prop-diff-a-greater-b b a)) 
              (#t 0))) 
(define (curt x) (curt-iter 1.0 x)) 
(define (curt-iter guess x) (if (curt-good-enough? guess x) 
                                guess 
                                (curt-iter (curt-improve guess x) x))) 
(define (curt-improve guess x) (/ (+ (/ x (square guess)) 
                                     (* 2 guess)) 
                                  3)) 
(define (curt-good-enough? guess x) 
        (< (prop-diff guess (curt-improve guess x)) 
           0.001)) 

Exercises for chapter 1.2

Exercise 1.9

(+ 4 5) 
(if (= 4 0) 5 (inc (+ (dec 4) 5))) 
(if (#false) 5 (inc (+ (dec 4) 5))) 
(inc (+ (dec 4) 5)) 
(inc (+ 3 5)) 
(inc (if (= 3 0) 5 (inc (+ (dec 3) 5)))) 
(inc (if (#false) 5 (inc (+ (dec 3) 5)))) 
(inc (inc (+ (dec 3) 5))) 
(inc (inc (+ 2 5))) 
(inc (inc (if (= 2 0) 5 (inc (+ (dec 2) 5))))) 
(inc (inc (if (#false) 5 (inc (+ (dec 2) 5))))) 
(inc (inc (inc (+ (dec 2) 5))))) 
(inc (inc (inc (+ 1 5)))) 
(inc (inc (inc (if (= 1 0) 5 (inc (+ (dec 1) 5)))))) 
(inc (inc (inc (if (#false) 5 (inc (+ (dec 1) 5)))))) 
(inc (inc (inc (inc (+ (dec 1) 5)))))) 
(inc (inc (inc (inc (+ 0 5))))) 
(inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5))))))) 
(inc (inc (inc (inc (if (#true) 5 (inc (+ (dec 0) 5))))))) 
(inc (inc (inc (inc 5)))) 
(inc (inc (inc 6))) 
(inc (inc 7)) 
(inc 8) 
9 
(+ 4 5) 
(if (= 4 0) 5 (+ (dec 4) (inc 5))) 
(if (#false) 5 (+ (dec 4) (inc 5))) 
(+ (dec 4) (inc 5)) 
(+ 3 6) 
(if (= 3 0) 6 (+ (dec 3) (inc 6))) 
(if (#false) 6 (+ (dec 3) (inc 6))) 
(+ (dec 3) (inc 6)) 
(+ 2 7) 
(if (= 2 0) 7 (+ (dec 2) (inc 7))) 
(if (#false) 7 (+ (dec 2) (inc 7))) 
(+ (dec 2) (inc 7)) 
(+ 1 8) 
(if (= 1 0) 8 (+ (dec 1) (inc 8))) 
(if (#false) 8 (+ (dec 1) (inc 8))) 
(+ (dec 1) (inc 8)) 
(+ 0 9) 
(if (= 0 0) 9 (+ (dec 0) (inc 9))) 
(if (#true) 9 (+ (dec 0) (inc 9))) 
9 

The first procedure's process is recursive: With each recursion, another inc operation is deferred. The second procedure's process is iterative: The number of state variables stays fixed to the initial two (a, b).

Exercise 1.10

(A 1 10) 
(A (- 1 1) (A 1 (- 10 1))) 
(A (- 1 1) (A 1 9)) 
(A 0 (A (- 1 1) (A 1 (- 9 1)))) 
(A 0 (A (- 1 1) (A 1 8)))) 
(A 0 (A 0 (A (- 1 1) (A 1 (- 8 1))))) 
(A 0 (A 0 (A (- 1 1) (A 1 7)))) 
(A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))) 
(A 0 (A 0 (A 0 (A 0 (A 1 6))))) 
(A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1))))))) 
(A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 5)))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1)))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 4))))))) 
(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 (- 1 1) (A 1 (- 4 1))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 3)))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1)))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 2))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1))))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (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 8))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 32))))) 
(A 0 (A 0 (A 0 (A 0 64)))) 
(A 0 (A 0 (A 0 128))) 
(A 0 (A 0 256)) 
(A 0 512) 
1024 = 2^10 

Next one:

(A 2 4) 
(A (- 2 1) (A 2 (- 4 1))) 
(A (- 2 1) (A 2 3)) 
(A 1 (A (- 2 1) (A 2 (- 3 1)))) 
(A 1 (A (- 2 1) (A 2 2))) 
(A 1 (A 1 (A (- 2 1) (A 2 (- 2 1))))) 
(A 1 (A 1 (A (- 2 1) (A 2 1)))) 
(A 1 (A 1 (A 1 2))) 
(A 1 (A 1 (A 1 2))) 
(A 1 (A 1 (A (- 1 1) (A 1 (- 2 1))))) 
(A 1 (A 1 (A (- 1 1) (A 1 1)))) 
(A 1 (A 1 (A 0 2))) 
(A 1 (A 1 4)) 
(A 1 (A (- 1 1) (A 1 (- 4 1)))) 
(A 1 (A (- 1 1) (A 1 3))) 
(A 1 (A 0 (A 1 3))) 
(A 1 (A 0 (A (- 1 1) (A 1 (- 3 1))))) 
(A 1 (A 0 (A (- 1 1) (A 1 2)))) 
(A 1 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))) 
(A 1 (A 0 (A 0 (A (- 1 1) (A 1 1))))) 
(A 1 (A 0 (A 0 (A 0 2)))) 
(A 1 (A 0 (A 0 4))) 
(A 1 (A 0 8)) 
(A 1 16) 
(A (- 1 1) (A 1 (- 16 1))) 
(A (- 1 1) (A 1 15)) 
(A 0 (A 1 15)) 
(A 0 (A (- 1 1) (A 1 (- 15 1)))) 
(A 0 (A (- 1 1) (A 1 14))) 
(A 0 (A 0 (A 1 14))) 

(at this point, I get too lazy to go on; I know the pattern from above, y-1 times "(A 0 " followed by "2" followed by the necessary closing brackets …)

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64)))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128))))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256)))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512))))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024)))))) 
(A 0 (A 0 (A 0 (A 0 (A 0 2048))))) 
(A 0 (A 0 (A 0 (A 0 4096)))) 
(A 0 (A 0 (A 0 8192))) 
(A 0 (A 0 16384)) 
(A 0 32768) 
65536 = 2^16 

Next one:

(A 3 3) 
(A (- 3 1) (A 3 (- 3 1))) 
(A (- 3 1) (A 3 2)) 
(A 2 (A (- 3 1) (A 3 (- 2 1)))) 
(A 2 (A (- 3 1) (A 3 1))) 
(A 2 (A 2 2)) 
(A 2 (A (- 2 1) (A 2 (- 2 1)))) 
(A 2 (A (- 2 1) (A 2 1))) 
(A 2 (A 1 2)) 
(A 2 (A (- 1 1) (A 1 (- 2 1)))) 
(A 2 (A (- 1 1) (A 1 1))) 
(A 2 (A 0 2)) 
(A 2 4) 

(I know from the last evaluation what this leads too …)

65536 = 2^16 

f(n) = 2n
g(n) = 2^n
h(n) = 2^(h(n-1)) (the question only dealt with n>=1 – this solution is valid with h(0)=1 as per the Scheme code; alternative notation: "2" followed by n-1 times "^2")

Exercise 1.11

Procedure that leads to a recursive process:

(define (f n) 
        (if (< n 3) 
            n 
            (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))) 

Procedure that leads to an iterative process:

(define (f x) 
        (define (iter a b c n) 
                (if (= n 0) 
                    a 
                    (iter (+ a (* 2 b) (* 3 c)) a b (- n 1)))) 
        (if (< x 3) 
            x 
            (iter 2 1 0 (- x 2)))) 

Exercise 1.12

This computes the value of the x-th element of the y-th row of Pascal's triangle:

(define (p y x) (cond ((< x 1) 0) 
                      ((= 1 x) 1) 
                      ((< y x) 0) 
                      (else (+ (p (- y 1) x) (p (- y 1) (- x 1)))))) 

Exercise 1.13

Spent quite some time on this one, without success. Seems my algebra is too bad. Here's some solutions by others:

Kommentare

Keine Kommentare zu dieser Seite.

Schreibe deinen eigenen Kommentar

Kommentar-Schreiben derzeit nicht möglich: Kein Captcha gesetzt.

PlomWiki-Engine lizensiert unter der AGPLv3. Quellcode verfügbar auf GitHub.