平成３１年度 春期 基本情報技術者試験問題と解説
問７
次の流れ図は、2数A、Bの最大公約数を求めるユークリッドの互除法を、引き算の繰返しによって計算するものである。Aが876、Bが204のとき、何回の比較で処理は終了するか。
ア 4 イ 9 ウ 10 エ 11
正解
エ
解説
開始
L ← 876、S ← 204
876 > 204 ・・・1回目
L ← 876 − 204 ＝ 672
672 > 204 ・・・2回目
L ← 672 − 204 ＝ 468
468 > 204 ・・・3回目
L ← 468 − 204 ＝ 264
264 > 204 ・・・4回目
L ← 264 − 204 ＝ 60
60 < 204 ・・・5回目
S ← 204 − 60 ＝ 144
60 < 144 ・・・6回目
S ← 144 − 60 ＝ 84
60 < 84 ・・・7回目
S ← 84 − 60 ＝ 24
60 > 24 ・・・8回目
L ← 60 − 24 ＝ 36
36 > 24 ・・・9回目
L ← 36 − 24 ＝ 12
12 < 24 ・・・10回目
S ← 24 − 12 ＝ 12
12 ＝ 12・・・11回目
A ＝ 876、B ＝ 204、L ＝ 12 の出力。
終了
よって、比較処理は11回である。
| 問６ | 目次 | 問８ |