Subscribed unsubscribe Subscribe Subscribe

最大公約数ワンライナー

お題:自然数で与えられる引数の、最大公約数を出力する。

CPANモジュールを使用する

Acme::Toolsにgcd関数が入っている。

$ perl -MAcme::Tools -le'print gcd@ARGV' 111 185
37


Math::Numbersモジュールだとnewに突っ込む形になる。

$ perl -MMath::Numbers -le'print Math::Numbers->new(@ARGV)->gcd' 111 185
37


他にも色々なモジュールに入ってそう。実装はだいたいユークリッド互除法っぽい。

ユークリッド互除法を自分で書く

  • 大きい方を小さい方で割った余りを使う
  • 再帰的に処理
  • どちらかが0になれば終了

だから、こんなカンジ?

$ perl -le'sub f{($a,$b)=@_;$a>$b?$b?f($a%$b,$b):$a:f($b,$a)}print f@ARGV' 111 185
37


ていうかどちらが大きいかなんて調べなくても毎回順番を逆にすればいいだけか。

$ perl -le'sub f{($a,$b)=@_;$b?f($b,$a%$b):$a}print f@ARGV' 111 185
37


引数が3つ以上になるとちょっと大変になる。

$ perl -le'sub f{my($a,$b,@c)=@_;@c?f($a,f($b,@c)):$b?f($b,$a%$b):$a}print f@ARGV' 111 222 148
37

再帰で戻ってきたときに処理を続けるのでmy宣言しておかないとマズいことになる。

総当たり的な方法

馬鹿正直に考えると、全部を割り切ることができる最大の数を見つければ良いので、こんなカンジに。

$ perl -le'for($i=$ARGV[0];$i>0;$i--){print$i and exit if !grep{$_%$i}@ARGV}' 111 222 148
37


for文を後置させるために".."で作ったリストを逆順にしてみるとか

$ perl -le'$i=$_,!grep{$_%$i}@ARGV and print$i and exit for reverse(1..$ARGV[0])' 111 222 148
37


そもそも、"and exit"とかダサい。「順番に見ていって、見つけたら出力して終了」じゃなくて「とりあえず全部チェックして抽出して、最後の要素だけ取り出す」という方法にすれば良い。

$ perl -le'print+(grep{/.*/,!grep$_%$&,@ARGV}1..$ARGV[0])[-1]' 111 222 148
37

というわけで、引数2個用のユークリッド互除法よりは長くなってしまうけど、3つ以上の引数に対してはこの方法の方が短く書ける。
実行効率、メモリ効率はひどいことになるけどw

追記

標準モジュールをキレイに使うならこんなカンジ?

$ perl -MList::MoreUtils=:all -le'print lastval{/.*/,none{$_%$&}@ARGV}1..@ARGV[0]' 111 222 148
37