Project Euler 問題33

pe_33.pl

#!/usr/bin/perl

use strict;
use warnings;

#約分してない答えの分数を作成する
my @fractions = ();
foreach my $i (1..8)
{
  foreach my $j (($i+1)..9)
  {
    push(@fractions, [$i, $j]);
  }
}

#2桁の1未満の分数を作成＆条件評価
my $ans = [1, 1];
foreach my $fra (@fractions)
{
  foreach my $d (1..9)
  {
    foreach (grep {$_->[0] < $_->[1]} (
      ["$fra->[0]$d", "$fra->[1]$d"],
      ["$fra->[0]$d", "$d$fra->[1]"],
      ["$d$fra->[0]", "$fra->[1]$d"],
      ["$d$fra->[0]", "$d$fra->[1]"],
    ))
    {
      is_equal($_, $fra) and $ans = arr_mul($ans, $fra);
    }
  }
}
print "Ans: $ans->[1]\n";
exit(1);

#
# 分数同士の掛け算
#
sub arr_mul
{
  my $a1 = reduce(shift);
  my $a2 = reduce(shift);

  $a1->[0] *= $a2->[0];
  $a1->[1] *= $a2->[1];

  return(reduce($a1));
}

#
# 分数(n,d)どうしが等しいかどうか
#
sub is_equal
{
  my $a1 = reduce(shift);
  my $a2 = reduce(shift);

  if($a1->[0] == $a2->[0] && $a1->[1] == $a2->[1])
  {
    return 1;
  }
  return 0;
}

#
# 約分する
#
sub reduce
{
  my $fra = shift;

  #分母、分子をそれぞれ素因数分解する
  my %numerator = get_primes($fra->[0]);    #分子
  my %denominator = get_primes($fra->[1]);  #分母

  foreach my $k (keys %numerator)
  {
    if(exists($denominator{$k}))
    {
      if($numerator{$k} > $denominator{$k})
      {
        $numerator{$k} -= $denominator{$k};
        $denominator{$k} = 0;
      }
      else
      {
        $denominator{$k} -= $numerator{$k};
        $numerator{$k} = 0;
      }
    }
  }

  my ($n, $d) = (1, 1);
  map { $n *= $_**$numerator{$_} } keys %numerator;
  map { $d *= $_**$denominator{$_} } keys %denominator;

  return [$n, $d];
}

#
# 素因数分解
#
sub get_primes
{
  my $src = shift;
  my %arr = ();

  for (my $div = 2; $div <= ($src/2); $div++)
  {
    if ($src % $div == 0)
    {
      $arr{$div}++;
      $src /= $div;
      redo;
    }
  }
  if ($src > 1)
  {
    $arr{$src}++;
  }
  return (%arr);  #例）156 = 2^2*3^1*13^1 = (2=>2,3=>1,13=>1)
}

# Ans: 100

＜Project Euler 33＞

分母分子から同じ数字を取り除く

＜自明でない＞
49/98 => 分母分子から『9』を取り除く => 4/8 => 約分（素因数分解）=> 1/2
49/98 => 約分（素因数分解）=> (7^2)/(2*7^2) = 1/2

＜自明である＞
30/50 => 分母分子から『0』を取り除く => 3/5
30/50 => 約分（素因数分解）=> (2_3_5)/(2*5^2) = 3/5
※0は使わない

＜約分できる分数とは？＞
　分母分子それぞれが素数同士の2項以上の掛け算で構成

＜ある数（49/98）を約分するには＞
(7^2)/(2*7^2) = 1/2
[49, 98]
　=> 素因数分解して素数にバラす => [[(1,)7,7], [[2,7,7]]
　=> 分母と分子で同じ数字を削除 => [1, 2]
　=> grepでもできそうな気がする