平成28年度 秋期 応用情報技術者 問2

正解 ア

(2)を1回実行するたびに、x1−xは半分になります。k回目の値は1/2^kです。1/2^k＜0.001を初めて満たすのはk=10のときです。

このアルゴリズムは二分法です。区間の中点をxとし、f(x)の符号を見て、解を含む側の半分を次の区間にします。(2)を1回目に実行するとx=0.5で、x1−x=0.5=1/2です。(4)でx0とx1のどちらを更新しても区間の幅は半分になるので、k回目の(2)の後はx1−x=1/2^kです。2^9=512なので、9回目は1/512≒0.00195で0.001以上です。2^10=1024なので、10回目は1/1024≒0.00098で0.001未満になり、終了します。したがって、(2)の実行回数は10回です。

イ：20回では幅が1/2^20まで縮みます。条件は10回目で満たされ、そこで終了するので、20回までは実行されません。

ウ：区間の幅は1回ごとに半分になり、指数的に縮みます。10回で0.001未満になるので、100回は多すぎます。

エ：1,000回は、区間を0.001ずつ一定の幅で狭める場合の回数です。二分法では幅が1回ごとに半分になるので、10回で済みます。

出典：平成28年度 秋期 応用情報技術者試験 問2