近似値を求めるアルゴリズム｜科目A-1（応用情報技術者） 令和7年 春期午前試験 問2
出典：令和7年春期 午前 問2
分野：基礎理論（中分類） ／ 応用数学
0 ≦ x ≦ 1の範囲で単調に増加する連続関数 ƒ(x) が ƒ(0) ＜ 0 ≦ ƒ(1) を満たすときに，区間内で ƒ(x) = 0 であるxの値を近似的に求めるアルゴリズムにおいて，（2）は何回実行されるか。
〔アルゴリズム〕
（1）x0 ← 0，x1 ← 1とする。
（2）x ←（x0 + x1）/2とする。
（3）x1 - x ＜ 0.001ならばxの値を近似値として終了する。
（4）ƒ(x)≧0ならばx1 ← xとして，そうでなければx0 ← xとする。
（5）（2）に戻る。
- ア：10
- イ：20
- ウ：100
- エ：1,000
TSUNAGARU-ADVICE
まず押さえたいこと
このアルゴリズムは、区間の中央を調べて探索範囲を半分ずつ狭めていく二分法です。繰返し回数を考えるときは、初期の区間幅が、1回ごとに1 / 2になっていくことに注目します。
迷ったときの判断軸
終了条件は関数値の大きさではなく、探索区間の幅が指定値より小さくなることです。そのため、初期区間幅を何回半分にすれば条件を満たすかを考えます。「半分にする操作の回数」と「中央点を計算する（2）の実行回数」を対応させて数えることがポイントです。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、二分法を探索範囲を指数的に縮小していくアルゴリズムとして理解しましょう。二分探索や計算量の評価、数値計算アルゴリズムの収束回数を考える問題にもつながります。
このアルゴリズムは、区間を半分ずつに狭めて解を近似する二分法です。
（2）を1回実行するたびに、探索区間の長さは半分になります。また、xは区間の中点なので、判定に用いるx1 - xは、その時点の区間の長さの半分です。
（2）をn回実行したとき、x1 - xは次のようになります。
x1 - x = 1 ÷ 2n
終了条件は、x1 - x < 0.001です。
n = 9のとき、1 ÷ 29 = 1 ÷ 512 ≒ 0.001953となり、0.001未満ではありません。
n = 10のとき、1 ÷ 210 = 1 ÷ 1,024 ≒ 0.000977となり、0.001未満になります。
したがって、（2）は10回実行されます。
したがって、アが適切です。