アルゴリズムとプログラミング
次の流れ図において、①→②→③→⑤→②→③→④→②→⑥ の順に実行させるために、①においてmとnに与えるべき初期値aとbの関係はどれか。ここで、a、bはともに正の整数とする。
ア.a=2b
イ.2a=b
ウ.2a=3b
エ.3a=2b正解
解説
これはユークリッドの互除法(大きい方から小さい方を引き続けて最大公約数を見つけるアルゴリズム)を手作業でトレースする問題。「実行順」という通り道が指定されているので、逆算で a と b の関係を割り出すのがコツ。
なぜ エ が正解か
実行経路を追うと、①でm=a, n=bをセット → ②比較 → ③分岐 → ⑤(m<nのとき n=n−m)→ ②比較 → ③分岐 → ④(m>nのとき m=m−n)→ ②比較 → ⑥終了(m=n)という順番です。つまり「先に n が小さくなり(m<n)、次に m が小さくなり(m>n)、最後に m=n で打ち止め」という3ステップ。具体例で a=2, b=3(3a=2b を満たす)を入れると、m=2,n=3 → n=1 → m=1 → m=n=1 で終了、経路ピッタリ一致。
出典: 基本情報技術者試験 令和5年 公開問題