Thinkers'Studio
JavaとC言語の自習ツール
最大公約数を求めるプログラム例(ユークリッドの互除法、再帰呼出し)
 今回は、2つの整数の最大公約数を求めるプログラムです。
 求め方はひとつではありませんが、ここでは「ユークリッドの互除法」と呼ばれる有名なアルゴリズムを使います。
ユークリッドの互除法
 このアルゴリズムは、2つの自然数を対象としたものです。それらを a, b とします( a >= b > 0 )。
   (1) a を b で割り、その余りを r に入れます。
   (2) r が 0 なら b が最大公約数です。処理を終了します。
   (3) そうでないとき、新a = b、新b = r として (1) の手順に戻ります。

最大公約数を求めるプログラム 1 >
 a, b をキーボードから指定するものとします。
#include <stdio.h>
main()
{
    int a, b, r, temp;

    while( 1 ) {
        printf( "2つの自然数を指定してください : " );
        if( scanf( "%d, %d",  &a, &b ) != 2 ) break;
        if( a < b ) { temp = a; a = b; b = temp; }
        if( b < 1 ) continue;

        //ユークリッドの互除法により最大公約数を求める
        while( (r = a % b) != 0 ) {
            a = b;
            b = r;
        }
        printf( "最大公約数は%d\n", b );
    }
}

最大公約数を求めるプログラム 2 再帰呼出し版
 関数化するなら、再帰呼出しを使って次のように書くことができます。
#include <stdio.h>
//機 能:ユークリッドの互除法によりa,bの最大公約数を求める
//戻り値: 最大公約数、(自然数以外が指定されたときは-1)
int euclid( int a, int b )
{
    int temp;

    if( a < b ) { temp = a; a = b; b = temp; }
    if( b < 1 ) return -1;

    if( a % b == 0 ) return b;
    return euclid( b, a % b );
}

main()
{
    int a, b, n;

    while( 1 ) {
        printf( "2つの自然数を指定してください : " );
        if( scanf( "%d, %d",  &a, &b ) != 2 ) break;

        if( (n = euclid( a, b )) > 0 )
            printf( "最大公約数は%d\n", n );
    }
}

 上の枠内に示したアルゴリズムと同様ですが、割り算の余りを r に入れずに euclid( b, a % b ) のように引数に指定し、自分自身を呼び出しています。  (参考:再帰呼出しとは
 なお、大小関係による引数の入替や値のチェックは、euclid関数に含めるべき処理なので関数の先頭に移しました。再帰呼出し時にも if 文が実行されますが、負荷は問題にならない程度なので、機能のまとまりを優先します。

< 実行結果例(1、2のプログラムとも)>
2つの自然数を指定してください : 6, 3
最大公約数は3
2つの自然数を指定してください : 27, 18
最大公約数は9
2つの自然数を指定してください : 50, 24
最大公約数は2
2つの自然数を指定してください : 876, 204
最大公約数は12
2つの自然数を指定してください : 1024, 512
最大公約数は512
2つの自然数を指定してください : q

(今回のクイズは自習です)
 上記以外の求め方として、最小の公約数でどんどん割っていく方法があります。 筆算で書くとこうです。
    2 | 876  204 
    2 | 438  102 
    3 | 219   51 
         73   17
 73 と 17 はもう割り切れないので、それまで割った数を全部かけて(2×2×3)で12 が最大公約数となります。興味があれば、この処理手順でもプログラムを書いてみてください。

前回 クイズはありませんでした)