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

二分法(バイセクション法)では、1回の反復ごとに探索区間の幅が半分になります。 初期の探索区間は [0, 1] であり、幅は 1 - 0 = 1 です。 (2) で中央値 x ← (x0 + x1) / 2 を計算し、(3) で x1 - x < 0.001 を判定します。 1回目の (3) 判定時点での x1 - x の値は、(1 - 0) / 2 = 1/2 です。 k 回目の実行後の判定値は (1/2)^k となります。 終了条件 x1 - x < 0.001 (= 1/1000) を満たす最小の整数 k は、2^10 = 1024 > 1000 より (1/2)^10 = 1/1024 < 1/1000 となるため、k = 10 です。 したがって、(2) は 10 回実行されます。 正解は ア です。 ア:正しい。2^10 = 1024 であるため、10回目の実行後に区間幅が 1/1024 ≒ 0.0009765 < 0.001 となり終了します。 イ:20回実行すると区間幅は約 1/1,000,000 になり、終了条件をはるかに超えてしまいます。 ウ:100回は誤りです。 エ:1,000回は誤りです。

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年度 春期 高度情報処理技術者試験 午前Ⅰ
ア
10
イ
20
ウ
100
エ
1,000