基本情報技術者試験「二分法の反復回数」の問題
二分法で初期の探索区間の幅が1.0である。1回の反復で区間幅が半分になるとき、区間幅を0.1未満にするために必要な最小の反復回数はいくらか。
ア3回でよい
イ10回必要になる
ウ5回
エ最小で4回必要
正解
エ．最小で4回必要
n回反復後の区間幅は1.0×(1/2)^n。n=3で0.125(>0.1)、n=4で0.0625(<0.1)となり、初めて0.1を下回るのは4回目なので正しい。
?選択肢ごとの解説
ア ×3回では幅0.125で、まだ0.1以上のため条件を満たさない誤りである。あと1回必要である。
イ ×10回は0.1という値を反復回数と取り違えたり、10分の1を10回と短絡した誤りで、実際は4回で足りる。
ウ ×5回では0.03125となり条件は満たすが0.1未満になる最初の回ではなく、最小回数という条件に反する。
エ ○n回反復後の区間幅は1.0×(1/2)^n。n=3で0.125(>0.1)、n=4で0.0625(<0.1)となり、初めて0.1を下回るのは4回目なので正しい。
✎くわしく
二分法は1回ごとに区間幅が厳密に半分になる。必要回数は1/2^n<目標誤差を満たす最小のnで、2^n>(初期幅/目標)を解けばよい。本問は2^n>10、すなわちn≧4。確実だが1回で約0.3桁(1ビット)しか精度が上がらない遅さも特徴である。
✓本番での押さえどころ
試験のコツ
幅=初期幅×(1/2)^nを1回ずつ計算して目標を初めて下回る回を数える。2^n>初期幅/目標でも解ける。
覚え方
半分ごとに0.5→0.25→0.125→0.0625、と紙を折る回数を数える感覚で求める。
よくある誤り
等号の扱いを誤り3回で十分とする、または『最小回数』を見落として大きい回数を選ぶ誤りが多い。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0106