S を正の数の有限集合としましょう。 解決したい問題とは、与えられた整数 x を、S から選択した正の数の倍数の和として表現する、異なる方法の数を見つけることです。 S 中のそれぞれの数をコインの額面に見立てると、 この問題は、与えられた値 x をコインの集合の和で表わす異なる方法がいくつあるか調べることになります。 この数を cc(S, x) で表わすと、関数 cc は次の特性を持ちます:
どのような S に対しても cc(S, 0) = 1
どのような S に対しても、もし x < 0 ならば cc(S, x) = 0
S が空で x > 0 ならば cc(S, x) = 0
S が数 c を含むならば、S1 が S から c を削除した集合の時 cc(S, x) = cc(S1, x) + cc(S, x-c)
// typedef int4 = (int, int, int, int) // val theCoins = (1, 5, 10, 25): int4 // fun coin_get (n: int): int = ( if n = 0 then theCoins.0 else if n = 1 then theCoins.1 else if n = 2 then theCoins.2 else if n = 3 then theCoins.3 else ~1 (* erroneous value *) ) (* end of [coin_get] *) // fun coin_change (sum: int): int = let fun aux (sum: int, n: int): int = if sum > 0 then (if n >= 0 then aux (sum, n-1) + aux (sum-coin_get(n), n) else 0) else (if sum < 0 then 0 else 1) // end of [aux] in aux (sum, 3) end // end of [coin_change] //
この章で紹介したコード全体と追加のテストコードは オンライン から入手できます。