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

初代Masteries

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

Project Euler - Problem 5

Problem 5

最初は総当たりで解こうと思ったのですが, かなり時間がかかってしまうので方針変更.
最終的にはこちらのページを参考に(参考というか, 書いてあったJavaのコードをPerlに書き直して...)実装しました.

use strict;
use warnings;
use bigint;

my $min = 1;

for (2..20) {
    $min = $min * $_ / gcd($min, $_);
}
print $min . "\n";

sub gcd {
    my ($a, $b) = @_;

    return $a if $a == $b;

    if ($a > $b) {
        my $mod = $a % $b;
        if ($mod == 0) {
            return $b;
        } else {
            return gcd($b, $mod);
        }
    } else {
        my $mod = $b % $a;
        if ($mod == 0) {
            return $a;
        } else {
            return gcd($a, $mod);
        }
    }
}

...ちなみにgcdは最大公約数を求める関数です.
後々流用できそうな気がしますね.

追記(2013/1/28)

コメント欄で@さんにアドバイスを頂いたので書きなおしてみました.

use strict;
use warnings;
use bigint;

my $min = 1;

for(2..20) {
    $min = $min * $_ / gcd($min, $_);
}
print $min . "\n";

sub gcd {
    my ($a, $b) = @_;

    return $a if $a == $b;

    my ($big, $small) = ($a, $b);
    if($a < $b) {
        $big = $b;
        $small = $a;
    }

    my $mod = $big % $small;
    if($mod == 0) {
        return $small;
    } else {
        return gcd($small, $mod);
    }
}

スマートになりましたね!

更に追記(2013/1/28)

再びコメント欄で@さんにアドバイスを頂きました!

use strict;
use warnings;
use bigint;

my $min = 1;

for(2..20) {
    $min = $min * $_ / gcd($min, $_);
}
print $min . "\n";

sub gcd {
    my ($l, $r) = @_;

    return $l if $l == $r;

    my ($big, $small) = $l > $r ? ($l, $r) : ($r, $l);

    my $mod = $big % $small;
    if($mod == 0) {
        return $small;
    } else {
        return gcd($small, $mod);
    }
}

当たり前っちゃ当たり前ですが, こうやってリストに対する(?)三項演算子もできるんですね...!
三項演算子ってなんかごちゃごちゃしてる感じがして好きじゃない系男子*1なんですが, これは凄い綺麗だなーと思いました.
ちょっと意識して使ってみようと思います.

あと, perlで変数名として$aや$bは使ってはいけないという話, Perl入学式でもさんざんやったのにすっかり忘れてました...
関数gcdを実装するときに参考にしたコードが変数a, bを使っていたので, ついついそのままにしてたっぽいです.

これを思い出せただけでも, こうやってProject Eulerの問題解いた甲斐があったなーと思います.
@さん, ありがとうございました!

*1:直感的にわかりにくいような気がする...