１）問題の分析──────────────────────────────１）
-
この問題で考えることはそんなにありませんね。とりあえず、入出力は標準入出力としておけば十分でしょう。あと必要なものは与えられた２数と、それらの商、余りです。
学生にこの手の問題を出すと、すぐメインルーチンで解こうとする人が多いのですが、あまりよくありません。こういう関数は後で使えるので、なるべく独立性を高くした方がいいのです。よって、２数を引数とし、その最大公約数を返す関数を作成することにします。（これは再帰版でも同じです）。
余談ですが、入出力については今回は（前回と違って）問題になりません。なぜなら、入出力に関係なく、与えられた２数の最大公約数を返す関数を作成すればいいからです。
詳しくは、後述します。
２）データとデータ構造──────────────────────────２）
-
データとしては、２数が与えられるので、これを受ける変数が必要です。それらの型としては普通の整数型で十分でしょう。あと、商、余りもあります。これらも整数型にしておきましょう。
３）大まかな流れ─────────────────────────────３）
-
大筋は簡単なので考えなくてもいいでしょう。
１）２数を入力する。
２）最大公約数を計算する。
３）結果を出力する。
こんな感じになります。えっ、何を当り前のことをって。いやこれで終りではなく、肝腎の最大公約数を計算する部分も考えましょう。二つの数が与えられたとき、その最大公約数を計算するにはどうすればいいでしょうか。（もちろんユークリッドの互除法を用いてです）これは少し考えてもらいましょう。（問題の例をよく見てください）
：
：
：
：
：
：
：
：
：
解答は次章で。
４）細かいアルゴリズムの決定───────────────────────４）
-
まず、メインルーチンの方からいきましょう。簡単ですが、前章を参考に少し考えてみてください。
：
：
：
：
：
：
：
：
：
では解答です。
最初はメインルーチンです。
まず、数の入力方法ですが、簡単にscanfを使いましょう。確かに前回、（またはご質問の解答で）scanf()は扱いが厄介なので使用は控えましょう、と書きましたが、この場合、逆にgetchar()で整数を入力する方が面倒なので、あえてscanf()を用いることにします。もし、ほかのものを使用する場合は、そこだけ書き換えても差し支えないでしょう。
次に最大公約数を計算する関数を呼び出し、その答えを変数にいれておきます。
最後に求めた答えを出力します。
次に、最大公約数を計算する関数ですが、どうなるでしょうか。（先の問題の例を見てください）
まず、とりあえず２数の余りを求めます。その余りが０なら割った答え（つまり商）が求める最大公約数です。もし０でないなら、割る数を余りで割り、その答えが０かどうか調べます。そして、余りが０になるまで繰り返します。この繰り返す部分をうまく作ればいいのです。手順としては
（１）ａをｂで割り、その余りをｃとする。
（２）もしｃが０なら（７）へ行く。
（３）ａ ← ｂとする。
（４）ｂ ← ｃとする。
（５）ａ÷ｂを計算し、余りをｃとする。
（６）（２）へ行く。
（７）ｂが答えである。
（ただし、ａ、ｂは与えられた整数でａ＞ｂとする。以降同じ）
こんな感じでしょうか。 （記号” ← ”は代入をあらわします。）
しかし、このアルゴリズムには、１つミスがあり、かつ冗長です。
ミスは”もしｂが０ならどうするか”ということであり、冗長な部分は”手順の中で２回割算がでてくる”ということです。ｂの問題はif文などを用いて解決できますが、冗長な部分はどうでしょうか。
アルゴリズムによっては、このような冗長性はなくせませんが、今回はなくすことが出来ます。実はその方法を使うと先のミス”ｂが０の時”も同時に解決できます。さぁ、一体どうすればいいのでしょうか。少し考えてみてください。
：
：
：
：
：
：
：
：
：
では、解答です。
まず、ｂが０の時を考えてみましょう。この時、求める最大公約数はａになります。
よって、
（０）もしｂが０ならａが答えである。
ということになります。
さて次に冗長性ですが、先の例の図とアルゴリズムをよく見てください。ａにｂを、ｂにｃを代入していますね。ここがポイントになります。ｂにｃを代入しているのですから、”ｃが０であるかないか”という問題はそのままｂについていえることになります。するとａわるｂを計算し、その余りをｃとして、ａ ← ｂ、ｂ ← ｃとして先の（０）で比較すればいいことになります。よく分からない方は、もう一度よく考えてみてください。
結局、アルゴリズムは以下のようになります。
（０）もしｂが０なら（５）へいく。
（１）ａをｂで割り、その余りをｃとする。
（２）ａ ← ｂとする。
（３）ｂ ← ｃとする。
（４）（０）へいく。
（５）ａが求める答えである。
（ただし、ａ、ｂは与えられた整数でａ＞ｂとする。）
よろしいですか？？
これを実際にプログラムに直すわけですが、繰り返しに関してはＣでは３種類ありましたね。今回はどれを用いればよいでしょうか。そうです。while文ですね。他のものを使って書くことは出来ますが、あまり自然ではありません。
では前回同様、抽象言語を使ってアルゴリズムを書き直してみましょう。
while(ｂが０でないならば)
{
ａ÷ｂの余りをｃとする。
ａ＝ｂ；
ｂ＝ｃ；
}
こうなります。最後になりましたが、関数はint型を返し、同じく、int型の引数を二つとります。
では、これらを基にプログラムを書いてみましょう。
５）プログラムを書く───────────────────────────５）
-
早速、プログラム全体を書いてみてください。インクルード文、変数、関数の宣言等を忘れないようにして下さい。
：
：
：
：
：
：
：
：
：
では解答です。
演習プログラム３−１
/* Program */
/* Short Program 5 */
/* 最大公約数を求める 1 */
#include <stdio.h>
int gcd(int a, int b);
main()
{
int x, y, z;
scanf("%d", &x);
scanf("%d", &y);
z = gcd(x, y);
printf("%d\n", z);
}
int gcd(int a, int b)
{
int c;
while (b <> 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
|
どうでしょうか。こんな感じになりましたか？？
では、解説しましょう。
まず、今回も特別な標準関数は用いていないので、インクルードするのはstdio.hだけでいいでしょう。
次に、最大公約数を計算する関数を宣言しています。返り値の型はint型、関数名はgcd、引数は二つでともint型です。
メインルーチンは、変数を３つ宣言しており、それぞれ、２つの数を入力する変数と、その最大公約数を入れる変数になります。
それから二つの値を入力し、その後それを関数に引数として渡し、最大公約数を求め、その結果を出力して終りです。
問題の関数の方ですが、ａ、ｂは引数として渡されるので、余りｃを宣言するだけです。後は、先のアルゴリズムに従って、書くだけです。
最後に答えのａをリターン文で返します。
６）コンパイル──────────────────────────────６）
-
いつものお約束のコンパイルです。くどいようですが、間違いが多いのは、
・”;”がない。
・”{}”の対応があってない。
など結構、初歩的なミスです。
最近のコンパイラはかなり親切にエラーメッセージを出してくれるので、それほど苦労することもないでしょうが、たまに分からなくなることがあります。そういう時は大抵これだと思って間違いないでしょう。エラーがでたらもう一度エディタで書き直します。
リンクが必要なコンパイラは、リンクもしておきましょう。
７）テスト────────────────────────────────７）
-
完成したらテストしてみてください。適当に２つの整数を入れてみて、プログラムがきちんと動くかどうか見てください。動いたら完成です。
８）改良─────────────────────────────────８）
-
今回の改良点は以下の通りです。
・入力をscanf()ではないものにする。
・入力がｘ＜ｙでもきちんと動くようにする。
・最大公約数を再帰的に求めるようにする。
・大きな整数も扱えるようにする。（100,000とか10,000,000,000位）
最初の点については、ここではやりません。いずれ機会があるでしょうから、その時にgetchar()を用いた方法について述べます。
２点目は、scanf()で二つの数を読み込んだ後、大小を比較して、大きい方がｘ小さい方がｙになるようにすればいいでしょう。
３点目は、後半で解説します。
４点目は、根本的にプログラムを改造する必要があります。
コンピュータでは通常大きな数（または小さな数）を扱う時は、配列を用いて計算します。例えば大きさ１００の整数型の配列を用意し、各要素として各桁の数値（０〜９）をいれるとするとこの配列で１００桁の数値が表現できることになります。これに対して、四則演算を行うサブルーチンを書き、比較するサブルーチンを書かなければならないわけです。出来ないことはありませんが、今はまだ難しいでしょう。（別にやってみてもかまいませんが）
９）完成─────────────────────────────────９）
-
と言うわけで、非再帰版はこれで完成です。
一休みしたら、再帰版に進みましょう。