平成28年度秋期 応用情報技術者試験 午前 問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回実行するたびに探索区間の幅[x0,x1]が半分になる。初期幅は1で、終了条件はx1−x<0.001、すなわち区間幅が0.001×2未満相当になるまで繰り返す。n回実行後の区間幅は1/2^nであり、x1−x=区間幅の半分=1/2^(n+1)…と厳密に追うより、1/2^n<0.001×2 → 2^n>500程度、実際にシミュレーションすると10回目でx1−x=1/1024<0.001となり終了する。2^10=1024>1000がポイントである。 ア: 正しい。(2)をn回実行するとx1−x=1/2^nとなり、1/2^10=1/1024≒0.00098<0.001で初めて条件を満たすため、10回実行される。 イ: 20回では区間幅が1/2^20と必要以上に細かくなる。終了判定は0.001でよいため20回も繰り返されない。 ウ: 100回は2^100分の1まで縮める回数であり、過剰である。 エ: 1,000回は精度0.001を「回数」と混同した誤答である。二分法は指数的に収束するため線形の1,000回は不要。 💡 二分法は1回で区間が半分になるので、必要回数は2^n>(初期幅/要求精度)を満たす最小n。2^10=1024≒10^3を覚えておくと即答できる。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。