最大公約数を求めるプログラム

学校の課題で明日の朝まで提出なのですが、わからないので教えてください。
二つの整数の最大公約数を求める再帰関数を定義し、最大公約数を表示するプログラムなのですが、その再帰関数が作れないのです。 どなたか教えていただけないでしょうか。モデルを書いていただけると助かります。

No.3 ベストアンサー 回答者： hisajiro 回答日時： 2008/08/11 13:57

手元にあるC言語によるアルゴリズム辞典には次のように書かれていました。

Euclidの互除法でｘ、ｙの最大公約数を求める。
int gcd(int x, int y) {
if (y == 0) return x;
elsereturn gcd(y, x % y);
}

この非再帰版は次のようになる。
int gcd(int x, int y) {
int t;
while (y != 0) {
t = x % y;x = y;y = t;
}
return x;
}

だそうです。
本の通りに書いただけなので正しいかは定かではないです。

この回答へのお礼

ありがとうございます。
完成させることができました。
本当に感謝です。

お礼日時：2008/08/11 22:30

No.5 回答者： Tacosan 回答日時： 2008/08/11 18:40

多分「オリジナル」という意味で正しい Euclid の互除法:

x, y に対し:
x が 0 なら y
y が 0 なら x
x ≧ y なら x-y と y に対して再帰的に求める
そうでなければ x と y-x に対して再帰的に求める

No.4 回答者： shirayukix 回答日時： 2008/08/11 15:19

最大公約数を求めるプログラム

http://okwave.jp/qa4243628.html
シーザー暗号の解読プログラム
http://okwave.jp/qa4243641.html

どちらも課題の丸投げのようです。
どこまで考えてどこが分からないのかを書いてください。

この回答へのお礼

そうですね。
おっしゃるとおりだと思います。
申し訳ございません。

お礼日時：2008/08/11 22:31

No.2 回答者： Jun15972 回答日時： 2008/08/11 13:38

ちょっと記述方法など忘れたので大体の流れだけになってしまいますが、

一番単純なものでは小さい方をA、大きいほうをBとして、2からAまでの数で両方を順番に割っていき、余りが0になる度に別の変数に除数を代入という感じになると思います。

No.1 回答者： okg00 回答日時： 2008/08/11 13:37

class GCDTest {

// ユークリッドの互除法により最大公約数を計算するメソッド gcd の定義
// int型の引数 n, m をとり, int型の値を返す
static int gcd(int n,int m){
// デバッグ(プログラムのミスを直す)のための出力
System.out.println("gcd("+n+","+m+")が呼ばれました");
// 剰余を求めて rに入れる
int r=n%m;
// nがmの倍数になっているなら最大公約数は m自身になる．
if(r==0) return m;
// n,mの最大公約数は m,rの最大公約数と等しい
else return gcd(m,r);
}
public static void main(String[] args){
// コマンドラインから
// java GCDTest arg0 arg1
// のようにして起動した時, args[0] -> arg0, args[1] -> arg1 となる．
// 文字列から int 型の整数値に変換するのは Integer.parseInt を使う
int i0=Integer.parseInt(args[0]);
int i1=Integer.parseInt(args[1]);
System.out.println(i0+"と"+i1+"の最大公約数は"+gcd(i0,i1)+"です");
}
}

JAVAでよいでしょうか？動作未確認です。課題なので答えは書きません。

http://itpro.nikkeibp.co.jp/members/ITPro/ITBASI …