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 が真なので、x1 ← 0.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 が真なので、x1 ← 0.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 が真なので、x1 ← 0.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 が真なので、x1 ← 0.0625
・・・
上記より、n回目には
(3) x1 − x ＝ 2-n であることが類推される。
210 ＝ 1024 であることから、2-10 < 0.001 であることが判る。
(2-10 ＝ 0.0009765625)
従って、
【10回目】
(3) x1− x ＝ 2-9 - 2-10 ＝ 2-10 < 0.001 で終了する。
| 問１ | 目次 | 問３ |