§Algorithm§

☆最大公約数を求める☆

　最大公約数を求めるとき、算数的に次のような方法を用いると思います。

　この方法がコンピュータ上の計算に向いているでしょうか？
この方法は、ひらめき的な要素も持っているのでコンピューターにとっては、 かなり苦手な部類に入る計算手段です。もちろんできないということはない でしょうが、無駄な計算処理が増えることは間違いありません。
　そこで、次のような方法を用います。

　「A,B２つの数字の最大公約数を求める場合を考えます。まずA,Bの大きい方の 数(Aとします)から小さい方の数(Bとします)を引いて、その差がCだったとします。 そしてBからCを引き、その差からCを引いて、というように2つの差が同じにな るまで繰り返し、同じになったその値が最大公約数となります。32,12の 最大公約数をこの方法で求めると、

32 - 12 = 20
20 - 12 = 8
12 - 8 = 4
8 - 4 = 4 //

のようになります。」
　このような方法は、人間的には不向きでしょうが、 コンピューター的には、最も効率のよい方法なのです。
Visual Basicのプログラムコードでは以下のようにまとめられます。 （クラスにまとめています。）

'========================================================
'-----処理内容-----
'最大公約数を求めそれを返す
'-----引数-----
'BaseValue()　最大公約数を求めたい数が入った配列
'========================================================
Public Function GetMaxDev(BaseValue() As Long) As Long

    Dim Count As Long        '配列の最大インデックス
    Dim i As Long            'カウンタ
    Dim a As Long, b As Long '最大公約数を求める2つの要素
    Count = UBound(BaseValue)
    a = BaseValue(0)

    '繰り返す回数は、(配列の数−1)回
    For i = 0& To (Count - 1)
        b = BaseValue(i + 1)
        Do While a <> b
            If a > b Then
                a = a - b
            Else
                b = b - a
            End If
        Loop
        '1で等しい場合、最大公約数はない
        If a = 1& Then GetMaxDev = 0&: Exit Function
    Next i
    '最大公約数を返す
    GetMaxDev = a
End Function

ちょっと計算回数が増えてきたとき修正する必要があるかもわかりませんが、 小学校の算数程度の問題なら、気にならない程の速度でしょう。

（サンプルプログラムの動作確認）

機種 PC-9821V13S
OS Windows95
開発ツール Visual Basic Ver.4.0
更新日 99/11/23

ダウンロード MaxDev.lzh(2.25KB)

Visual Basic Ver.5.0,Ver.6.0でも問題なく動作すると思います。
なお、このコーナーに掲載されているプログラムコード、およびプログラムファ イルが原因で起きた損害などに関して一切の責任を負うことはできません。

★このコーナーに掲載されているプログラムコード、およびプログラムファ イルを無断で配布・転載することは、原則として禁止です。

（参考書）

「C言語によるはじめてのアルゴリズム入門」
著者：河西　朝雄氏
出版社：技術評論社

Algorithmインデックス トップ

Copyright(C)1999 Tomoya. All rights reserved.