修了試験 2020-07-26実施分 基本情報技術者試験 問4

解説

正解は1です。 区間を半分ずつ狭めて解を探す二分法のアルゴリズムで、繰り返しの回数を数える問題です。 (2)で区間の中点をxとし、(4)で解を含む側の半分に区間を狭めます。 【計算】 最初の区間の幅x_1－x_0は1です。 (2)を1回目に実行すると、x_1－x＝1/2になります。 (4)で区間の幅が半分になるので、k回目の(2)の後はx_1－x＝1/2^kです。 (3)の終了条件は1/2^k＜0.001で、これは2^k＞1000と同じです。 2^9＝512は1000以下なので、9回目の(2)の後では終了しません。 2^10＝1024は1000を超えるので、10回目の(2)の後に終了します。 したがって、(2)は10回実行されます。 【選択肢別解説】 1：○ 2^10＝1024で初めて終了条件を満たすので、(2)の実行回数は10回です。 2：× 20回までは繰り返しません。 10回目の(2)の後で、既に終了条件を満たしています。 3：× 100回は、区間が毎回半分になる性質を考えていない値です。 二分法では幅が指数的に小さくなるので、10回で足ります。 4：× 1,000回は、幅を0.001ずつ減らすと考えた場合の回数です。 二分法では幅が半分ずつ減るので、はるかに少ない回数で終わります。 【ポイント】 二分法では、n回の繰り返しで区間の幅が1/2^nになります。 2^10＝1024がおよそ1000であることは頻出なので、覚えておくと便利です。