平成28年度秋期 ネットワークスペシャリスト 午前Ⅰ 問1

反復回数を見積もる視点

区間を段階的に狭める計算では、初期の範囲と各反復での縮まり方を対応させ、求める精度に達するまでの流れを順序立てて確認することが重要です。途中の丸めや終了条件にも注意します。

この問題で問われていること

確認の中心は、初期状態から終了条件を満たすまでに、区間の大きさが各段階でどう変化するかを追い、反復を一回として数える境目を一貫させることです。特に開始時点を含めるかを確認します。

視点

初期条件、縮小の単位、目標とする精度、終了判定の関係を整理し、回数を数える基準が途中で変わっていないかを確認しましょう。

確認ポイント

• 初期状態を反復回数に含めるか確認する
• 各段階で比較している区間の基準をそろえる
• 終了条件を満たした時点の数え方を確認する

正解

ア

解説

このアルゴリズムは区間の中央値を繰り返し求める二分法です。k回目の(2)では、中央値から右端までの距離が1／2^kとなるため、1／2^k＜0.001を初めて満たす回数を求めます。

理由

初期区間の幅は1です。(2)をk回実行した直後の中央値から右端までの距離は、初期幅をk回二分した右半分なので、1／2^kです。停止条件より、1／2^k＜0.001、すなわち2^k＞1000を満たす最小のkを調べます。2^10＝1024なので、k＝10回です。

比較

条件は区間全体の幅ではなく、(2)で求めた中央値xと右端x₁との差です。したがって、区間幅が0.001以下になる回数をそのまま数えるのではありません。中央値を求めるたびに対象となる差が半分になり、10回目で1／1024となって0.001未満になります。

選択肢ア（正解）

これは正解だよ。初期区間の幅は1で、(2)をk回実行したときのx₁−xは1／2^kです。停止条件は1／2^k＜0.001なので、2^k＞1000を満たす最小のkを求めます。2^9＝512では不足しますが、2^10＝1024となるため、(2)は10回実行されます。

選択肢イ

これは不正解だよ。20回という回数は、停止条件を満たす最小回数ではありません。中央値を求めるたびに右端までの差は半分になり、10回目で1／1024となって0.001未満です。したがって、20回では条件を満たした後も余分に実行することになり、最小回数を表していません。

選択肢ウ

これは不正解だよ。100回は、区間を二分して停止条件を確認する回数として過大です。必要なのは2^kが1000を初めて超える回数であり、2^10＝1024で条件を満たします。100回実行すると、0.001未満になった後も繰り返すため、アルゴリズムの終了回数とは一致しません。

選択肢エ

これは不正解だよ。1,000回という値は、誤差の基準0.001をそのまま反復回数として扱ったものと考えられます。しかし、この処理では差が毎回半分になるため、回数は1000との単純な比例では決まりません。2^k＞1000を満たす最小の回数は10回であり、1,000回は必要以上です。

学習のポイント

二分法における区間幅の半減と、停止条件を満たす最小反復回数の求め方。