読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 33

Problem 33

'49/98'のような, 分子と分母に共通する数字(この場合, 9)を取り除いた時に, 取り除く前の数字と取り除いた後の数字が一致する(49/48 = 4/8)分数を探す問題です.
ただし,

  1. 分数は1より小さい.
  2. 分子・分母ともに2桁の数.
  3. '30/50'のような, 明白なものは除く.

...という条件があって, この条件を満たす分数は4個あるらしく, それらの分数の積を約分した時の分母が答えになる, という問題です.

use strict;
use warnings;
use Math::BigRat;

my $answer = Math::BigRat->new(1);

for my $denominator (11..99) {
    for my $numerator (10..$denominator - 1) {
        next if $denominator % 10 == 0;
        if (my $same = has_same($denominator, $numerator)) {
            for my $s (keys %{$same}) {
                (my $n = $numerator) =~ s/$s//;
                (my $d = $denominator) =~ s/$s//;
                next if $d == 0;
                if ($n / $d == $numerator / $denominator) {
                    $answer->bmul("$n/$d");
                }
            }
        }
    }
}
print $answer->bstr . "\n";

sub has_same {
    my ($denom, $numer) = @_;

    my @denoms = split //, $denom;
    my @numers = split //, $numer;
    my $same = {};

    for my $d (@denoms) {
        for my $n (@numers) {
            $same->{$d} = 1 if $d == $n;
        }
    }
    return scalar keys $same ? $same : 0;
}

「結果は出たけど分数の約分とか面倒そう...」と思っていたら, Math::BigRatというモジュールが存在するらしく, これを使うと演算を分数として行えるようです.
Math::BigIntに対する'use bigint;'のように, 'use bigrat;'として使うこともできるようですが, 今回は答えを格納する'$answer'にのみ適用するようにしてみました.