応用情報技術者 2016年秋期午前2 問02

問題文

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 < 0.001

ならばxの値を近似値として終了する。　(4)

f (x) \geq 0

ならば

x_{1} \leftarrow x として、そうでなければ

x_0 \gets xとする。　(5) (2) に戻る。

選択肢

ア：10（正解）

イ：20

ウ：100

エ：1,000

$0 \leq x \leq 1$ の範囲で単調増加関数の零点近似【午前2 解説】

要点まとめ

結論：この二分探索法では、区間幅が0.001以下になるまで約10回の反復が必要です。
根拠：初期区間幅1を半分にする操作を繰り返し、 $1/ 2^{n} \leq 0.001$ を満たす $n$ を求めます。
差がつくポイント：二分探索の反復回数は区間幅の対数で決まるため、計算過程を理解し正確に求めることが重要です。

正解の理由

選択肢ア（10回）が正解です。
初期区間幅は1で、各反復で区間幅が半分になります。

n

回の反復後の区間幅は

1/ 2^{n}

です。
これが0.001以下になる条件は、

2^{n} \geq 1000

。

2^{10} = 1024

で条件を満たすため、10回の反復で終了します。

よくある誤解

反復回数を単純に区間幅÷0.001で計算し、1000回と誤解することがあります。
反復回数は区間幅の半減回数（対数）で決まるため、線形計算は誤りです。

解法ステップ

初期区間幅を確認する（ $x_{1} - x_{0} = 1$ ）。
反復ごとに区間幅が半分になることを理解する。
反復回数 $n$ での区間幅は $1/ 2^{n}$ と表せる。
条件 $1/ 2^{n} \leq 0.001$ を対数で解く。
$n \geq lo g_{2} 1000 \approx 9.97$ より、切り上げて10回と判断する。

選択肢別の誤答解説

イ（20回）： $2^{20} = 1, 048, 576$ で過剰な回数。精度0.001には不要。
ウ（100回）：指数的に大きすぎ、計算効率を無視した誤り。
エ（1,000回）：現実的でなく、二分探索の特徴を理解していない。

補足コラム

二分探索法は単調関数の根を効率的に求める基本アルゴリズムです。
反復回数は区間幅の対数に比例し、計算量は

O (lo g \frac{1}{ϵ})

（

ϵ

は許容誤差）となります。
この性質を理解すると、精度と計算時間のバランスを適切に設計できます。

FAQ

Q: なぜ区間幅が半分になるのですか？
A: 中点

x = (x_{0} + x_{1}) /2

で評価し、根が存在する側の区間に絞るため、区間幅が半減します。

Q: 反復回数はどうやって計算しますか？
A:

1/ 2^{n} \leq ϵ

を満たす

n

を対数で求めます。具体的には

n \geq lo g_{2} (1/ ϵ)

です。

関連キーワード: 二分探索法、根の近似、反復回数、計算量、単調関数、数値解析

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2016年 秋期 午前2 問02

問題文

選択肢

0≤x≤1の範囲で単調増加関数の零点近似【午前2 解説】