【学習ログ】【Ruby】最大公約数を求めるアルゴリズム

※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。

最大公約数を求めるアルゴリズム

いきなり完成コード

def greatest_common_divisor(a,b)
    
  if a < b
    a, b = b, a
  end
  
  while
    c = a % b
    
      if c == 0
      return b
      end

    a, b = b, c
  end
end

puts greatest_common_divisor(66,32)

試行錯誤の上、上記のコードで落ち着いた。
ちなみに引数に’0’とか渡すと、下記のようなエラーになる。

algorithm_exercise1.rb:21:in `%': divided by 0 (ZeroDivisionError)
        from algorithm_exercise1.rb:21:in `greatest_common_divisor'
        from algorithm_exercise1.rb:32:in `<main>'

簡単に用語の説明から

最大公約数とは？

それぞれの数字の共通の約数（公約数）の中で一番大きな数字のこと。最大公約数を求める方法の一つとしてユークリッドの互除法という計算方法がある。

ユークリッドの互除法（ごじょほう）とは？

スミマセン、私数学的なものが大の苦手で・・用語を調べても重要な性質とやら数式とやらで、もうサッパリ。なんとか読み砕いて、だいたいこういうことだろうなということで落ち着いた。

aとbの最大公約数を求める時（a>bであることが前提）
①　まずaとbを割った数を求め、その余り（c）を割り出す。
②　bの値をaへ、cの値をbへ移動する
③　①と②を余りが0になるまで繰り返す
⑤　余りが0になったときにbに入っている値が最大公約数

私なりの解釈

そもそも、最大公約数とかユーグリットの互除法とかかなり無知なレベルだったので、理解に時間がかかったが自分なりに解釈した結果は以下。

a, b = b, c #処理が続く間は、bをaにcをbに代入し続けるのくだりについて
以下のような図を作ってみた。

正確ではないかもしれないが、だいたいこんな感じだろうか・・

本日は以上となります。

最後までお読みくださりありがとうございました。