コインで支払う組み合わせ
引用： Mixi 「Ocaml使い」コミュニティ， 「OCamlで頭の体操」トピックより
n円のお金を日本のコインで支払う組み合わせは何通りあるか計算する関数を作成せよ．例：
n = 5 の場合は，(5円コイン1枚，1円コイン5枚）の2通り
n = 15 の場合は，次の6通り：
1) 10円コイン1枚 + 5円コイン1枚
2) 10円コイン1枚 + 1円コイン5枚
3) 5円コイン3枚
4) 5円コイン2枚 + 1円コイン5枚
5) 5円コイン1枚 + 1円コイン10枚
6) 10円コイン15枚
その他，例えばn = 24の場合は答えは9になるはず．
Prolog なので組み合わせを見つける述語を作って，何通りあるかは処理系におまかせしよう．
とりあえず bounds は読んでおこう．
?- use_module(library(bounds)).
N 円を分割する述語 divide を定義します．
% divide(N, L) ： N 円をコインで分割すると L のように分けられる
divide(0, []).
divide(N, [M|MoneyList]) :-
Coins = [1, 5, 10, 50, 100, 500],
member(M, Coins),
N - M #>= 0,
R is N - M,
divide(R, MoneyList),
ascending([M|MoneyList]),
label(MoneyList).
ascending(L) は L が昇順であることを表す述語です．
もしかして標準であるかも．
ともかく，これが無いと，同じ組み合わせで順番が違うものが出てしまい，冗長になってしまいます．
ascending([]).
ascending([_]).
ascending([A|[B|L]]) :-
A #=< B,
ascending([B|L]).
うーん．まだ文法とか不安だ...
動かした感じでは合ってるっぽいのでいいか．(いいかげん)．
実行．
たしかに9個出た．あってるかな?
?- divide(24, X).X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
X = [1, 1, 1, 1, 5, 5, 5, 5] ;
X = [1, 1, 1, 1, 5, 5, 10] ;
X = [1, 1, 1, 1, 10, 10] ;
No
?-
