AP過去問令和7年度春期午前問2

問2(問題文)

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

[アルゴリズム]

(1) $x_0 \leftarrow 0$ 、 $x_1 \leftarrow 1$ とする。

(2) $x \leftarrow \frac{x_0+x_1}{2}$ とする

(3) $x_1 - x \lt 0.001$ ならば $x$ の値を近似値として終了する。

(4) $f(x) ≧ 0$ ならば $x_1 \leftarrow x$ として、そうでなければ $x_0 \leftarrow x$ とする。

(5) (2)に戻る。

ア　10

イ　20

ウ　100

エ　1000

この問題は、関数の値が0になる点を二分探索法によって近似的に求めるアルゴリズムの繰り返し回数について問うものです。アルゴリズムでは、探索区間を毎回半分にしていくため、何回繰り返せば区間の長さが0.001未満になるかを計算すれば答えが出ます。

初期状態では、区間の長さは $x_1−x_0=1−0=1$ です。

アルゴリズムは1回ごとに区間を半分にしていくので、n回後には区間の長さが $\frac{1}{2^n}$ になります。

この長さが0.001未満になる必要があるため、次の不等式を解きます。

$\frac{1}{2^n} \lt 0.001$

両辺の逆数をとると

$2^n＞1000$

この不等式を満たす最小のnを求めます。

$2^{10}=1024 \gt 1000$

よって、 $n = 10$ で条件を初めて満たすことになります。

したがって、(2)は10回実行されます。

　したがって

ア

　が答えです。