二分法の繰返し回数
出典: 平成28年度 秋期 応用情報技術者試験 午前 問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 でまだ終わりません)。