jordyn/sicpsgjd @ b51745d6a961f90cc7bbf300f9cf88c26dcc4192

1.9
1.10
1.11
1.12
1.17
1.21
linear fibbonacci

1.9

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

this impl describes a recursive process.

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

this impl describes an iterative process

1.10

Ackerman's function:

  (define (A x y)
    (cond ((= y 0) 0)
          ((= x 0) (* 2 y))
          ((= y 1) 2)
          (else (A (- x 1)
                   (A x (- y 1))))))
(A 2 4)

(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 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

(A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) (A 1 (A 0 (A 1 3))) (A 1 (A 0 (A 0 (A 1 2)))) (A 1 (A 0 (A 0 (A 0 (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 … ) 65536

(A 0 n): 2n (A 1 n): 2^n (A 2 n): 2^2^n

1.11

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

this is the recursive approach. slow with even small numbers TODO: iterative approach

1.12

this is a pascal's triangle

1: 1 2: 1 1 3: 1 2 1 4: 1 3 3 1 5: 1 4 6 4 1 6: 1 5 10 10 5 1

6, 6 = 1 6, 1 = 1 6, 2 = 5 1, 1 = 1

write a procedure that computes the elements recursively

  (define (pascals row num)
    (if (or (= row num) (= num 1) (= row 1))
	1
	(+ (pascals (- row 1) (- num 1))
	   (pascals (- row 1) num))))
  (pascals 6 4)

1.17

(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))

  (define (double a)
    (mul a 2))
  (define (halve a)
    (/ a 2))
  (define (fast-mul a b)
  TODO

1.21

find the lowest common divisor of 199, 1999, 19999

  (define (smallest-divisor n)
    (find-divisor n 2))
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
	  ((divides? test-divisor n) test-divisor)
	  (else (find-divisor n (+ test-divisor 1)))))
  (define (divides? a b)
    (= (remainder b a) 0))

  (smallest-divisor 199)
  (smallest-divisor 1999)
  (smallest-divisor 19999)

199: 199 1999: 1999 19999: 7

linear fibbonacci

alluded to in the lecture, find a fast fibb computation

  (define (fib n)
    (fib-iter n 0 1 0))
  (define (fib-iter n count sum last-sum)
    (if (= count n)
	last-sum
	(fib-iter n (1+ count) (+ sum last-sum) sum)))
  (fib 10)

this is the linear version of the tree reversal from the lecture for this version, space = O(1) time = O(n)

the version in the lecture has time O(fib(n)) calculating the 10th elem, O(fib(n)): 55 vs O(n): 10

exercises.org 3.6 KB History Raw

1.9