出産前後の痔にはご注意!

二つの正の整数A,Bの最大公約数を求めるユークリッドの互除法のアルゴリズム

互除法(A,B)
入力正の整数A,B
1 もしA<Bならば
2 BをAで割ったあまりをCとせよ
3 もしC=0でないならAを出力して終了
4 そうでないならば
5 GCD=互除法(A,C)とし、GCDを出力し終了
6 そうでないならば
7 AをBで割ったあまりをCとせよ
8 もしC=0ならばBを出力して終了
9 そうでないならば
10 GCD=互除法(B,C)とし、GCDを出力し終了

互除法(48,84)を行ったときのうえのアルゴリズムの動作(再帰呼び出しの途中に現れるCやGCDの値)を求めよ

これを一応といてみましたが表現方法がいまいちわからないので良い回答の仕方教えてください。

自分で解いた答え
1 A<BなのでB/Aのあまり36をCとする
2 C=36
3 Cは0でない
4、5 GCD=(A,C)=(48,36)

1に戻る A=48,B=36とする
1 A<Bでない
6 A/BのあまりをCとする
7 48/36のあまり C=12
8 Cは0でない
9,10 GCD=(36,12)

1に戻る A=36,B=12
1 A<Bでない
6,7 36/12 C=0
8 C=0 B=12

このQ&Aに関連する最新のQ&A

3C とは」に関するQ&A: E2cとE3の違いは?

A 回答 (2件)

トレースはきちんと出来ていますね。



ただ問題の出来がひどすぎます。

1.項番5と項番10のGCDの出力は絶対に通らないようになっています。
GCDには値も入りません。
必ず項番3と項番8でしか出力しません。
問題を出した人が再帰が良くわかっていないようです。
これをきちんとするには「RETURN:CALL先の次へ戻る」を入れる必要があります。
それをしないとこのプログラムはおそらく暴走するでしょう。

2.項番3は「もしC=0なら」のミスでしょう。

一応このままやってみると
1 48:84だからA<B
2 C=84%48=36
3 C≠0で次へ
4,5 48,36で互除法を呼ぶ 
1 48:36だからA<Bではない
6,7 C=48%36=12
8 C≠0で次へ
9,10 36,12で互除法を呼ぶ
1 36:12だからA<Bではない
6,7 C=36%12=0
8 C=0なのでb=12を出力して終了

てなとこでしょうか。
    • good
    • 0

再起処理をしない例です。



1. もし、B>0ならばループ、それ以外はループから脱出し、6に行く
2. cにa÷bの余りを代入する。
3. aにbを代入する。
4. bにcを代入する。
5. 1に行く
6. aが最大公約数

いかがでしょうか。

JavaScriptであれば、

function gcm(a,b)
{
  var c ;
  while ( b > 0 ){
    c = a%b ;
    a = b ;
    b = c ;
  }
  return a ;
}

C言語であれば、
int gcm(int a,int b)
{
  int c ;
  while ( b > 0 ){
    c = a%b ;
    a = b ;
    b = c ;
  }
  return a ;
}
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング