アルゴリズムとプログラミング
令和5年度 基本情報技術者試験 科目A 公開問題 問11
次の流れ図において，① → ② → ③ → ⑤ → ② → ③ → ④ → ② → ⑥ の順に実行させるために，①において m と n に与えるべき初期値 a と b の関係はどれか。ここで，a，b はともに正の整数とする。
流れ図:
開始
① m ← a ; n ← b
② 判定 m : n （≠ のとき ③ へ、= のとき ⑥ へ）
③ 判定 m : n （< のとき ⑤ へ、> のとき ④ へ）
④ m ← (m － n) → ② に戻る
⑤ n ← (n － m) → ② に戻る
⑥ m の値を印字（平行四辺形）
終了
- ア a = 2b
- イ 2a = b
- ウ 2a = 3b
- エ 3a = 2b
出典：令和5年度 基本情報技術者試験 科目A 公開問題 問11
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法(引き算版)は、大きい方から小さい方を引く操作を繰り返し、両者が等しくなったときの値を最大公約数とするアルゴリズムである。
この問題で必要なこと
指定の実行順では、まず m<n で n←n−m (n=b−a)、次に m>n で m←m−n (m=2a−b) となり、m=n で終了する。2a−b=b−a から 3a=2b が導かれる。
ひっかけ
途中の分岐の向きを逆に追ったり、1回目の更新後の値を使い間違えると、a=2b や 2a=3b などの誤答になる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）