令和7年度春期 応用情報技術者試験 午前 問2
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
解答・解説を見る
正解：ア
AI解説
このアルゴリズムでは、(2)を1回実行するごとに探索区間の幅がそれまでの半分になる。初期の区間幅は1であり、n回目の(2)実行時点でのx1-xの値は1/2^nとなる。1/2^n<0.001を満たす最小のnを求めると2^10=1024>1000より10回で条件を満たすため、(2)は10回実行される。 ア: 正しい。1/2^n<0.001を満たす最小のnは10であり、(2)は10回実行される。 イ: 20回は、区間幅の縮小を誤って半分ではなく1/4など過大に見積もった場合に生じる誤答である。 ウ: 100回は、区間幅の縮小率を極端に小さく見誤った場合に生じる誤答値である。 エ: 1,000回は、0.001という閾値の桁数をそのまま繰返し回数と誤認した場合に生じる誤答である。 💡 二分探索(二分法)は1回ごとに探索区間が半分になるため、必要回数はlog2(区間幅/許容誤差)で概算できる。ここでは2^10=1024>1000から10回と求まる。
出典：令和7年度 春期 応用情報技術者試験 午前 問2 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。