問題
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) に戻る。
選択肢
- 110
- 220
- 3100
- 41,000
正解
1. 10
詳しい解説を見る解説を閉じる
解説
これは二分法のアルゴリズムである。最初の区間幅は 1 で、(2) を 1 回実行するごとに区間幅が半分になる。終了条件は x₁−x＜0.001、すなわち区間幅が 0.001 未満になることである。n 回実行後の区間幅は 1/2ⁿ であり、1/2ⁿ＜0.001 となる最小の n を求める。2¹⁰＝1024＞1000 なので n＝10 で初めて 1/2¹⁰＜0.001 を満たす。よって (2) は 10 回実行され、アが正解。（出典: 平成28年度 秋期 応用情報技術者試験 午前 問2）
一問一答
全400問を繰り返し学習