Problem31

30分プログラム、その304。Problem31 via ProjectEuler。

イギリスでは硬貨はポンド£とペンスpがあり，一般的な流通ではこれらの8つの硬貨がある．
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?

よくある両替の問題をちょっと変形させるだけで解ける。Perlでリストを扱うのは面倒なので、組み合せを実際に計算するのではなく、組み合せの数だけを数えるようにした。あと、Perlでちょっと再帰を書くとすぐにDeep recursionの警告がでるのはうざい。

使い方

$ time perl problem31.pl
73682
perl problem31.pl  0.68s user 0.02s system 86% cpu 0.812 total

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# problem31.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/05/14 22:44:04
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
use strict;
use warnings;
no warnings "recursion";

sub make_of($@){
    my ($target,@coins) = @_;
    my ($x,@xs) = @coins;

    # 金額が0 -> 成功
    return 1 if($target == 0);

    # コインが1枚の場合 -> 割り切れるなら使える
    return ($target % $x) == 0 if(@xs == 0);

    if($target < $x){
	# 目的の金額 < コインの額面
	#   -> このコインは使えない
	&make_of($target,@xs);
    }else{
	# コインを使う場合 + コインを使わない場合
	&make_of($target-$x,@coins) + &make_of($target,@xs);
    }
}

my @coins = (200,100,50,20,10,5,2,1);
print make_of(200,@coins),"\n";

参考

• 過去の30分プログラム
• Problem 31 - PukiWiki