几个简单编程问题

牛顿法求平方根

如果对x的平方根有一个估计值y，则可以通过求y和x/y的平均值可以得到一个更好的猜测。

(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 (- (square guess) x)) 0.001))

(define (square x) (* x x))

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

(sqrt 10)

求立方根

(define (cubrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (cubrt-iter (improve guess x)
             x)))

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (square x) (* x x))

(define (cubic x) (* x (square x)))

(define (good-enough? guess x)
  (< (abs (- (cubic guess) x)) 0.0001))

(define (cubrt x)
  (cubrt-iter 1.0 x))

(cubrt 10)

阶乘

线性递归的计算过程

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 5)

线性迭代的计算过程，

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

(factorial 5)

在迭代的情况中，在计算的任何一点，上面的三个变量都提供了有关计算状态的一个完整描述。而递归则需要维持一个更多更长的信息。

树形递归之fib

;递归
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

;迭代
(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))))

换零钱问题

将金钱数a换成n中不同类型币值的任意组合有多少种组合方式。
使用一种递归的方法可以很容易地表示这个问题，首先将币种进行从大到小排序，然后将问题分为两种情况。

（1）将全部钱a换成除了第一种币值以外的钱
（2）将钱a-d换成所有币值的组合，其中d为第一种币值。

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

(count-change 100)