令和7年度春期応用情報技術者試験午前問2

この問題は2025(R7)春応用情報技術者午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

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

〔アルゴリズム〕

(1) $x_0 \leftarrow 0$ ， $x_1 \leftarrow 1$ とする。
(2) $x \leftarrow (x_0 + x_1) / 2$ とする。
(3) $x_1 - x < 0.001$ ならば $x$ の値を近似値として終了する。
(4) $f(x) \geqq 0$ ならば $x_1 \leftarrow x$ として，そうでなければ $x_0 \leftarrow x$ とする。
(5) (2)に戻る。

ア. 10

イ. 20

ウ. 100

エ. 1,000

解答・解説を読む

正解: 選択肢ア

このアルゴリズムは 二分法（バイセクション法） と呼ばれる、方程式 $f(x) = 0$ の解を近似的に求める手法です。

初期状態として、区間幅は $x_1 - x_0 = 1 - 0 = 1$ です。
(2)の処理で $x$ を区間の中点とするため、(4)を通って次のループに進むごとに区間幅は半分になります。
したがって、 $k$ 回目の(2)が実行された直後の (3)の判定式における $x_1 - x$ （現在の区間幅の半分）は、 $(1/2)^k$ となります。

終了条件は $x_1 - x < 0.001$ すなわち $(1/2)^k < 1/1000$ です。
これを満たす最小の $k$ を求めます。

$2^9 = 512$
$2^{10} = 1024$

よって、条件を満たす最小の整数は $k=10$ です。
したがって、(2)は 10 回実行されます。

各選択肢の解説

ア: 正解です。10回目の実行で判定値が $1/1024$ となり、 $0.001$ を下回るためアルゴリズムは終了します。
イ: 実行回数が20回の場合、判定値は $1/2^{20}$ となり $0.001$ をはるかに下回ります。10回目で既に終了条件を満たすため誤りです。
ウ: 実行回数が100回の場合、終了条件に達した時点でアルゴリズムは終了するため誤りです。
エ: 実行回数が1,000回の場合も同様に誤りです。