応用情報技術者試験 令和7年度 春期 午前 問2
0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)＜0≦f(1)を満たすときに、区間内でf(x)＝0であるxの値を近似的に求めるアルゴリズムにおいて、(2)は何回実行されるか。 〔アルゴリズム〕 (1) x₀←0、x₁←1とする。 (2) x←(x₀＋x₁)／2とする。 (3) x₁－x＜0.001ならばxの値を近似値として終了する。 (4) f(x)≧0ならばx₁←xとして、そうでなければx₀←xとする。 (5) (2)に戻る。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】ア
このアルゴリズムは、解を含む区間を半分ずつに狭める二分法です。最初の区間幅は1です。(2)を1回実行すると、中点xは0.5となり、判定に使うx₁－xは1／2です。その後は区間が毎回半分になるので、(2)をn回実行したときのx₁－xは1／2ⁿとなります。
終了条件は1／2ⁿ＜0.001です。9回目では1／2⁹＝1／512≒0.001953となり、まだ条件を満たしません。10回目では1／2¹⁰＝1／1,024≒0.0009766となり、0.001未満です。したがって、(2)の実行回数は10回です。
イの20回は誤りです。20回目では区間の半幅が1／2²⁰となり、必要な精度を大幅に超えて細かくしています。終了判定は10回目で既に成立します。
ウの100回は誤りです。区間を100等分する方法ではなく、1回ごとに半分にする方法なので、100回も必要ありません。
エの1,000回は誤りです。幅0.001を単純に1,000分割する逐次探索の回数と混同した値です。二分法では指数的に区間が狭まります。
【ポイント】 二分法で初期幅Lをn回半分にしたときの幅はL／2ⁿです。本問では中点から端までの距離を判定しているため、1／2ⁿ＜0.001を満たす最小のnを求めます。
出典：令和7年度 春期 応用情報技術者試験 午前 問2
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の80問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる