二つの正の整数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.1
- 回答日時:
再起処理をしない例です。
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 ;
}
No.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を出力して終了
てなとこでしょうか。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 数学 g=gcd(a,b)とする。このときa|cかつb|cならばab|cgを示せ。という問題を c=qa, 3 2023/05/21 18:31
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- 数学 数学A、確率の問題です。 nを4以上の自然数とする。数字の1からnが書かれたカードが1枚ずつ、合計n 3 2023/07/02 22:54
- Visual Basic(VBA) vba メモリ節約 3 2022/09/16 21:45
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 再質問 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分 4 2023/03/05 17:08
- Java Java 年数計算 3 2023/01/28 10:52
- 転職 転職活動中の者です。 少し気になった事があるのですが、転職サイトにおける求人募集終了のタイミングです 2 2023/01/09 00:53
- 計算機科学 高校1年の数学です! ユークリッドの互除法です。 写真の左上の問題で、問題集の答えは x=14、y= 1 2023/02/25 16:59
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
PS4コントローラーをPCでゲーム...
-
詳しくないので、どなたかお教...
-
VBA レジストリの値の読み方に...
-
コンセントの電力は入力と出力...
-
TV出力ポートをOFFにすれば良い...
-
4Kの外部モニターに出力すると...
-
COBOLのMOVEで桁数が異なる場合
-
AIに回答させるって
-
printfの書式%.*s
-
cout と cerrの違い
-
プログラムについての質問です...
-
printfとputcharの違いは
-
OBS配信すると、マイクが途切れ...
-
ExcelマクロでIEのHP上のダウン...
-
C++の’ \\n’と ’endl’ の違いに...
-
VBAでテキスト出力時のスペース...
-
\\00.入力先ディレクトリ上でWO...
-
【エクセル、並び替えについて】
-
Windows Formアプリからコンソ...
-
エクセルマクロで出力行の増や...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
PS4コントローラーをPCでゲーム...
-
4Kの外部モニターに出力すると...
-
MMDでavi出力が出来ない
-
プログラムについての質問です...
-
コンセントの電力は入力と出力...
-
AIに回答させるって
-
OBS配信すると、マイクが途切れ...
-
VBAでテキスト出力時のスペース...
-
cout と cerrの違い
-
アクセスでエクセルに出力する...
-
printfとputcharの違いは
-
ACCESS クエリ→フォーム...
-
VBAのExecメソッドで画面を非表...
-
COBOLのMOVEで桁数が異なる場合
-
テキストファイルから特定の文...
-
VBAで有効数字の設定
-
coutで出力した文字を消去する...
-
Windows Formアプリからコンソ...
-
KEYENCEのシーケンスプログラム...
-
CRC16計算について
おすすめ情報