基本情報技術者試験 基本情報技術者試験 平成31年度 春期 午前 午前 問7: 次の流れ図は，2 数 A, B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。A が 876, B が 204 のとき，

問題本文

次の流れ図は，2 数 A, B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。A が 876, B が 204 のとき，何回の比較で処理は終了するか。

選択肢

• ア.4
• イ.9
• ウ.10
• エ.11

正解

エ. 11

解説

L=876, S=204 から大きい方から小さい方を引く操作を繰り返す。876→672→468→264→60 (4回, LSのループ)、次に S を減らす: 204→144→84→24 (3回, L<Sのループ)、再びLS: 60→36→12 (2回)、再びL<S: 24→12 (1回)、L=S=12で=判定で終了 (1回)。比較回数の合計は 4+3+2+1+1 = 11。エが正解。