2

単純なフィボナッチ関数を拡張しようとしていますが、各項の値を複数回使用する必要があります。だから、私letは値を保持するために使用すると思いました。しかし、私は私が機能から外すべきだと思うものを手に入れていません。

元のfib関数は次のとおりです。

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

これが同じことをする私の試みですが、let：

(define (fib-with-let n)
  (if (< n 2)
      0
      (let ((f1 (fib-with-let (- n 1)))
            (f2 (fib-with-let (- n 2))))
        (+ f1 f2))))

結果：

> (fib 10)
55
> (fib-with-let 10)
0

ありがとう！

4

4 に答える 4

7

タイプミスをしました：

(if (< n 2)
    0
    ...)

つまりn。

于 2011-06-16T18:51:22.353 に答える
6

ベースケースのタイプを間違えました。あなたが持っていた最初のバージョンでは：

(if (< n 2)
      n

しかし、後者のバージョンでは、次のように書いています。

(if (< n 2)
      0

したがって、に変更0してnください。

于 2011-06-16T18:52:58.777 に答える
2

あなたのレットは実際には何もしていません。あなたはまだすべての余分な計算を行っています。f1として定義したからといっ(fib-with-let (- n 1))て、n-1のfibを再度計算しないという意味ではありません。を使用f2しませんf1。見たい場合はf2を使用します。しかし、これでも本当にあなたが望むものではありません。 f1let*

これの証拠として、ここに実行時間for fib(35)とfib-with-let(35)：があります。

(time (fib 35))
cpu time: 6824 real time: 6880 gc time: 0
(time (fib-with-let 35))
cpu time: 6779 real time: 6862 gc time: 0

余分な計算を避けるために本当にやりたいことは、動的計画法を使用し、ボトムアップ方式で再帰することです。

必要なのは次のコードです。

(define (dynprog-fib n)
  (if (< n 2)
      n
      (dynprog-fib-helper 1 1 2 n)))

(define (dynprog-fib-helper n1 n2 current target)
  (if (= current target)
      n2
      (dynprog-fib-helper n2 (+ n1 n2) (add1 current) target)))

(time (dynprog-fib 35))
cpu time: 0 real time: 0 gc time: 0
(time (dynprog-fib 150000))
cpu time: 2336 real time: 2471 gc time: 644

ご覧のとおり、ナイーブなアプローチにかかる時間の3分の1で、最初の150,000フィブを実行できます。

あなたは何が私にもっとよく説明させてくれるのかについて混乱しているように見えるので：

あなたが言う時：

(let ((a 1)
      (b 2))
  (+ a b))

あなたが言っているのは、aを1、bを2とし、それらを足し合わせることです。代わりに言った場合：

(let ((a 1)
      (b (+ a 1))
  (+ a b))

あなたはあなたが何を得るかを推測できますか？3ではありません。expand: unbound identifier in module in: a

簡単letに言えば、あなたの割り当てはお互いを見ることができません。上記を書きたい場合は、以下を使用する必要がありますlet*。

(let* ((a 1)
      (b (+ a 1))
  (+ a b))

それはあなたにあなたが期待する3を与えるでしょう。let*基本的に次のように拡張されます。

(let ((a 1))
     (let ((b (+ a 1)))
          (+ a b)))

あなたがレットでやっていたと思ったことは、メモ化と呼ばれます。これは、中間値を保存して、それらを繰り返す必要がないようにする手法です。しかし、あなたのためにそれをしないようにしましょう。

于 2011-06-23T04:47:12.697 に答える
0

問題はfib-with-let関数のタイプミスですが、最も単純な形式でletは、匿名ラムダの「シンタティックシュガー」とそれに続く引数が評価されてランバに渡され、評価されて最終値が返されます。それで

(let ((f1 (fib-with-let (- n 1)))
      (f2 (fib-with-let (- n 2))))
        (+ f1 f2))

letのように見えることなく書き直されます

((lambda (f1 f2) (+ f1 f2))(fib-with-let (- n 1))(fib-with-let (- n 2)))
于 2011-06-17T19:53:15.263 に答える