アルゴリズム (全79問中50問目)
No.50
次の流れ図は,2数 A,Bの最大公約数を求めるユークリッドの互除法を,引き算の繰返しによって計算するものである。 Aが876,Bが204のとき,何回の比較で処理は終了するか。
出典:平成20年春期 問15
- 4
- 9
- 10
- 11
- [出題歴]
- 基本情報技術者 H15秋期 問15
- 基本情報技術者 H31春期 問7
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと次のようになります。
- (開始時にL←876,S←204で初期化)
876>204 … L←876−204=672 - 672>204 … L←672−204=468
- 468>204 … L←468−204=264
- 264>204 … L←264−204=60
- 60<204 … S←204−60=144
- 60<144 … S←144−60=84
- 60<84 … S←84−60=24
- 60>24 … L←60−24=36
- 36>24 … L←36−24=12
- 12<24 … S←24−12=12
- 12=12 … A,B,Lの出力