平成28年度 秋期 応用情報技術者試験 午前 問2

このアルゴリズムは二分法です。(2)で区間の中点を求め，(4)で区間 [x₀, x₁] の幅を半分にしていきます。

最初の区間の幅は1なので，(2)を n 回目に実行した直後の x₁ − x は，区間幅の半分で
x₁ − x = 1 ÷ 2ⁿ
になります。(3)の終了条件は 1 ÷ 2ⁿ ＜ 0.001，つまり 2ⁿ ＞ 1,000 です。
2⁹ = 512，2¹⁰ = 1,024 なので，n = 10 で初めて条件を満たします。したがって(2)は10回実行されます。

• ア: 10
  正しい。10回目の(2)の実行で x₁ − x = 1 ÷ 1,024 ≒ 0.00098 ＜ 0.001 となり終了します。

• イ: 20
  誤り。20回では 1 ÷ 2²⁰ となり，必要以上に区間が狭くなります。10回目の時点で終了します。

• ウ: 100
  誤り。区間を0.001刻みで順に調べる場合の回数に近い値ですが，二分法では毎回幅が半分になるため，はるかに少ない回数で終了します。

• エ: 1,000
  誤り。1 ÷ 0.001 = 1,000 ですが，これは区間を均等に1,000分割して順番に調べる場合の考え方です。

答え

ア: 10