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

ユークリッドの互除法（引き算法）【午前解説】

正解の理由

解法ステップ

1. 初期化：L ← 876, S ← 204。比較回数カウントを0とする。
2. 比較を1回行う（カウント+1）。876 > 204 なので L ← 876 − 204 = 672。
3. 再度比較（カウント+1）：672 > 204 → L ← 468。
4. 比較（カウント+1）：468 > 204 → L ← 264。
5. 比較（カウント+1）：264 > 204 → L ← 60。 ここまで比較4回、減算4回。
6. 比較（カウント+1）：60 < 204 → S ← 204 − 60 = 144。
7. 比較（カウント+1）：60 < 144 → S ← 84。
8. 比較（カウント+1）：60 < 84 → S ← 24。 ここまで比較7回、減算7回。
9. 比較（カウント+1）：60 > 24 → L ← 36。
10. 比較（カウント+1）：36 > 24 → L ← 12。 ここまで比較9回、減算9回。
11. 比較（カウント+1）：12 < 24 → S ← 12。 ここまで比較10回、減算10回。
12. 比較（カウント+1）：12 = 12 → 等号判定で終了。合計比較回数は11回。

選択肢別の誤答解説

• ア: 4
  876 を 204 で4回引いて 60 になる部分だけを見て「4回で終わる」と誤認。以降の処理を無視した誤りです。
• イ: 9
  商を使って 4 + 3 + 2 = 9 とまとめて考えた誤り。最後の群で等しくなるため、単純に商の和を比較回数と同一視できません。
• ウ: 10
  実際の減算回数（10）を比較回数と混同した誤り。問題は「比較が何回行われるか」を問うため、最後の等号判定を含める必要があります。
• エ: 11（正解）
  上の手順で示した通り、減算10回に最後の等号比較1回を加えた合計が比較回数となります。

よくある誤解

• 減算回数だけを数えて「10回だからウ（10）」とする誤り。問題は比較回数を問うため、最後の等号判定を含める必要があります。
• 最初のグループ（876÷204＝4）だけ見て「4回で終了＝ア（4）」と早合点する誤り。以降の値のやり取りを追わないと誤ります。
• 商を単純に足して9（4+3+2）としてしまう誤り（イ:9）。最後の群で途中で等しくなる場合があり、単純和だけでは比較回数になりません。

補足コラム

FAQ