プログラムが自分自身を呼び出す処理のことを「再帰呼出し」といいます。
今回は再帰呼出しを使って、2つの数の最大公約数を求める方法を解説します。
最大公約数を求めるために、今回は『ユークリッドの互除法』と呼ばれるアルゴリズムを使います。
再帰呼出しの解説は以下の記事も参照ください。
auroralights.jp
最大公約数を求めるのVBAコード
以下は「48」と「20」の最大公約数を求めるVBAコードです。
Sub sampleCall()
MsgBox sampleGcd(48, 20)
End Sub
Function sampleGcd(ByVal m As Long, ByVal n As Long) As Long
If n = 0 Then
sampleGcd = m
Else
sampleGcd = sampleGcd(n, m Mod n)
End If
End Function※Sub sampleCall内のMsgBox sampleGcd(48, 20)の()内の数字「48,20」を任意の2つの数字に変えると、その数字の最大公約数を求めることができます。
処理を考える
上記の最大公約数を求めるVBAの処理を見ていきます。
1～2行目：Subプロシージャ「sampleCall」からFunctionプロシージャ「sampleGcd」を呼び出し、引数48と20を渡します。
5行目：48を「m」、20を「n」に格納します。
6行目：IF文の条件分岐です。n = 0ではないので、9行目に移ります。
9行目：Functionプロシージャ「sampleGcd」を再帰呼出し、その際に「n」と「m mod n (mをnで除算した余り)」を引数として渡します。
5行目：渡された引数「n」を「m」、「m mod n」を「n」に格納します。
以降は「n」が「0」になるまで、再帰呼出しでFunctionプロシージャ「sampleGcd」の処理を繰り返します。「n」が「0」になった時点の「m」を返り値として、Functionプロシージャ「sampleGcd」から呼び出し元のSubプロシージャ「sampleCall」に渡し、メッセージボックスに表示して処理を終えます。
引数「m」と「n」の変化
参考情報：ユークリッドの互除法、最大公約数、GCD関数
ユークリッドの互除法
ユークリッドの互除法は、2つの自然数a、bの最大公約数を求める方法です。(詳細な内容は難しいので割愛します)
1.「a」を「b」で割る。余り「r」を求める
2.「b」を1.で求めた「r」で割る。その余り「r1」を求める
3.「r」を2.で求めた「r1」で割る、その余り「r2」を求める
4.「r1」を3.で求めた「r2」で割る、その余り「r3」を求める
・・・・
余りが「0」になる(割り切れる)まで繰り返します。(必ず割り切れます)
余りが「0」になったときの割る数が最大公約数になります。
以下は500と75の最大公約数を求め方です。
最大公約数
2つ以上の数を割り切る数の中で、共通している数かつ、最も大きい数を最大公約数といいます。
最大公約数を理解するには、約数、公約数を理解する必要があります。
- 約数：ある1つの正の整数を割り切る数
- 公約数：2つ以上の正の整数に共通な約数
- 最大公約数：公約数の中で一番大きな数
以下画像では10と12の最大公約数を考えています。
GCD関数
Excelのワークシート関数『GCD関数』を使うと、最大公約数を求めることができます。
■GCD関数の書式
=GCD(数値1,数値2[,・・・・・,数値255])
GCD関数の利用例(=GCD(C2:D2)と引数にセル範囲を指定)
お読みいただきありがとうございました。
