応用情報技術者試験 応用情報技術者試験 令和7年度春期 午前 問2: 0 ≦ x ≦ 1 の範囲で単調に増加する連続関数 f(x) が f(0)＜0 ≦ f(1) を満たすときに，区間内で f(x)＝0 である x の値を近似的に

問題本文

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)に戻る。

選択肢

• ア.10
• イ.20
• ウ.100
• エ.1,000

正解

ア. 10

解説

これは区間を半分ずつ狭めて解に近づける二分法（バイナリサーチと同じ原理）で、毎回 (2) で区間の中点 x を求めます。x は x0 と x1 の中点なので、x1 と x の差は常に区間幅 x1－x0 のちょうど半分です。区間幅は最初 1（=1－0）で、ループのたびに半分になるため、k 回目の (2) 実行後の x1－x は 1/2^k となります。終了条件 x1－x＜0.001 を満たすのは 1/2^k＜0.001、すなわち 2^k＞1,000 のときで、2^10＝1,024＞1,000 より k＝10。したがって (2) は 10 回実行され、正解はアです。