基本情報技術者 2013年 春期 午前（科目A） 問08

自然数の流れ図処理【午前解説】

正解の理由

解法ステップ

1. 初期化を確認：$q\leftarrow 0,r\leftarrow x$ を把握する。
2. 判定条件を読む：条件は $r<y$。Yes で終了、No で $r\ge y$ のとき処理が進む。
3. ループ処理を確認：No 側で $r\leftarrow r-y,q\leftarrow q+1$ を行い判定へ戻る。
4. 不変式を導く：各ループ後に $x=q\times y+r$ が成り立つことを確認する。
5. 終了条件で $0\le r<y$ が得られ、q が商、r が余りであると結論付ける。

選択肢別の誤答解説

• ア：q を「x ÷ y の余り」、r を「x ÷ y の商」としているが、流れ図では q が繰り返し加算され商に相当し、r が引かれて小さくなる余りなので逆です。
• イ：正解。q が $x÷y$ の商、r が余りです。
• ウ：y ÷ x としているため除算の方向が逆です。流れ図は x から y を引くので x÷y を扱っています。
• エ：ウと同様に除数と被除数が逆になっており、さらに商・余りの位置も逆です。

よくある誤解

• 誤解1：判定の Yes/No を見誤り、ループの方向（終了が右、繰り返しが下）を逆に解釈する。これで商と余りが入れ替わる誤答が出ます。
• 誤解2：変数名の意味（q が積算される回数＝商）を見落とし、q を余りと考えてしまう。流れを追って増減を確認すれば防げます。
• 誤解3：$y=0$ のケースを考えずに除算と同じ扱いを想定すると無限ループや未定義扱いになる点を見落とす。

補足コラム

• 擬似コード例（理解確認用）：

q = 0
r = x
while not (r < y):   # つまり r >= y の間
    r = r - y
    q = q + 1
# 終了後: q は商, r は余り

• ループ回数は最終的に q 回であり、計算量は $O(q)$（繰り返し引き算の回数）。効率的な整数除算アルゴリズムと比べると非効率ですが、原理的に正しい方法です。
• 注意：$y=0$ の場合は除算にならず、このフローは無限ループあるいは未定義の扱いになります。通常は $y\ge 1$ を前提とします。

FAQ