システムアーキテクト 2010年 午前2 問11

ユークリッド互除法【午前2解説】

正解の理由

1. 最初に m < n であること（⑤へ進むため）
2. ⑤後の新しい n' = n − m に対して m > n' であること（次に④へ進むため）

解法ステップ

1. フローチャートの分岐から、指定の実行順序が示す「最初は⑤（n ← n − m）が先に来る」＝初期で $m<n$ を導く。
2. ⑤実行後に次の分岐で④（m ← m − n）が来るために、⑤後の $n^{\prime }=n-m$ に対して $m>n^{\prime }$ が必要。
3. $m>n-m$ を整理して $2m>n$ を得る。
4. 1 と 3 を合わせて $m<n<2m$。これを $a,b$ に置き換えると $a<b<2a$。
5. 選択肢を比べ、$a<b<2a$ を満たすものが正解。$3a=2b$ は $b=1.5a$ で条件を満たすため正解（エ）。

• ① m=2,n=3
• ② m≠n → ③ m<n → ⑤ n←3−2=1
• ② m≠n → ③ m>n → ④ m←2−1=1
• ② m=n → ⑥ 印字 → 終了
  順序は問題の示す通りになります。

選択肢別の誤答解説

• ア: a = 2
  • 単に $a=2$ と定めるだけでは $b$ に関する情報がなく、$a<b<2a$ を保証しないため実行順序を確定できない。設問が求める「a と b の関係」になっていない。
• イ: $2a=b$
  • ここで $b=2a$、すなわち $n=2m$ なので初期は $m<n$（⑤へ進む）。しかし⑤後は $n^{\prime }=n-m=2a-a=a$ となり $n^{\prime }=m$ で等しくなる。したがってその後は④に進むのではなく、②で等号判定を経て即座に⑥（終了）に向かう。要求される順序（⑤の後に④が来る）は満たさない。
    -（注意）誤って「この場合は最初に $m>n$ となる」とする記述がしばしば見られますが、正しくは $m<n$ です。
• ウ: $2a=3b$
  • これは $b=\frac{2}{3}a$、すなわち $n<m$ の初期状態を意味するため、初めから④（m ← m − n）が実行される。したがって指定の順序と合致しない。
• エ: $3a=2b$
  • $b=\frac{3}{2}a$ より $a<b<2a$ を満たし、上で導いた条件と一致する。したがって指定の実行順序を実現する。

よくある誤解

• 2a = b のときに m > n になると誤認する
  • 実際は $n=2m$ であり初期は $m<n$。等号が生じるのは⑤実行後である点を見落としやすい。
• フローチャートの矢印方向と比較符号の対応を取り違える
  • 「<」が右へ行く、」「>」が下へ行く等、図の方向を正確に追うことが重要。
• 実行順序の記述とループ回数を混同する
  • 「どの分岐を通るか」を先に決め、各分岐での変化後の不等式を順に検証すること。

補足コラム

FAQ