#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 );
}
}
#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 文が実行されますが、負荷は問題にならない程度なので、機能のまとまりを優先します。
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 1773 と 17 はもう割り切れないので、それまで割った数を全部かけて(2×2×3)で12 が最大公約数となります。興味があれば、この処理手順でもプログラムを書いてみてください。
(前回 クイズはありませんでした)