令和1年度 春期 基本情報技術者 午前 問7

この手順をA=876, B=204で実行すると、

1回目: 876 - 204 = 672 (A=672, B=204)

2回目: 672 - 204 = 468 (A=468, B=204)

3回目: 468 - 204 = 264 (A=264, B=204)

4回目: 264 - 204 = 60 (A=60, B=204)

5回目: 204 - 60 = 144 (A=60, B=144)

6回目: 144 - 60 = 84 (A=60, B=84)

7回目: 84 - 60 = 24 (A=60, B=24)

8回目: 60 - 24 = 36 (A=36, B=24)

9回目: 36 - 24 = 12 (A=12, B=24)

10回目: 24 - 12 = 12 (A=12, B=12)

ここでAとBが等しくなったため、処理は終了します。この間に実行された比較（あるいは引き算）の回数は10回です。しかし、問題文は「何回の比較で処理は終了するか」と問うています。ユークリッドの互除法では、一般的に「AとBが等しくなったとき」または「一方の数が0になったとき」に終了します。上記の例では、10回の引き算でA=12, B=12となり、ここで比較して等しいと判断し終了します。もし、もう1回比較（A=12, B=12）を行うとすると、11回目の比較で終了することになります。問題文の「比較」を、AとBの値が等しいかどうかを判断する行為と解釈すると、10回の引き算の結果、A=12, B=12となり、この時点で「AとBは等しい」という比較を行い、終了するため、合計11回の比較が必要と解釈できます。

アの4回は、初期の段階での引き算回数に過ぎず、誤りです。

イの9回も、誤った回数計算によるものです。

ウの10回は、引き算の回数としては正しいですが、「比較」の最終段階を考慮すると不足しています。