《计算机编程的构造和解释》学习记录

Ackermann.ss

; 1.2
; http://en.wikipedia.org/wiki/Ackermann_function
; TODO 了解

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

(display (A 1 10)) (newline)
(display (A 2 4)) (newline)
(display (A 3 3)) (newline)


(define (f n) (A 0 n)) ; (define (double y) (* 2 y))
(define (g n) (A 1 n)) ; proc {|n| 2 ** n } 而不是(define (eight y) (* 8 y))
(define (h n) (A 2 n)) ; 指数形式

fast-expt.ss

; 1.2.4
; 求任意树乘幂，并优化复杂度为Math.log2(n)

(define (square x)
  (* x x))
(define (even? n)
  (= (remainder n 2) 0))
(define (fast-exprt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-exprt b (/ n 2))))
        (else (* b (fast-exprt b (- n 1))))))

(display (fast-exprt 2 50)) (newline)
(display (fast-exprt 2 51)) (newline)

sqrt-iter.ss

; 1.2
; 求平方根

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

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.000000001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
        x)))
  (display (sqrt-iter 1.0 x)) (newline))


(sqrt 9)
; 3.000091554