応用情報技術者試験令和7年春午前問2 解説付き過去問

問題

0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0) ＜ 0 ≦ f(1)を満たすときに、区間内でf(x)＝0であるxの値を近似的に求めるアルゴリズムにおいて、 (2)は何回実行されるか。

〔アルゴリズム〕

100

1,000

この問題は、与えられた区間内で関数の根を見つけるための二分探索アルゴリズムの動作を理解し、特定の条件下でステップ（2）が実行される回数を求めることに関するものです。

二分探索アルゴリズムの基本原理
二分探索アルゴリズムは、指定された範囲内で目的の値（この場合は f(x)=0）を見つけるために、範囲を反復的に半分に分割していきます。
初期値として x₀=0、x₁=1 が与えられ、中点 x は x₀＋x₁2 で計算されます。この中点が関数 f(x) の値によって次の探索範囲が決定され、x₀ または x₁ が更新されます。
アルゴリズムの停止条件
アルゴリズムの停止条件は、x₁ と x の差が 0.001 未満になる場合です。この条件が満たされると、x は f(x) = 0 の近似解として受け入れられます。
二分探索では、各ステップで探索範囲が半分になるため、精度が指数的に向上します。ここで、x₁ と x₀ の初期差は 1 であり、0.001 に達するまでには、おおよそログ2ベースで計算すると log(0.001)log(0.5) 回の繰り返しが必要です。この計算結果は約10回になります。

したがって、このアルゴリズムにおいてステップ（2）は約10回実行されることが期待され、これが正解です。