アルゴリズムとプログラミング
平成31年度 春期 基本情報技術者試験 午前 問7
次の流れ図は，2 数 A, B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。A が 876, B が 204 のとき，何回の比較で処理は終了するか。
流れ図:
開始 → [L←A; S←B] → 判断 L:S
L:S の判断で，> のとき [L←(L−S)] を実行して判断 L:S に戻る。< のとき [S←(S−L)] を実行して判断 L:S に戻る。= のとき [A, B, L の出力] → 終了。
答えを選ぶ
出典：平成31年度 春期 基本情報技術者試験 午前 問7（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、2数が等しくなるまで大きい方から小さい方を引くと最大公約数が得られる。
この問題で必要なこと
大きい方から小さい方を引く操作を繰り返す。876,204では引き算が10回、等しくなって終わる比較を含めて11回の比較になる。
ひっかけ
引き算の回数(10)と比較回数(11)を取り違えさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）