本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成28年度 秋期 高度情報技術者試験問題と解説

問1

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

〔アルゴリズム〕

(1) x0 ← 0、x1 ← 1とする。

(2) x ← (x0 + x1) / 2 とする。

(3) x1 - x < 0.001ならば x の値を近似値として終了する。

(4) f(x) ≧ 0ならば x1 ← x として、そうでなければ x0 ← x とする。

(5) (2)に戻る。

ア 10  イ 20  ウ 100  エ 1,000


正解


解説

題意より、f(0) < 0 であるが、ある x の値を境にして、0 ≦ f(x) となる。
どの値で f(x) = 0 となるか分からないので、x = 0.000001 の時に f(x) = 0 として考えてみる。

(1) x0 ← 0、x1← 1
【1回目】
(2) x ← (0+1)/2 = 0.5
(3) x1 − x = 1 − 0.5 = 0.5 = (2-1)
(4) f(0.5) ≧ 0 が真なので、x10.5

【2回目】
(2) x ← (0+0.5)/2 = 0.25
(3) x1 − x = 0.5 − 0.25 = 0.25 = (2-2)
(4) f(0.25) ≧ 0 が真なので、x10.25

【3回目】
(2) x ← (0+0.25)/2 = 0.125
(3) x1 − x = 0.25 − 0.125 = 0.125 = (2-3)
(4) f(0.125) ≧ 0 が真なので、x10.125

【4回目】
(2) x ← (0+0.125)/2 = 0.0625
(3) x1 − x = 0.125 − 0.0625 = 0.0625 = (2-4)
(4) f(0.0625) ≧ 0 が真なので、x10.0625

・・・

上記より、n回目には
(3) x1 − x = 2-n であることが類推される。

210 = 1024 であることから、2-10 < 0.001 であることが判る。
(2-10 = 0.0009765625)

従って、
【10回目】
(3) x1− x = 2-9 - 2-102-10 < 0.001 で終了する。

目次 問2