アルゴリズムをコードにする練習2:最大公約数を求める
はじめに
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に余りが代入されている」ところからをスタートだと考えます。すると、
- bが0ならばaが最大公約数
- bが0でないならばaにbを、bにa÷bの余りを代入する
- 1に戻る
という形にすることが出来ます。
「なんでまだ計算してないのに結果が入ってることになるの?」 と思われる方もいるでしょうけれど、この、初回の計算をしたとみなして始めるは、ロジックを考えるときによく使う手段です。この視点を取り入れるだけで、複数の処理をまとめることが出来るときがしばしばあるので、「そういうものか」と思ってもらえると良いです。
フローチャート1
さて、上に書いた3つの手順をフローチャートにしてみます。
…繰り返しの中でやっている作業をよく見てみましょう。
練習0のときに確認しましたが、変数は代入したら元の値は消えてしまいますよね。
ということは、
- a ← b
- 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関数があります
なので、このあたりは調べてみてください。
まとめ
リカーシブルコールを使うと、繰り返しをシンプルにすることが出来ます。
知らないで初めてコードで目にするとびっくりすると思うので、ここで見慣れてもらえると良いと思います。
Author And Source
この問題について(アルゴリズムをコードにする練習2:最大公約数を求める), 我々は、より多くの情報をここで見つけました https://zenn.dev/riko111/articles/169888f63e4945fbc853著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol