アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20190728 実施分 問7
次に示すユークリッドの互除法（方法 1，方法 2）で，正の整数 a，b の最大公約数は，それぞれ m と n のどちらの変数に求まるか。ここで，m mod n は，m を n で割った余りを表す。
流れ図 2 つ。
[方法1] 開始 → m←a, n←b → r←m mod n → ループ1（条件 r=0：ループ端の上端に記載）→ m←n → n←r → r←m mod n → ループ1（下端）→ 終了
[方法2] 開始 → m←a, n←b → ループ2（上端・条件なし）→ r←m mod n → m←n → n←r → ループ2（下端，条件 r=0）→ 終了
選択肢は 方法1・方法2 の列を持つ表（ア～エ）。
- ア 方法1：m，方法2：m
- イ 方法1：m，方法2：n
- ウ 方法1：n，方法2：m
- エ 方法1：n，方法2：n
出典：基本情報技術者試験 科目A免除 修了試験 20190728 実施分 問7
答えと解説を見る
正解：ウ
覚える知識
ユークリッドの互除法のトレースと初期値関係
互除法はrが0になったときの除数(直前のn)が最大公約数である。
この問題で必要なこと
方法1は余りを先に計算しr=0で出て最終のnが、方法2はループ内で更新してr=0で出るため最終のmが最大公約数。
ひっかけ
ループの前判定・後判定の違いを見落としmとnを取り違えさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）