0

私は SICP を介した関数型プログラミングを調査しているだけで、演習 2.19 を拡張してより便利なことを行う方法を考えています (これには副作用が必要なようです)。

この演習には、与えられた硬貨の種類のリストを使用して、与えられた金額 (ペニー単位) を変更できる方法の数を数えるプログラムが含まれます。解決策は非常に簡単です (cc は「count-change」の略です):

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (first-denomination coinTypes) (car coinTypes))
(define (except-first-denomination coinTypes) (cdr coinTypes))
(define (no-more? coinTypes) (null? coinTypes))

関連する SICP セクションはこちらで確認できます。上記が明確でない場合は、アルゴリズムの説明にリンクしています。

最初に、コインの実際の組み合わせがどのような変更方法を構成するかを確認したかったので、各ソリューションをリストとして出力する独自のバージョンを作成しました。

(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
                    (display (reverse currChangeList)) 
                    (newline) 
                    1)
              ((or (negative? amount) (null? coinTypes)) 
                    0)
              (else (+ (cc amount (cdr coinTypes) currChangeList)
                       (cc (- amount (car coinTypes)) coinTypes (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes ()))

だからここで私は立ち往生しています:私は自分のメソッドを変更して、整数の結果=変更する方法の数を返すのではなく、計算中に各方法を単純に出力するのではなく、ソリューションのリストを返すようにしたいと考えています(リストの長さ = 変更する方法の数)。しかし、私はこれを実現する方法に途方に暮れています。命令型/オブジェクト指向言語で行うのは簡単ですが、機能的に行う方法がわかりません。

これを達成する方法を知っている人はいますか？経験豊富な関数型コーダーにとっては、かなり簡単なことのように思えます.. 私の好奇心を満たすのを手伝ってください。

ありがとう

4

1 に答える 1

0 
(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
               (list (reverse currChangeList)))
              ((or (negative? amount) (null? coinTypes)) 
               '())
              (else
                (append
                   (cc amount (cdr coinTypes) currChangeList)
                   (cc (- amount (car coinTypes))
                       coinTypes
                       (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes '()))
于 2013-01-30T09:02:59.767 に答える