アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20130623 実施分 問52
次の流れ図において，
①→②→③→⑤→②→③→④→②→⑥
の順に実行させるために，①においてmとnに与えるべき初期値aとbの関係はどれか。ここで，a，bはともに正の整数とする。
流れ図:
開始 → ①[a→m, b→n] → ②判定「m : n」
・②で「=」→ ⑥[mの値を印字] → 終了
・②で「≠」→ ③判定「m : n」
・③で「<」→ ⑤[n−m→n] → ②の直前へ戻る
・③で「>」→ ④[m−n→m] → ②の直前へ戻る
- ア a＝2b
- イ 2a＝b
- ウ 2a＝3b
- エ 3a＝2b
出典：基本情報技術者試験 科目A免除 修了試験 20130623 実施分 問52
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
引き算型の互除法は大きい方から小さい方を引く操作を等しくなるまで繰り返し、順に追えば初期値の関係式が得られる。
この問題で必要なこと
m=a,n=b。m<nでn=b-a、次にm>nでm=a-(b-a)=2a-b、その後m=nが成立するので 2a-b=b-a、すなわち3a=2b。
ひっかけ
実行順の③の分岐方向(<,>)を取り違えると別の関係式になる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）