問題
-
How many different ways can £2 be made using any number of coins?
-
いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?
解答
ポンドとペンスを別々に扱うのは面倒と無駄以外の何者でもないので、単位をペンスに統一します。よって問題は合計が200ペンスとなるコインの組み合わせは何通りあるかです。
コインを昇順にCi(i = 0, 1, 2, ..., 7)と番号づけることにします。 合計nペンスとなるCk以下のコインを使った組み合わせをcc(n, k)と表すと、次のようになります:
- cc(0, k) = 1
- cc(n, 1) = 1
- cc(n, k) = Σ(cc(n - iCk, k - 1))、ただしi ∈ { 0 , 1, 2, ..., floor(n / Ck) }
副問題は同じものが何度も出てくるのでメモ化しています。
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw/say state/;
use List::Util qw/sum/;
sub coin_comb($;$);
{
my @coins = (1, 2, 5, 10, 20, 50, 100, 200);
sub coin_comb($;$) {
state %memos;
my ($currency, $coin_idx) = @_;
$coin_idx //= $#coins;
return $memos{$currency, $coin_idx} if exists $memos{$currency, $coin_idx};
return 1 if $currency == 0;
return 1 if $coin_idx == 0;
use integer;
$memos{$currency, $coin_idx} = sum map {
coin_comb($currency - $coins[$coin_idx] * $_, $coin_idx - 1);
} 0 .. $currency / $coins[$coin_idx];
}
}
say coin_comb 200;
コメント
コメントを投稿