金額と枚数を指定した両替

Scheme 30分プログラム

30分プログラム、その617。金額と枚数を指定した両替（本当に分からないので教えてください４ - C・C++・C# 締切済み| 【OKWAVE】）をやってみよう。

金額と枚数を入力する．
硬貨，紙幣の合計が入力金額，合計枚数が入力枚数になる場合を1つ見つけるプログラムを作成せよ．
使える硬貨，紙幣は一万円，五千円，千円，五百円，百円，五十円，十円，五円，一円とする．
また，各硬貨，紙幣の枚数が求められたら，合計枚数と合計金額が間違いないか確かめを行うプログラムを追加し，結果を表示せよ．

＜実行結果＞
金額:1234
枚数:999
10000 : 0
5000 : 0
1000 : 0
500 : 0
100 : 0
50 : 0
10 : 0
5 : 55
1 : 944

金額 : 1219
枚数 : 999

とりあえずやってみたけど、なかなか難しい。動作はするんだけど、遅くて999枚だと計算が終わらない。

使い方

gosh> (exchange 4 1055 *coins*)
(((500 . 2) (50 . 1) (5 . 1)))

ソースコード

(define *coins* '(10000
		  5000
		  1000
		  500
		  100
		  50
		  10
		  5
		  1))

(define (add value xs)
  (cond
   [(null? xs) (list (cons value 1))]
   [(eq? value (caar xs))
    (cons (cons value
		(+ 1 (cdar xs)))
	  (cdr xs))]
   [else
    (cons (cons value 1) xs)]))

(define (exchange n amount coins)
  (cond
   [(and (= n 0)
	 (= amount 0)) '(())]
   [(or (= n 0)
	(= amount 0)
	(null? coins)) '()]
   [else
    (append (map (cute add (car coins) <>)
		 (exchange (- n 1) (- amount (car coins)) coins))
	    (exchange n amount (cdr coins)))]))

;; (exchange 4 1055 *coins*)

参考