练习

---

换零钱方式统计

例：

将1美元换成 半美元，四分之一美元，十美分，五美分，一美分

> (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)))                 
        
        
        
> (define (count-change amount)
      (cc amount 5))
      
      
> (count-change 100)
292

---

函数f由 n<3 : f(n) = n; f >= 3：f(n)=f(n-1) + 2f(n-2) + 3f(n-3)

递归版：

> (define (f n)
          (cond ((< n 3) n)
              (else (+ (f (- n 1)) 
                      (* 2 (f (- n 2)))
                      (* 3 (f (- n 3)))))))
> (f 3)
4
> (f 4)
11
> (f 5)
25
> (f 1)
1
> (f 2)
2
> (f 8)
335

迭代版：

> (define (fun f s l a n)
      (cond
        ((= a n) f)
       (else (fun s l (+ l (* 2 s) (* 3 f)) (+ a 1) n))))
> (define (f n)
    (fun 0 1 2 0 n))  
> (fun 1)
1
> (fun 2)
2
> (fun 3)
4
> (fun 4)
11
> (fun 5)
25
> (fun 8)
335

升级版

> (define (fun f s l n)
        (cond
          ((= n 0) f)
         (else (fun s l (+ l (* 2 s) (* 3 f)) (- n 1)))))
> (define (f n)
    (fun 0 1 2 n))
> (fun 8)
335
> (fun 5)
25
> (fun 4)
11

有漏洞:
不能为负数

> (define (fun f s l n)
        (cond
            ((< n 0) n)
          ((= n 0) f)
         (else (fun s l (+ l (* 2 s) (* 3 f)) (- n 1)))))
> (define (f n)
    (fun 0 1 2 n))
> (fun 8)
335
> (fun 5)
25
> (fun 4)
11

这个例子说明了迭代比递归效率高 ，计算迭代（fun 100000）的时间和计算递归（f 35）的差不多

---

求幕 运算

递归版：

> (define (fun b n)
    (if (= n 0) 
        1
        (* b (fun b (- n 1)))))
> (fun 2 3)
8
> (fun 2 4)
16
> (fun 2 5)
32
> (fun 5 5)
3125
> (fun 2 10)
1024

迭代版：

> (define (f b r n)
      (if (= n 0)
          r
          (f b (* r b) (- n 1))))
> (define (fun1 b n)
    (f b 1 n))
    
> (fun1 2 10)
1024
> (fun1 2 5)
32