スキップしてメイン コンテンツに移動

投稿

5月, 2009の投稿を表示しています

Project Euler - Problem 31

問題原文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) = 1cc(n, 1) = 1cc(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]; }…

Project Euler - Problem 30

問題原文Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.日本語訳各桁を5乗した和が元の数と一致するような数の総和を求めよ.解答まず探索範囲の上限を定める必要があります。n桁の最大の整数an = 9n-19n-2...90を考えると、その各桁の5乗の和はbn = 95nと表せます。an+1 = 10an + 9bn+1 = bn + 95ですから、桁数nが大きくなるにつれてaがbよりも急激に大きくなるのが分かります。ある桁数nmaxを超えると、常にanmax > bnmaxが成立するので、両者が等しくなることはなくなります。 実際に調べるとnmaxは6なので、探索範囲は高々0から999,999までとなります。各桁の乗数の和は、桁の並びに関わらず各桁の数のみによって決まります。例えば2501、5012、(0)215のいずれも同じbnを持つので、これを別々に計算するのは時間の無駄です。 そこで、このような数をすべて同値と見なす正規化を考えます。手っ取り早く桁の並べ替えで良いでしょう。各桁を昇順に並べ替え、その上で先頭に1個以上0があったら取り除くという処理です。先ほどの例に挙げた数字をこの方法で正規化すると、いずれも125となります。この正規化された数のみを走査すれば良いわけですから、(0を含まない)n桁の数1つにつき同じ値をn!通り計算していたところが、1通りで済むことになります。処理の手順をまとめると次のようになります:全ての正規化された数に対してbnを計算し、連想配列に格納しておく。連想配列に格納された値を1つ取り出し、anとする。anを正規化して連想配列から対応するbnを引く。an = bnであれば解に加える。連想配列の値を全て走査するまで2.に戻って繰り返す。下記のコードでは初期化の都合上、桁数ごとに連想配列を分けていますがアルゴリズム自体に違いはありません。#!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub regularize($) { join ''…

Project Euler - Problem 29

こんばんはSekia the Liarです。更新頻度についての釈明はさておきえーとP.E. 29でしたね。はい、すいません。問題原文Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: (引用者による省略) How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?日本語訳2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, abを全て考えてみよう: (引用者による省略) 2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?解答値の重複を取り除くにはハッシュを使うのが定石です。use strict; use warnings; use feature qw/say/; use Math::BigInt; my %pows; for my $n (2 .. 100) { for my $i (2 .. 100) { $pows{ Math::BigInt->new($n) ** $i } = 1; } } say scalar keys %pows; しかしPerlのメソッド解決オーバヘッドは結構でかいので、10,000個のMath::BigIntインスタンス生成は割と時間を食います。毎回Math::BigIntというのも芸がないし、少し頭を使って解いてみることにしました。ab = (an)b/nであることに着目しましょう。これは中学だか高校だかで習った通りです。ただし問題の範囲は整数なので、指数は2 ≤ b/n ≤ 100なる整数でなければなりません。つまりnはbの約数(ただしb自身を除く)です。この等号で結ばれたべき乗は同じ(つまり重複した)値を持ちます。例えば212 = 4(=22)6 = 8(=23)4 = 16(=24)3 = 64(=26)2 = 4,096であり、他に4,096となるようなべき乗は整数の範囲ではなさそうです(証明してないので間違ってたら教えてください)。これをふまえると、等式が成り立つa、bの組のうちaが最小のもの(ここでa0、b0とおき…