13

そう; 私は SICP を使って作業しようとしている愛好家です (無料です! )。最初の章には、アメリカの硬貨で両替する方法を数えるための手順の例があります。(change-maker 100) => 292. 次のように実装されています。

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

ともかく; これはツリー再帰手順であり、作成者は同じ問題 (つまり、固定スペース) を解決するための反復手順を見つけることを「課題として残します」。私はこれを理解したり、イライラした後に答えを見つけたりすることができませんでした。それは私の側の脳のおならなのか、それとも作者が私をからかっているのか疑問に思っています.

4

5 に答える 5

13

一般に、再帰を排除する最も簡単で最も一般的な方法は、補助スタックを使用することです。再帰呼び出しを行う代わりに、引数をスタックにプッシュして繰り返します。続行するために再帰呼び出しの結果が必要な場合も、一般的なケースでは、「継続要求」をプッシュできる必要があるため、少し複雑になります（これは補助から外れます）。結果がわかっているときにスタックします）; ただし、この場合、すべての再帰呼び出し結果で実行し​​ているのは合計であるため、アキュムレータを保持するだけで十分です。さらに呼び出しを行う必要がなく、数値結果を取得するたびに、それをに追加します。アキュムレータ。

ただし、スタックが大きくなるため、これ自体は固定スペースではありません。もう1つの便利なアイデアは、これは純粋関数（副作用なし）であるため、特定の引数セットの関数の値を計算したことに気付いたときはいつでも、引数と結果の対応をメモすることができます。これにより、呼び出しの数が制限されます。ほぼ同じ計算につながる別の概念的アプローチは動的計画法[[別名DP]]ですが、DPでは、再帰から始めて次のように作業するのではなく、いわば「メモ化する結果の準備」をボトムアップで行うことがよくあります。それを排除します。

たとえば、この関数のボトムアップDPを取り上げます。「最小のコインだけで金額Xを変更する方法はいくつあるか」（元のコインのさまざまな組み合わせでXに切り詰める）が繰り返し発生することを知っているので、これらの値のamount計算を開始します。amount単純な反復（f（X）= X/ valueifXが最小コイン値で正確に割り切れる場合value、それ以外の0場合;ここでvalueは1であるため、すべてのX> 0に対してf（X）= X）。次に、新しい関数g（X）を計算します。これは、2つの最小のコインでXを変更する方法です。ここでも、Xを増やすための単純な反復で、g（x）= f（X）+ g（X- value） thevalue2番目に小さいコインの（g（X）を計算するときまでに、y <Xの場合はf（X）とすべてのg（Y）を計算して保存しているため、単純な反復になります-もちろん、g（X）= 0（すべてのX <= 0）。また、h（X）の場合、 3つの最小のコイン（上記のようにh（X）= g（X）+ g（X- ））を使用してXを変更する方法value。これからは、fは必要ありません。 （X）これ以上、そのスペースを再利用できます。結局のところ、これにはスペースが必要です2 * amount。まだ「固定スペース」ではありませんが、近づいています...

「固定スペース」に最後の飛躍を遂げるには、次のことを自問してください。各ステップで2つの配列（最後に計算した配列と現在計算している配列）のすべての値を維持する必要がありますか、それとも一部の配列のみを保持する必要がありますか。値、ループを少し再配置することによって...？

于 2009-09-28T02:16:42.653 に答える
2

これが、動的計画法を使用した私のバージョンの関数です。サイズ n+1 のベクトルは 0 に初期化されますが、0 番目の項目は最初は 1 です。次に、可能なコイン (外側の do ループ) ごとに、k 番目から始まる各ベクトル要素 (内側の do ループ) 、ここで、k はコインの値であり、現在のインデックスの値から k を引いた値だけインクリメントされます。

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(1 5 10 25 50) 100)
292

このプログラムはhttp://ideone.com/EiOVYで実行できます。

于 2012-04-13T13:07:27.403 に答える
1

私が思いついた解決策は、「財布」で使用している各タイプのコインの数を数えることです

メイン ループは次のように機能します。'denom は現在の金種、'changed は財布の中のコインの合計額、'given は必要な釣り銭の額、'clear-up-to は、指定された金種よりも小さいすべてのコインを財布から取り出します。 .

#lang scheme
(define (sub changed denom)
  (cond
   ((> denom largest-denom)
    combinations)

   ((>= changed given)
    (inc-combinations-if (= changed given))

    (clear-up-to denom)
    (jump-duplicates changed denom)) ;checks that clear-up-to had any effect.

   (else
    (add-to-purse denom)
    (sub
     (purse-value)
     0
     ))))

(define (jump-duplicates changed denom)
  (define (iter peek denom)
    (cond
     ((> (+ denom 1) largest-denom)
      combinations)

     ((= peek changed)
      (begin
        (clear-up-to (+ denom 1))
        (iter (purse-value) (+ denom 1))))

      (else
       (sub peek (+ denom 1)))))
  (iter (purse-value) denom))

Alex Martelliの答えを読んだ後、私は財布のアイデアを思いつきましたが、それを機能させることに取り掛かりました

于 2010-05-02T00:09:26.463 に答える
-2

疑似計画法で動的計画法を使用して反復的に解くことができます。

于 2010-04-29T21:43:44.030 に答える