<問題> ユークリッドの互除法によって、２つの整数p, q の最大公約数を求めるプログラムを作成せよ。（ただし、p > q とする）
<実行例> 最大公約数を出力するだけでもいいが、このプログラムが、どのように実行されているのかを、変数を追いかけて確かめよう。適当なprintf文を入れてみよう。
p,qを入力してください p = 512 q = 384 512と384の最大公約数を求める p = 512, q = 384, r = 128 p = 384, q = 128, r = 0 最大公約数は128である。 p = 91 q = 77 91と77の最大公約数を求める p = 91, q = 77, r = 14 p = 77, q = 14, r = 7 p = 14, q = 7, r = 0 最大公約数は7である。 p = 876 q = 204 876と204の最大公約数を求める p = 876, q = 204, r = 60 p = 204, q = 60, r = 24 p = 60, q = 24, r = 12 p = 24, q = 12, r = 0 最大公約数は12である。
解答例
#include <stdio.h>
int gcd1(int p, int q);
int main (void) {
int p, q;
printf("p,q (p > q)を入力してください \n");
printf("p = ");
scanf("%d", &p);
printf("q = ");
scanf("%d", &q);
printf("\n%dと%dの最大公約数を求める\n", p, q);
printf("%dと%dの最大公約数は%dである。\n",p, q, gcd1(p,q));
return 0;
}
int gcd1 (int p, int q) {
int r;
/* 以下、適当なprintf文で、変数、x,y,rの変化をおいかけてみよう */
r = p % q; // p > q でないといけない。もちろん余りだから, q > r
while(r != 0) {
p = q; // 次のxとyをセット
q = r;
r = p % q; // あまりを求める
printf("p = %4d, q = %4d, r = %4d \n", p, q, r);
}
return q;
}