平成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)に戻る。
出典：平成28年度 秋期 応用情報技術者試験 午前 問2
- ア10
- イ20
- ウ100
- エ1,000
正解：ア
解説
このアルゴリズムは区間[0,1]を毎回半分に狭める二分法です。初期の区間幅は1で，(2)を1回実行するごとに区間幅は半分になります。区間幅が0.001未満になるまで繰り返すので，1/2ⁿ＜0.001を満たす最小のnを求めると，2¹⁰＝1024＞1000より，n＝10回で条件を満たします。
選択肢ごとの解説
- ア正しい。区間幅は1回ごとに半分になり，2¹⁰＝1024＞1000なので10回の実行で区間幅が0.001未満になります。
- イ誤り。20回では区間幅は1/2²⁰程度まで狭まり，必要以上に細かくなります（1/2¹⁰の時点で既に条件を満たします）。
- ウ誤り。100回は不要に多い回数で，二分法の収束の速さ（1回ごとに半分）を考慮していません。
- エ誤り。1,000回は明らかに過大で，桁数の0.001と回数を混同した誤りと考えられます。