乐正

Actions speak louder than words.

Sicp-ex1-11

问题

函数$f$由如下的规则定义:如果$n<3$,那么$f(n) = n$;如果$n\ge 3$,那么$f(n) = f(n-1) + 2f(n-2) + 3f(n-3)$。请写一个采用递归计算过程计算$f$的过程。再写一个采用 迭代计算过程计算$f$的过程。

解答

函数为: $$ f(n) = \begin{cases} n, & \text{if $n<3$} \\ f(n-1) + 2f(n-2) + 3f(n-3), & \text{if $n\ge 3$} \end{cases} $$

练习1.11 (ex1-11.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
; 使用递归计算过程
(define (f n)
  (if (< n 3) n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

; 使用迭代计算过程
(define (f2 n)
  (define (f2-iter x y z count)
    (cond ((< count 2) count)
          ((= count 2) x)
          (else (f2-iter (+ x (* 2 y) (* 3 z)) x y (- count 1)))))
  (f2-iter 2 1 0 n))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(f 1)
;Value: 1

(f 3)
;Value: 4

(f 5)
;Value: 25

(f2 1)
;Value: 1

(f2 3)
;Value: 4

(f2 5)
;Value: 25

draft

« sicp-ex-1-10 sicp-ex1-12 »

Comments