🐙

アルゴリズムをコードにする練習2:最大公約数を求める

2020/11/22に公開

はじめに

3回目になる今回は、最大公約数を求めるやり方について見ていきます。
ここで、リカーシブルコール(再帰呼び出し)と言われる手法を使っていきます。

ユークリッド互除法

2つの整数の最大公約数を見つけるやりかた。2000年以上前にも遡ることが出来る最古のアルゴリズムだとか。

最大公約数とは

約数

ある自然数(0以上の整数)を割り切ることが出来る整数。

公約数

複数の自然数に共通の約数。

最大公約数

公約数の内最大のもの。

例)3と9の最大公約数は3。8と12の最大公約数は4。56と98の最大公約数は14。

ユークリッド互除法の考え方

a > bになる2つの整数a,bの最大公約数は、bとaをbで割った余りの最大公約数に等しい、という性質があります。
aをbで割った余りをrとして、上記の性質を利用すると、bをrで割った余りを求め、さらに r をその余りで割ったときの余り、と余りを求める計算を繰り返して、余りが 0 になった時の割った数(除数)がaとbとの最大公約数になる、という考え方が、ユークリッド互除法です。

  • 例えば3と9のとき
     a=9,b=3
     a÷b 余り0
     割った数bは3なので、最大公約数は3
  • 8と12では
     a=12,b=8
     a÷b 余り4
     r=4
     b÷r 余り0
     割った数4が最大公約数
  • 56と98では
     a=98,b=56
     a÷b 余り42
    r=42
     b÷r 余り14
    b=42,r=14
     b÷r 余り0
    割った数14が最大公約数

3番目の例では3回割り算をしてますが、2回めと3回目は同じb÷rの計算をしてますね。1回目も同じ計算になるにはどうしたら良いでしょう。
そもそも、最初の1回目がa÷bなので、そのあとも同じになるように代入をします。
つまり、

  • 8と12では
     a=12,b=8
     a÷b 余り4
     a=b,b=余り
     a÷b 余り0
     割った数4が最大公約数
  • 56と98では
     a=98,b=56
     a÷b 余り42
    a=b,b=余り
     a÷b 余り14
    a=b,b=余り
     a÷b 余り0
    割った数14が最大公約数

という形にするわけです。ただ、これだと余りが変数に割り当てられていないので、「bに余りが代入されている」ところからをスタートだと考えます。すると、

  1. bが0ならばaが最大公約数
  2. bが0でないならばaにbを、bにa÷bの余りを代入する
  3. 1に戻る

という形にすることが出来ます。

「なんでまだ計算してないのに結果が入ってることになるの?」 と思われる方もいるでしょうけれど、この、初回の計算をしたとみなして始めるは、ロジックを考えるときによく使う手段です。この視点を取り入れるだけで、複数の処理をまとめることが出来るときがしばしばあるので、「そういうものか」と思ってもらえると良いです。

フローチャート1

さて、上に書いた3つの手順をフローチャートにしてみます。

…繰り返しの中でやっている作業をよく見てみましょう。
練習0のときに確認しましたが、変数は代入したら元の値は消えてしまいますよね。
ということは、

  1. a ← b
  2. b ← a ÷ bの余り
    1つ目の作業をしたあと、2つ目の作業をするときには、もうaの値はbの値で上書きされています。じゃあ、順番を逆にしたら? …解決しませんね。

ということは、せっかくスッキリしたと思うのにやっぱりrが必要なんでしょうか。
いえいえ、これを解決する手段があります。

フローチャート2


これが、リカーシブルコール(再帰呼び出し)を使った処理です。gcdという処理の中から、再度gcdという処理を呼び出す、呼び出された処理は更にgcdを…と自分自身を呼び出し続けているものです。
変数のスコープは開始から終了までなので、呼び出すときのa,bと呼び出されるときのa,bは別物になります。なので、この書き方で先程の上書き問題が解消されるのです。

コードでは

C言語

int gcd(int a, int b)
{
    if(b == 0){
        return a;
    } else {
        return gcd(b, a%b);
    }
}

JavaScript

function gcd(a,b){
    if(b==0){
        return a;
    } else {
        return gcd (b, a%b);
    }
}

その他の言語

その他の言語では、最大公約数は最初からライブラリに用意されています(笑)

  • Java
     BigIntegerクラスドにgcdメソッドがあります
  • Python
     mathモジュールにgcd関数があります
  • C++
     C++17以降に、stdにgcd関数があります

なので、このあたりは調べてみてください。

まとめ

リカーシブルコールを使うと、繰り返しをシンプルにすることが出来ます。
知らないで初めてコードで目にするとびっくりすると思うので、ここで見慣れてもらえると良いと思います。

Discussion