二分法による方程式の近似解法

正解は ア です。 二分法は、解がある区間 $[x_0, x_1]$ を中点 x で半分に分け、f(x) の符号で解のある側を残す操作を繰り返します。(2) を1回実行するごとに $x_1 - x$(区間の半分の幅)が半分になります。 (2)の実行回数 k 1 2 3 … 9 10 $x_1 - x$ 1/2 1/4 1/8 … 1/512≒0.00195 1/1024≒0.00098 (3)で終了? × × × … × ○(0.001未満) $2^{10}=1024>1000$ なので、10回目で初めて $x_1 - x < 0.001$ となり終了します。 20回では幅が約 $1/10^6$ になります。終了条件は10回目で満たされるので、20回までは実行されません。 幅が100分の1ずつ小さくなると考えた値ですが、二分法は1回ごとに半分になります。 線形探索のように 0.001 刻みで調べた場合の回数です。

0≦x≦10 \leqq x \leqq 1 の範囲で単調に増加する連続関数 f(x) が f(0)<0≦f(1)f(0) < 0 \leqq f(1) を満たすときに,区間内で f(x)=0f(x) = 0 である x の値を近似的に求めるアルゴリズムにおいて,(2) は何回実行されるか。

〔アルゴリズム〕 (1) x0←0x_0 \leftarrow 0,x1←1x_1 \leftarrow 1 とする。 (2) x←x0+x12x \leftarrow \frac{x_0 + x_1}{2} とする。 (3) x1−x<0.001x_1 - x < 0.001 ならば x の値を近似値として終了する。 (4) f(x)≧0f(x) \geqq 0 ならば x1←xx_1 \leftarrow x として,そうでなければ x0←xx_0 \leftarrow x とする。 (5) (2) に戻る。

出典令和7年度 春期 応用情報技術者試験 午前 問2
ア
10
イ
20
ウ
100
エ
1,000