問題プレビューID: aa0cecb0応用情報技術者試験 2025年(令和7年度)春期 午前

問 2
応用情報技術者試験 2025年(令和7年度)春期 午前

0≤x≤10 \le x \le 1 の範囲で単調に増加する連続関数 f(x)f(x) が f(0)<0≤f(1)f(0) < 0 \le 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) \ge 0 ならば x1←xx_1 \leftarrow x として,そうでなければ x0←xx_0 \leftarrow x とする。
  • (5) (2) に戻る。
解説

正解は「ア」です。

2 分法(二分探索)によって方程式の解を求めるアルゴリズムです。初期状態は x0=0x_0 = 0,x1=1x_1 = 1 なので,区間の幅は x1−x0=1x_1 - x_0 = 1 です。

(2) で区間の中点 x=x0+x12x = \dfrac{x_0 + x_1}{2} を求め,(4) で解が含まれる側に区間を半分に狭めます。このとき xx は区間の中点なので,x1−xx_1 - x は区間の幅の半分になります。したがって,(2) を kk 回実行した直後は x1−x=12kx_1 - x = \dfrac{1}{2^k} となります。

(3) の終了条件 x1−x<0.001x_1 - x < 0.001 を満たすのは,12k<0.001\dfrac{1}{2^k} < 0.001,すなわち 2k>10002^k > 1000 となる最小の kk です。210=1024>10002^{10} = 1024 > 1000 より k=10k = 10 となり,(2) は 10 回実行されます。

  • イ・ウ・エ: 1 回の繰返しで区間の幅が半分になることを考慮していない値です。

関連問題

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