シェル芸で最小公倍数・最大公約数を求める

Pocket

どうも、みどりごけです。

10月7日にjus共催 第31回朝からだと疲れるから午後からでええじゃろシェル芸勉強会に参加してきました。

そこで出題された問題に最小公倍数を求めるものがありましたので、それの解答とそれを応用して最大公約数を求める方法を考えてみました。

最小公倍数を求める

「それぞれの数に1から順番に掛けていき、最初に同じ数が2回出てきたものが最小公倍数」というアルゴリズムを使います。

それを元にシェル芸にするとこうなります
(見やすくするために改行を挟んでいます)

yes 4 6 |
awk '{print $1*NR RS $2*NR}' |
awk 'a[$1]++{print;exit}'

最初の4と6の部分を変えるとその2つの最小公倍数が求められます。

解説

処理の流れは以下のようになっています。

  1. yesコマンドで2つの数字をスペース区切りで無限に生成する
  2. awkコマンドでそれぞれの数に今の行数を掛けて、間に改行を挟んで出力する
  3. awkコマンドで同じ数が2回目に出てきたらそれを出力して終了する

NRは今の行数をが格納されている特殊変数です。
行数は1ずつ増えるので結果的に1から順番に掛けることになります。
RSは行の区切り文字、つまりは改行文字が格納されている特殊変数です。

そしてa[$1]++は同じ文字が2回目以降に出てきたときにマッチするパターンです。
一度以上出てきた数字na[n]の値がインクリメントされ1以上になり、awkはパターンが1以上ならアクションを実行するからです。

最後のexitの部分で最初にマッチしたときに終了するようにしているので最小公倍数のみ出力されます。

最大公約数を求める

(最大公約数をシェル芸で求める方法も過去のシェル芸勉強会で出題済みでした)

最小公倍数と逆の考え方で、「それぞれの数を1から順番に割っていき、割り切れた余りのない数で最初に同じ数が2回出てきたものが最大公約数」というアルゴリズムを使います。
最大公約数を求める有名なアルゴリズムとしてユークリッドの互除法がありますが、ループが必要なので、流れで処理するシェル芸的には不向きな気がします。

それを元にシェル芸にするとこうなります。
(見やすくするために改行を挟んでいます)

yes 12 18 |
awk '{print $1/NR RS $2/NR}' |
grep -Fv --line-buffered . |
awk 'a[$1]++{print;exit}'

同様に最初の12と18の部分を変えるとその2つの最大公約数が求められます。

解説

処理の流れは以下のようになっています。

  1. yesコマンドで2つの数字をスペース区切りで無限に生成する
  2. awkコマンドでそれぞれの数を今の行数で割って、間に改行を挟んで出力する
  3. grepコマンドで.(小数点)を含まない行を出力する
  4. awkコマンドで同じ数が2回目に出てきたらそれを出力して終了する

最小公倍数の問題と違うのは間にgrepコマンドが挟まっていることです。

このgrepコマンドでは-Fオプションで正規表現として扱わないようにして、-vオプションでマッチしない行を表示されています。
その結果、.(小数点)を含まない、つまりは割り切れた整数の商を出力します。

–line-bufferedオプションはバッファに詰まらないようにするために指定しています。

 

以上がシェル芸で最小公倍数・最大公約数を求める方法でした。

シェル芸勉強会は2ヶ月毎の偶数月に開催されているので気になった方は参加してみては如何でしょうか。

ではでは。

The following two tabs change content below.
みどりごけ

みどりごけ

スペシャルエグゼクティブアドバイザーほしい物リスト
どこぞのシェル芸大好き鯖管(自称ではない) / 基本情報技術者 / Linux (LPIC2保有) / C# / PHP / JavaScript / 食べ鉄 / Minecraft / ETS2 / GTAV / Ingress
みどりごけ

最新記事 by みどりごけ (全て見る)

コメントを残す