メインコンテンツへ
アルゴリズムとプログラミング

次の流れ図において、①→②→③→⑤→②→③→④→②→⑥ の順に実行させるために、①において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 で終了、経路ピッタリ一致。

なぜ ア は間違いか

a=2b(例: a=4,b=2)だと最初から m>n なので、⑤(m<n用)には一切寄り道せず ④→⑥ で早期終了。⑤を通る経路にならないので不正解。大きいものしかいない部屋に『小さい側担当』が呼ばれることはない。

なぜ イ は間違いか

2a=b(例: a=2,b=4)だと最初は m<n で正しく⑤を通るが、そのまま m=n になって終了。「⑤→⑥」の2ステップで終わり、④をスキップしてしまう。もう1周足りない。

なぜ ウ は間違いか

2a=3b(例: a=3,b=2)だと最初 m>n なので ④ → 次に m<n で ⑤ → 終了、という順序になり、問題の「⑤が先・④が後」とは逆順になる。正しいロジックだが鏡に映したように左右反転。もどかしい。

出典: 基本情報技術者試験 令和5年 公開問題