応用情報技術者 2020年 秋期 午前2 問47

逐次減算の遷移【午前2解説】

正解の理由

解法ステップ

• m = a, n = b （a,b は正の整数）

1. 最初の判断（②）で右へ進み③に入るには m ≠ n かつ m < n が必要
   • よって条件1： $a<b$ （かつ $a\ne b$、しかし正整数なので $<$ で十分）
2. ③で m < n の場合（右へ）⑤を実行：n ← n − m
   • ⑤の後の値を記すと、m = a, n = b − a（ここを n1 と置く）
   • 以降の判断で再び③に入るためには、②で m ≠ n1 が必要（つまり $a\ne b-a$）
3. 次に③で下へ（④）に入るには m > n1 が必要
   • よって条件2： $a>b-a$（すなわち $2a>b$）
4. ④を実行すると m ← m − n1
   • ④の後の値は m = a − (b − a) = $2a-b$（これを m1 とする）、n は n1 = $b-a$
5. 最後に②で等号の下辺（下へ）に行って⑥へ至るには m1 = n1 が必要
   • よって条件3： $2a-b=b-a$
6. 条件3を整理すると
   • $2a-b=b-a\Rightarrow 3a=2b$

• $3a=2b$ を満たすとき、a,b は正整数なので存在するパラメータ表示 $a=2k,b=3k$（$k\in {\mathbb{Z}}_{>0}$）が得られます。
• この一般形は条件1（$a<b$）、条件2（$a>b-a$）および各中間値が正であることを自動的に満たします。したがって、実行順を満たす初期関係は $3a=2b$（選択肢 エ）です。

• 最小の $k=1$ で $a=2,b=3$ を取ると、 ① m=2,n=3 → ②: 2<3 → ③: ＜ → ⑤: n=1 → ②: 2≠1, 2>1 → ③: ＞ → ④: m=1 → ②: 1=1 → ⑥（終了）。順序が一致します。

選択肢別の誤答解説

• ア: $a=2b$
  これだと $a>b$ となり、最初の比較で m>n（④へ）になってしまい、所望の右側ルート（⑤を先に実行する）に入らないため不適。
• イ: $2a=b$（すなわち $b=2a$）
  これは初期で $a<b$（良い）が、⑤を実行すると $n=b-a=a$ となり、次の②で既に m=n になってしまうため（すぐに⑥へ）、要求されるループ（③→⑤→…→④）を経ない。
• ウ: $2a=3b$（すなわち $a=1.5b$）
  これだと $a>b$ になり、最初の比較が下辺（④）へ進むため、最初に③→⑤の経路をとらない。したがって順序が合致しない。
• エ: $3a=2b$
  上記の解法ステップで示した通り、各比較の不等号の向きと変数更新が矛盾なくつながり、求める実行順を満たす。

よくある誤解

• 初期の比較で「等しくない＝右へ進む」が要件なだけだと誤解して、どちらの不等号（＜か＞）になるかを追わない。実行順を得るには不等式の向き（＜か＞か）まで確定する必要があります。
• 変数更新を忘れる／取り違える（例えば⑤で m を変えると誤認する）。⑤は n を更新し、④は m を更新します。どちらが変わるかを正確に追うことが重要です。
• 整数性や正の条件を確認しない。導出された関係が整数解を持つか（例：$3a=2b$ は $a=2k,b=3k$）を確認しないと、実際の初期値候補が存在するか不明瞭になります。

補足コラム

FAQ