(sicp37)m3.27
memo化
(define (make-table) (let ((table (cons '*table* '()))) (define (insert! key value) (let ((record (assoc key (cdr table)))) (if record (set-cdr! record value) (set-cdr! table (cons (cons key value) (cdr table)))))) (define (lookup key) (let ((record (assoc key (cdr table)))) (if record (cdr record) #f))) (define (inspect) (print (cdr table))) (define (dispatch m) (cond ((eq? m 'lookup-proc) lookup) ((eq? m 'insert-proc!) insert!) ((eq? m 'inspect-proc) inspect))) dispatch)) (define (lookup key table) ((table 'lookup-proc) key)) (define (insert! key value table) ((table 'insert-proc!) key value)) (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result)))))) (define memo-fib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memo-fib (- n 2)) (memo-fib (- n 1)))))))) (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 2)) (fib (- n 1))))))