問題プレビューID: 44a5d022基本情報技術者試験 午前免除試験 2020年7月26日

問 4
基本情報技術者試験 午前免除試験 2020年7月26日

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] の中点 xx を求め,f(x)f(x) の符号に応じて区間を半分に絞り込む 2 分法です。初期状態では区間の幅は x1−x0=1x_1 - x_0 = 1 であり,処理 (2) を 1 回実行するごとに区間の幅は半分になります。

処理 (2) を kk 回実行したときの x1−xx_1 - x は 1/2k1 / 2^k となるので,終了条件 x1−x<0.001x_1 - x < 0.001 を満たすのは 2k>10002^k > 1000 となる kk です。210=1024>10002^{10} = 1024 > 1000 なので k=10k = 10,すなわち (2) は 10 回実行されます。よって正解は「ア」です。

  • イ・ウ・エ: いずれも 2 分法の収束に要する回数(約 10 回)とは一致しません。

関連問題

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