問題プレビューID: c0fb62a3応用情報技術者試験 2016年(平成28年度)秋期 午前

問 2
応用情報技術者試験 2016年(平成28年度)秋期 午前

0≦x≦10 \leqq x \leqq 1 の範囲で単調に増加する連続関数 f(x)f(x) が f(0)<0≦f(1)f(0) < 0 \leqq f(1) を満たすときに,区間内で f(x)=0f(x) = 0 である xx の値を近似的に求めるアルゴリズムにおいて,(2) は何回実行されるか。

〔アルゴリズム〕

  • (1) x0←0x_0 \leftarrow 0,x1←1x_1 \leftarrow 1 とする。
  • (2) x←x0+x12x \leftarrow \dfrac{x_0 + x_1}{2} とする。
  • (3) x1−x<0.001x_1 - x < 0.001 ならば xx の値を近似値として終了する。
  • (4) f(x)≧0f(x) \geqq 0 ならば x1←xx_1 \leftarrow x として,そうでなければ x0←xx_0 \leftarrow x とする。
  • (5) (2) に戻る。
解説

正解は「ア」です。

このアルゴリズムは,区間 [x0,x1][x_0, x_1] の中点を求めて解を含む側の区間を選び直し,区間を半分に絞り込んでいく 2 分法です。初期状態では x1−x0=1x_1 - x_0 = 1 で,(2) を 1 回実行するごとに区間の幅は半分になります。

(2) を実行した直後は xx が区間の中点なので,x1−xx_1 - x は区間幅の半分です。kk 回目の実行では x1−x=1/2kx_1 - x = 1 / 2^k となり,(3) の条件 x1−x<0.001x_1 - x < 0.001 を満たすのは

1/2k<0.001  ⟺  2k>10001 / 2^k < 0.001 \iff 2^k > 1000

となる最小の kk です。29=5122^{9} = 512,210=10242^{10} = 1024 なので k=10k = 10 となります。

  • イ: 20 回は計算が過剰で,2202^{20} までの精度は不要です。
  • ウ・エ: 100 回や 1,000 回も不要で,10 回で十分な精度に達します。

よって正解は「ア」です。

関連問題

本文が同じ・似ている問題を表示しています