アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20210124 実施分 問10
次の流れ図は，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 の出力] → 終了。
- ア 4
- イ 9
- ウ 10
- エ 11
出典：基本情報技術者試験 科目A免除 修了試験 20210124 実施分 問10
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、2数の差を取る(または剰余を取る)操作を繰り返して最大公約数を求める。
この問題で必要なこと
876と204から引き算を繰り返す。大きい方から引くと10回の引き算で両者が12になり、最後の等しい判定を加えて計11回の比較となる。
ひっかけ
引き算の回数(10)と比較の回数(11)を混同する。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）