二分法の繰返し回数
出典: 令和7年度 春期 応用情報技術者試験 午前 問2 (IPA)
0 ≦ x ≦ 1 の範囲で単調に増加する連続関数 f(x) が f(0) ＜ 0 ≦ f(1) を満たすときに，区間内で f(x) ＝ 0 である x の値を近似的に求めるアルゴリズムにおいて，(2) は何回実行されるか。
〔アルゴリズム〕
(1) x₀ ← 0，x₁ ← 1 とする。
(2) x ← (x₀＋x₁)/2 とする。
(3) x₁ − x ＜ 0.001 ならば x の値を近似値として終了する。
(4) f(x) ≧ 0 ならば x₁ ← x として，そうでなければ x₀ ← x とする。
(5) (2) に戻る。
- ア 10
- イ 20
- ウ 100
- エ 1,000
正解と解説を見る
正解: ア
- ア: 区間が毎回半分になり、10 回で 1 ÷ 1,024 ＜ 0.001 となるので正しい答えです。
- イ: 20 回では、区間は 1 ÷ 2²⁰ ≒ 0.000001 まで小さくなります。10 回目ですでに終了しています。
- ウ: 100 回は、区間を毎回 0.01 ずつ縮めるような場合の回数です。二分法では毎回半分になります。
- エ: 1,000 回は、区間を 0.001 ずつ順に調べる場合の回数です。二分法では毎回半分になります。
ポイント
- このアルゴリズムは 二分法 です。解がある区間を毎回半分にしていきます。
- (2) を n 回実行したとき、x₁ − x は 1 ÷ 2ⁿ になります。これが 0.001 未満になれば終了します。
- 2¹⁰ = 1,024 なので、1 ÷ 1,024 ＜ 0.001 となる 10 回 で終わります (2⁹ = 512 では 1 ÷ 512 ≒ 0.002 でまだ終わりません)。