3

SICPの1.11を実行するための私の解決策は次のとおりです。

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

さすがに（f 100）のような評価には時間がかかります。このコードを（再帰を先にせずに）改善したり、マルチコアボックスを利用したりする方法があるかどうか疑問に思いました。私は「mit-scheme」を使用しています。

4

6 に答える 6

8

この演習では、2つの関数を作成するように指示します。1つはf「再帰的プロセスによって」計算し、もう1つはf「反復プロセスによって」計算します。あなたは再帰的なものをしました。この関数はfib、リンクしたセクションの例で示した関数と非常に似ているため、関数の再帰的で反復的な例を見ると、これを理解できるはずですfib。

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

この場合、引数だけでなく、、、および引数をf-iter取る関数を定義します。abccount

これがf-iter関数です。との類似性に注意してくださいfib-iter：

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

そして、少し試行錯誤した結果、、、、はそれぞれ、、、に初期化する必要があることがわかりました。aこれもb、c関数の初期化とtoと。のパターンに従います。したがって、次のようになります。210fibab10f

(define (f n)
  (f-iter 2 1 0 n))

注：これf-iterは再帰関数ですが、Schemeの動作方法により、再帰関数であるだけでなく再帰プロセスであるコードとは異なり、反復プロセスO(n)として実行され、時間と空間で実行されます。O(1)これが演習1.1の作者が探していたものだと思います。

于 2009-04-21T04:24:23.630 に答える
4

スキームでコーディングするのに最適な方法はわかりませんが、このようなもので速度を向上させるための一般的な手法は、メモ化を使用することです。簡単に言うと、f（p）の結果（おそらく、表示されるすべてのp、または最後のn個の値）をキャッシュして、次にf（p）を呼び出すときに、保存された結果が返されるようにすることです。再計算されました。一般に、キャッシュはタプル（入力引数を表す）から戻り型へのマップになります。

于 2009-04-21T04:22:34.930 に答える
2

さて、あなたが私に尋ねるなら、数学者のように考えてください。スキームを読み取ることはできませんが、フィボナッチ関数をコーディングしている場合は、再帰的に定義するのではなく、漸化式を解いて閉じた形式で定義してください。フィボナッチ数列の場合、たとえば、閉じた形はここにあります。それははるかに速くなります。

編集：おっと、あなたが再帰を取り除くのをやめると言ったことを見ませんでした。その場合、オプションははるかに制限されます。

于 2009-04-21T04:46:23.297 に答える
1

関数型プログラミングを使用した高速フィボナッチ関数の開発に関する優れたチュートリアルについては、この記事を参照してください。Common LISPを使用しますが、これはいくつかの点でSchemeとは少し異なりますが、それでうまくいくはずです。実装はbogo-fig、ファイルの先頭近くにある関数と同等です。

于 2009-04-21T04:24:12.820 に答える
0

その特定の演習は、末尾再帰を使用して解決できます-再帰呼び出しが戻るのを待つ代わりに（提示する単純なソリューションの場合のように）、再帰が動作するように、パラメーターに回答を蓄積できます。消費するスペースの点では、反復とまったく同じです。例えば：

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))
于 2011-11-14T21:03:27.910 に答える
0

別の言い方をすれば：

末尾再帰を取得するには、再帰呼び出しがプロシージャが実行する最後の処理である必要があります。

再帰呼び出しは*および+式に埋め込まれているため、末尾呼び出しではありません（*および+は再帰呼び出しの後に評価されるため）。

Jeremy Rutenのバージョンはf-iter、反復ではなく末尾再帰です（つまり、再帰的な手順のように見えますが、反復的な同等の手順と同じくらい効率的です）。

ただし、反復を明示的にすることができます。

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

また

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))
于 2009-04-22T08:47:12.943 に答える