高度情報処理技術者試験・情報処理安全確保支援士試験 令和7年度 春期 午前I 問1
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までの幅x₁－xは1／2になります。（4）では、f(x)の符号に応じてx₀又はx₁を中点に置き換えるので、次の区間幅も直前の半分になります。したがって、（2）をn回実行した直後のx₁－xは1／2ⁿです。
9回目では1／2⁹＝1／512＝0.001953125であり、0.001未満ではありません。10回目では1／2¹⁰＝1／1,024＝0.0009765625となり、初めて終了条件を満たします。よって、（2）の実行回数は10回です。
イの20回は誤りです。20回目まで進めば区間は更に狭くなりますが、このアルゴリズムは10回目で既に終了します。
ウの100回は誤りです。二分法では区間幅が指数的に減少するため、100回もの反復は必要ありません。
エの1,000回は誤りです。0.001の逆数をそのまま反復回数とした値であり、区間を毎回0.001ずつ縮める線形な方法と混同しています。
【ポイント】 二分法では、n回の反復後の区間幅は初期幅の1／2ⁿになります。 終了条件が「未満」か「以下」かにも注意し、境界付近では実際の値を比較します。 必要回数は、2ⁿが初期幅と許容誤差の比を超える最小のnとして求められます。
出典：令和7年度 春期 高度情報処理技術者試験・情報処理安全確保支援士試験 午前I 問1
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の30問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる