応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問2: 0 ≦ x ≦ 1 の範囲で単調に増加する連続関数 f(x) が f(0) < 0 ≦ f(1) を満たすとき，区間内で f(x) = 0 である x の値を近

問題本文

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

解説

区間を半分に絞り込む二分法(2分探索の発想)の反復回数を問う問題。このアルゴリズムは区間 [x₀, x₁] を毎回 x=(x₀+x₁)/2 で2分し、解のある側に区間を狭めていく。区間幅は最初 1 で、(2)を実行して中央を取り (4) で片側に絞るたびに半分(1→1/2→1/4→…)になる。終了条件 x₁−x < 0.001 は、中央 x までの幅すなわち区間幅の半分が 0.001 未満になることを意味する。区間幅を半分にする操作を n 回行うと幅は 1/2ⁿ で、その半分 1/2ⁿ⁺¹ < 0.001 となる最小の n を求めると、2¹⁰=1024 より 1/2¹⁰≒0.000976 < 0.001 が成立する。したがって (2) はおよそ10回実行され、正解はアである。選択肢は数値のみで個別比較に学習価値が薄いため選択肢別解説は省略する。