ユークリッドの互除法
ユークリッドの互除法
『情報処理教科書 基本情報技術者試験のアルゴリズム問題がちゃんと解ける本 第2版』に、ユークリッドの互除法というのが載っています。
なぜそのようになるのか、証明を読むのが面倒くさくて今一歩理屈を理解してはいませんが、面白そうなので、ちょっとプログラミングに調子づいてきたところなので、作ってみることにしました。
互除法にも2種類のやり方がある
互除法にも2種類のやり方があるようです。
１つ目のやり方は、大きい方から小さい方を引いて、その答えと小さい方とで、どちらか大きい方からまた一方を引いて答えを求めるということを繰り返して、最後に、2つの数字が同じになったときが、最大公約数になるのだそうです。
２つ目のやり方は、大きい方を小さい方で割った余りで今度はまた小さい方を割る。ということを繰り返して、余りが無くなったときの割った値が最大公約数だということです。
1つ目のやり方は、大きい方から何度も小さい方を引けるだけ引いていくと、結局大きい方を小さい方で割った余りが残るので、そうなったら今度の数からもう一方を引いていって余りをまた出し、結局両者が一緒になるということは、もう一度引き算をすれば余りはゼロになるということで、割り算をしていった時に割り切れた数字と結局は同じものを求めているということになります。
実際に作ろうとすると結構面倒くさい
理屈は、以上なのですが、対象を正の整数ではなくて、整数全体にしようとすると、色々と問題が起こってきます。
まず、元の数値のままでは、マイナスの場合は、引いたり割ったりした数の絶対値がどんどん大きくなっていく場合があるので、上の理屈そのままにプログラムを組むと、いつまでたっても処理が終わらない可能性が出てきます。
マイナスの場合の公約数の考え方は、マイナスの数字に共通の約数を掛けてその数字になってもいいので、結局、2つの数字の絶対値、つまりどちらも正の値に直してから計算しても、結果は同じ事になるのだそうです。
次に、どちらかの数字が0 の場合には、引いても数値の絶対値は変化しないし、割れもしないので、他とは別個に、特別の処理をする必要があります。私は今回は、その場合だけは、計算をしないことにしました。
そんなこんなで、基本は簡単なのだけれど、例外処理をしようとすると、結構面倒くさいことになってしまいます。
こんなもんでいいのかしら
上記の本には、ベーシックな骨組みの部分しか載ってはいなかったので、私の下のプログラムが、果たして無駄が無いのかどうか、私には判断が付きかねます。
そもそも、絶対値を返す関数を自分で作ってから、人のを見ていて、Cに絶対値を返すabs() という標準関数が用意されていることを知ったぐらいですから、詳しい人から見ると、まだまだかもしれません。
#include <stdio.h>
#include <stdlib.h>
void input(int* a, int* b);
int calc1(int a, int b);
int calc2(int a, int b);
int main() {
int a, b, c;
c = 0;
input(&a, &b);
if (a == 0 || b == 0) {
printf("0では、最大公約数は計算できません:: a = %d b = %d", a, b);
}else {
c = calc1(a, b);
printf("引き算:: %d と %d の最大公約数は、 %d\n\n", a, b, c);
c = calc2(a, b);
printf("割り算:: %d と %d の最大公約数は、 %d\n\n", a, b, c);
}
}
/* ２つの数値入力 */
void input(int* a, int* b) {
char buff[40];
printf("最初の数字を入力してください\n");
fgets(buff, sizeof(buff), stdin); // キーボードからの入力
*a = atoi(buff);
printf("2つ目の数字を入力してください\n");
fgets(buff, sizeof(buff), stdin); // キーボードからの入力
*b = atoi(buff);
}
/* 引き算による互除法 */
int calc1(int a, int b) {
a = abs(a); /* 絶対値で処理をする */
b = abs(b);
if ((a != 0) && (b != 0)) {
while ((a != b)) {
if (a > b)
a -= b;
else
b -= a;
}
return a;
}else
return -1;
}
/* 割り算による互除法 */
int calc2(int a, int b) {
a = abs(a); /* 絶対値で処理をする */
b = abs(b);
if ((a != 0) && (b != 0)) {
while ((a != 0) && (b != 0)) {
if (a > b)
a = a % b;
else
b = b % a;
}
if (a >= b) {
return a;
}else {
return b;
}
}else
return -1;
}
実行結果
最初の数字を入力してください 28 2つ目の数字を入力してください 980 引き算:: 28 と 980 の最大公約数は、 28 割り算:: 28 と 980 の最大公約数は、 28