基本情報技術者 2023年 科目A 問11

3回の差の更新で一致させる関係【午前解説】

正解の理由

解法ステップ

1. 初期は m=a, n=b。最初の比較で m≠n かつ m<n である必要がある。よって $a<b$。
2. m<n のとき実行されるのは n ← n − m なので、更新後は $m=a,n=b-a$（ここで $b-a>0$）。
3. 再び比較して今度は m>n になり、m ← m − n が実行されるため $a>b-a\Rightarrow 2a>b$（これで $m=a-(b-a)=2a-b>0$）。
4. その後 m と n が等しくなる必要があるため $2a-b=b-a$ を解くと $3a=2b$。
5. 条件 $a<b$ と $2a>b$ を同時に満たす正の整数解は $a=2t,b=3t(t\in {\mathbb{Z}}_{>0})$ の形になる。最小例は $(a,b)=(2,3)$。

選択肢別の誤答解説

• ア: $a=2b$
  これは $a>b$ となるため初回比較で m>n の経路を通り、図が要求する m<n → n←n−m の順序になりません。よって不適。
• イ: $2a=b$
  この場合 $b=2a$ で初回は確かに $a<b$。しかし n←n−m を一回行うと $n=b-a=a$ になり、直後に m=n になって出力に行ってしまい、図で要求される「先に n を減らし、その後 m を減らす」一連の2段更新の順序になりません。
• ウ: $2a=3b$
  これは $a=1.5b$ で $a>b$ となり、初回比較で m>n の経路（mを先に減らす）になってしまい、問題の通る順序と合いません。
• エ: $3a=2b$
  上の解法ステップで導かれる条件と一致します。例えば $(a,b)=(2,3)$ を代入すると (2,3) → n←1 → m←1 → (1,1) と順に進み、図の示すノード順になることが確認できます。

よくある誤解

• 「最初の比較で m:n と書かれた菱形は同じ判定しかしていない」と誤解して、どのノードが等号・不等号のどれを担当するかを混同する。図中は最初の菱形が等＝か否か、右側の菱形が大小の分岐を決める点に注意すること。
• 更新後の戻り先が別の比較ノード（③）だと思い込み、どの時点で等号判定が行われるかを誤ると順序条件を取り違える。ループは更新後に最初の判定（②）へ戻る点を踏まえる。
• 符号や不等式を扱う際、更新後の値が正であることを確認しないまま式を立ててしまい、途中で負やゼロが出る可能性を見落とす（本問は正の整数であることが前提）。

補足コラム

FAQ