アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20200726 実施分 問4
0≦x≦1 の範囲で単調に増加する連続関数 f(x) が f(0)＜0≦f(1) を満たすときに，区間内で f(x)＝0 である x の値を近似的に求めるアルゴリズムにおいて，(2) は何回実行されるか。
〔アルゴリズム〕
(1) x_0←0，x_1←1 とする。
(2) x←(x_0+x_1)/2 とする。
(3) x_1−x＜0.001 ならば x の値を近似値として終了する。
(4) f(x)≧0 ならば x_1←x として，そうでなければ x_0←x とする。
(5) (2) に戻る。
- ア 10
- イ 20
- ウ 100
- エ 1,000
出典：基本情報技術者試験 科目A免除 修了試験 20200726 実施分 問4
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
区間を毎回半分にする探索の繰返し回数はlog2(区間幅/精度)程度である。
この問題で必要なこと
(2)を実行するたびに区間が半分になり、(3)で終了するのは1/2^k<0.001となるときで、2^10=1024より k=10回。
ひっかけ
20や100は半減ではなく別の増減を想定させる。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）