応用情報技術者 平成28年秋期 午前問2
[問題文]
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)に戻る。
[解説]
f(x)のxの値は任意です。
この問題はトレースの問題です。
任意のxに対して差分0.001の近似値を求める時、何回アルゴリズムを実行するかという問題です。
x = 0.1としてみましょう。
(1):x0 = 0, x1 = 1, x = 0.5
x1 - x = 0.5 < 0.001
f(0.5) >= 0は、0.1 < 0.5なので真
x1 = 0.5
(2):x0 = 0, x1 = 0.5, x = 0.25
x1 - x = 0.25 < 0.001
f(0.25) >= 0は、0.1 < 0.25なので真
x1 = 0.25
(3):x0 = 0, x1 = 0.25, x = 0.125
x1 - x = 0.125 < 0.001
f(0.125) >= 0は、0.1 < 0.125なので真
x1 = 0.125
(4):x0 = 0, x1 = 0.125, x = 0.0625
x1 - x = 0.0625 < 0.001
f(0.0625) >= 0は、0.1 < 0.0625なので偽
x0 = 0.0625
(5):x0 = 0.0625, x1 = 0.125, x = 0.09375
x1 - x = 0.03125 < 0.001
f(0.03125) >= 0は、0.1 < 0.03125なので偽
x0 = 0.09375
(6):x0 = 0.09375, x1 = 0.125, x = 0.109375
x1 - x = 0.015625 < 0.001
f(0.015625) >= 0は、0.1 < 0.015625なので偽
x0 = 0.109375
(7):x0 = 0.109375, x1 = 0.125, x = 0.1171875
x1 - x = 0.0078125 < 0.001
f(0.0078125) >= 0は、0.1 < 0.0078125なので偽
x0 = 0.1171875
(8):x0 = 0.1171875, x1 = 0.125, x = 0.12109375
x1 - x = 0.00390625 < 0.001
f(0.00390625) >= 0は、0.1 < 0.00390625なので偽
x0 = 0.12109375
(9):x0 = 0.12109375, x1 = 0.125, x = 0.123046875
x1 - x = 0.001953125 < 0.001
f(0.001953125) >= 0は、0.1 < 0.001953125なので偽
x0 =0.123046875
(10):x0 = 0.123046875, x1 = 0.125, x = 0.1240234375
x1 - x = 0.0009765625 < 0.001
終了！
[まとめ]
f(x)のxがどのような値でも10回になるはずです。
テスト中はf(x)の数字の規則性を見つけると早く解けます。
x/2に必ずなるので10回目の商を計算すると終わります。
