首页 > 代码库 > SICP_3.27

SICP_3.27

 1 (define false #f)
 2 (define true #t)
 3 
 4 (define (make-table)
 5   (let ((local-table (list *table*)))
 6 
 7      (define (assoc key records)
 8       (cond ((null? records) false)
 9             ((equal? (caar records) key) (car records))
10             (else (assoc key (cdr records)))))
11 
12     (define (lookup keys)
13       (define (lookup-helper keys table)
14         (let ((subtable (assoc (car keys) (cdr table))))
15           (if subtable
16               (if (null? (cdr keys))
17                   (cdr subtable)
18                   (lookup-helper (cdr keys) subtable))
19               false)))
20       (lookup-helper keys local-table))
21 
22     (define (insert! keys value)
23       (define (insert-helper! keys table)
24         (if (null? table)
25             (if (null? (cdr keys))
26                 (cons (car keys) value)
27                 (list (car keys) (insert-helper! (cdr keys) ())))
28             (let ((sub (assoc (car keys) (cdr table))))
29               (if sub
30                   (if (null? (cdr keys))
31                       (set-cdr! sub value)
32                       (insert-helper! (cdr keys) sub))
33                   (if (null? (cdr keys))
34                       (set-cdr! table (cons (cons (car keys) value) (cdr table)))
35                       (set-cdr! table (cons
36                                        (list (car keys)(insert-helper! (cdr keys) ()))
37                                        ;;可以直接用(insert-helper! keys ())
38                                        (cdr table))))))))
39       (insert-helper! keys local-table)
40       ok)
41   
42     (define (dispatch m)
43       (cond ((eq? m lookup-proc) lookup)
44             ((eq? m insert-proc) insert!)
45             (else (error "Unknow operation --TABLE" m))))
46 
47     dispatch))
48 
49 (define (lookup x table)
50   (let ((keys (list x)))
51     ((table lookup-proc) keys)))
52 
53 (define (insert! x result table)
54   (let ((keys (list x)))
55     ((table insert-proc) keys result)))
56 
57 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
58 
59 (define (memoize f)
60   (let ((table (make-table)))
61     (lambda (x)
62       (let ((previously-computed-result (lookup x table)))
63         (or previously-computed-result
64             (let ((result (f x)))
65               (insert! x result table)
66               result))))))
67 
68 
69 (define memo-fib
70   (memoize (lambda (n)
71              (cond ((= n 0) 0)
72                    ((= n 1) 1)
73                    (else (+ (memo-fib (- n 1))
74                             (memo-fib (- n 2))))))))
75 
76 
77 (memo-fib 0)

 

简单的定义为

(memoize fib)

能工作,但这样并没有意义,因为这样定义在处理 fib(n-2)和fib(n-1)时就是普通fib函数了

 

步数:

在计算fib(n)时 需要fib(n-1)和fib(n-2)而fib(n-1)的值需要fib(n-2)的值,如使用记忆法,则fib(n-2),fib(n-3)已事先存在表中。所以事先

要计算fib(n-2),一直到达n=0 和 n=1时整个表都被填满,总的来看就是求一遍fib(2)到fib(n-1)所以需要O(n)步来计算fib(n)。

SICP_3.27