令和7年度 春期 応用情報技術者試験 午前 問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) に戻る。
出典：令和7年度 春期 応用情報技術者試験 午前 問2
- ア10
- イ20
- ウ100
- エ1,000
正解：ア
解説
これは区間を半分ずつ狭めていく二分法のアルゴリズムです。(2) を n 回目に実行した直後の x1−x は区間幅の半分に当たり，1回目は 1/2，2回目は 1/4，…，n 回目は 1/2ⁿ になります。終了条件 1/2ⁿ ＜ 0.001 を満たす最小の n は，1/2⁹＝0.00195…，1/2¹⁰＝0.00097… より n＝10 なので，(2) は 10 回実行されます。
選択肢ごとの解説
- ア正しい。1/2¹⁰＝約0.00098 で初めて 0.001 を下回るので，(2) の実行回数は 10 回です。
- イ誤り。20 は，要求精度を 0.001 ではなく 10⁻⁶ 程度と取り違えた場合の回数に近い値です。
- ウ誤り。100 は，1 回の実行で区間が半分になるのではなく 0.01 ずつ狭まると考えた場合の値です。
- エ誤り。1,000 は，区間 [0,1] を 0.001 刻みで先頭から線形に探索すると考えた場合の回数で，二分法の反復回数ではありません。