04/06/10 12:07
>>576 ありがとうございます。
URLﾘﾝｸ(mitpress.mit.edu) と
URLﾘﾝｸ(www.geocities.co.jp)
を参考にして、以下のコードを書いてみました。
(define (memoize proc)
(let ((cache '()))
(lambda args
(let ((hit (assoc args cache)))
(if hit (cdr hit)
(let ((result (apply proc args)))
(set! cache (cons (cons args result) cache))
result))))))
(define memo-fib
(memoize (lambda (n)
(if (< n 2)
1
(+ (memo-fib (- n 1))
(memo-fib (- n 2)))))))
大変うまくいきました。コードはほぼ定義どおりで、しかも (memo-fib 10000)でも
即時に演算が終わるようになりました。memoize って素晴らしいです。
数年前、Java で数値計算をしていて、再帰で書いたら同じ問題に遭遇して、仕方なく
ループで書き直したことがあります。あのときに memoize を知っていたらなあ。
URLﾘﾝｸ(mitpress.mit.edu)
は私には難しいので、時間をかけて考えてみます。
ということで皆さま、いろいろありがとうございました。