アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20260125 実施分 問37
次の流れ図において，
①→②→③→⑤→②→③→④→②→⑥
の順に実行させるために，①においてmとnに与えるべき初期値aとbの関係はどれか。ここで，a，bはともに正の整数とする。
流れ図:
開始 → ① [m ← a; n ← b] → ② 判定 [m : n]
②: ≠ なら ③ へ，＝ なら ⑥ [mの値を印字] → 終了
③ 判定 [m : n]: ＜ なら ⑤ [n ← (n － m)] へ，＞ なら ④ [m ← (m － n)] へ
④，⑤ の後はいずれも ② の入口へ戻る（②の上へ合流）
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20260125 実施分 問37（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
引き算による互除法(m>nならm−n、m<nならn−m)を指定の経路で辿ると初期値の関係式が導ける。
この問題で必要なこと
指定の経路は、n←n−m、m←m−n、m=nの順なので、n'=b−a、m'=a−(b−a)=2a−b となる。m'=n'より 3a=2b になる。
ひっかけ
1回目の分岐の向きを逆にすると別の関係式(2a=3bなど)になる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）