アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問51
次の流れ図において，
①→②→③→⑤→②→③→④→②→⑥
の順に実行させるために，①において m と n に与えるべき初期値 a と b の関係はどれか。ここで，a, b はともに正の整数とする。
流れ図: 開始 → ①「a → m, b → n」→ ②判定「m : n」。② が「＝」なら ⑥「m の値を印字」→ 終了。② が「≠」なら ③判定「m : n」へ。③ が「＞」なら ④「m−n → m」，「＜」なら ⑤「n−m → n」。④ と ⑤ の後は ② の入口へ戻る。
- ア a＝2b
- イ 2a＝b
- ウ 2a＝3b
- エ 3a＝2b
出典：基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問51
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
引き算によるユークリッドの互除法は、m=nになるまで大きい方から小さい方を引き、最大公約数を求める。
この問題で必要なこと
m>n→m−n、次にm<n→n−m、次にm>n→m−n、最後にm=n。a−b=m1、b−m1=n1、m1−n1=a−b−(2b−a)... 条件を解くと3a=2b。
ひっかけ
手順の順序を取り違えa,bの関係式を誤る。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）