アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20161211 実施分 問7
次の流れ図は，2 数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。A が 876，B が 204 のとき，何回の比較で処理は終了するか。
流れ図:
開始 → [A→L, B→S] → 判断 L:S
- L:S が > のとき: [L−S→L] → 判断 L:S の入口へ戻る
- L:S が < のとき: [S−L→S] → 判断 L:S の入口へ戻る
- L:S が = のとき: [A,B,L の出力] → 終了
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20161211 実施分 問7（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
引き算版の互除法は、2数が等しくなるまで大きい方から小さい方を引き、等しくなった値が最大公約数となる。
この問題で必要なこと
大きい方から小さい方を引く操作を繰り返し、両者が等しくなるまでの比較回数を数える。876と204では引き算が10回で、最後の一致判定を加えて11回になる。
ひっかけ
最後の等号判定の1回を数え忘れて10回とする誤り。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）