アルゴリズムと問題解決に関する問題

質問

二つの正の整数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

回答No.2

ymmasayan

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

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

１．項番５と項番１０のＧＣＤの出力は絶対に通らないようになっています。
ＧＣＤには値も入りません。
必ず項番３と項番８でしか出力しません。
問題を出した人が再帰が良くわかっていないようです。
これをきちんとするには「ＲＥＴＵＲＮ：ＣＡＬＬ先の次へ戻る」を入れる必要があります。
それをしないとこのプログラムはおそらく暴走するでしょう。

２．項番３は「もしＣ＝０なら」のミスでしょう。

一応このままやってみると
１　４８：８４だからＡ＜Ｂ
２　Ｃ＝８４％４８＝３６
３　Ｃ≠０で次へ
４，５　４８，３６で互除法を呼ぶ　
１　４８：３６だからＡ＜Ｂではない
６，７　Ｃ＝４８％３６＝１２
８　Ｃ≠０で次へ
９，１０　３６，１２で互除法を呼ぶ
１　３６：１２だからＡ＜Ｂではない
６，７　Ｃ＝３６％１２＝０
８　Ｃ＝０なのでｂ＝１２を出力して終了

てなとこでしょうか。

回答No.1

arukamun

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

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 ;
}