PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 31 / 硬貨の和

イギリスでは硬貨はポンド£とペンス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を作る方法は何通りあるか?

Problem 31 - Project Euler

整数の分割

要するに 1, 2, 5, 10, 20, 50, 100, 200 を使って200を作る問題です。整数を分割する問題は前にもやりました。IntegerPartitions を使います。

IntegerPartitions[a, b, list] とすれば list に含まれる数を最大 b 個使って a を表す方法が返ってきます。その個数を求めれば終わり。

べき級数を使う

べき級数を使う方法もあります。昔,『組合せ論入門』(G.ポリア,近代科学社)で読みました。たとえば1, 2, 5を使って10を作る方法は

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^5+x^10+...)

を展開したときの x^10 の係数と同じ数だけあります。級数を整理して

1/(1-x)(1-x^2)(1-x^5)

これの10次の係数を求めればいいわけです。ポリアの本には手計算による現実的な方法が書いてありましたが,いまは Mathematica にやってもらいます。IntegerPartitions よりもこちらの方が速いです。


組合せ論入門

組合せ論入門

  • 作者: ジョージポリア,ドナルド・R.ウッズ,ロバート・E.タージャン,今宮淳美
  • 出版社/メーカー: 近代科学社
  • 発売日: 1986/09/01
  • メディア: 単行本
  • 購入: 1人 クリック: 7回
  • この商品を含むブログ (11件) を見る