SCIP Exercise Code

;; 1.1.7
;; Newton's sqrt method
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)
      )
  )

(define (improve guess x)
  (average guess (/ x guess))
  )

(define (average x y)
  (/ (+ x y) 2)
  )

(define (good-enough? guess x)
  (< (/ (abs (- (improve guess x) guess)) guess) 0.001)
  )

(define (sqrt x)
  (sqrt-iter 1.0 x)
  )

;; Newton's cube root method
(define (cube-iter guess x)
  (if (cube-good-enough? guess x)
      guess
      (cube-iter (improve-cube guess x) x)
      )
  )

(define (improve-cube guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3)
  )

(define (cube-good-enough? guess x)
  (< (/ (abs (- (improve-cube guess x) guess)) guess) 0.001)
  )

(define (cubert x)
  (cube-iter 1.0 x)
  )

;; lexical scoping
(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

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

;; iterative
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

;; (+ 4 5)
;; (+ 3 6)
;; (+ 2 7)
;; (+ 1 8)
;; (+ 0 9)
;; 9

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

;; (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)))
;; 2^2^2^2

;; (A 3 3)
;; (A 2 (A 3 2))
;; (A 2 (A 2 (A 3 1)))
;; (A 2 (A 2 2))
;; (A 2 (A 1 (A 2 1)))
;; (A 2 (A 1 (A 1 2)))
;; 2^2^2^2

;; 2n
(define (f n) (A 0 n))

;; 2^n
(define (g n) (A 1 n))

;; 2^(2^2...(n times))
(define (h n) (A 2 n))

;; tree recursion version
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

;; linear iteration version
;; if want to reduce steps significantly, we must use extra parameter
;; to remember state
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

;; amount a
;; n kinds of coins

;; 1) the number of ways to make change without using any of the
;; first kind of coin
;; 
;; 2) the number of ways to make change assuming that we do use the
;; first kind of coin

;; actually, we just need to get a formula to recursive

(define (count-change amount)
  (cc amount 5)
  )

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ 
               (cc amount (- kinds-of-coins 1))
               (cc (- amount (first-denomination kinds-of-coins)) 
                   kinds-of-coins)
               )
              )
        )
  )

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)
        )
  )

;; todo linear iteration version

;; 1.11
;; recursive process
(define (f n)
  (if (< n 3) 
      n 
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3)))
         )
      )
  )

;; linear iteration
;; oh, in iteration, we must know which states are changed, and
;; save, update them.
(define (f n)
  (f-iter 2 1 0 n)
  )

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

;; Pascal's triangle recursive solution
(define (pascal n)
  (if (= n 1)
      1
      (+ n (pascal (- n 1)))
      )
  )