AP過去問 令和7年度春期 午前 問2
AP過去問 令和7年度春期 午前 問1前の問題へ
AP過去問 令和7年度春期 午前 問3次の問題へ
問2(問題文)
0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに区間内でf(x)=0であるxの値を近似的に求めるアルゴリズムにおいて、(2)は何回実行されるか。
[アルゴリズム]
(1) x0←0、x1←1とする。
(2) x←x0+x12とする
(3) x1−x<0.001ならばxの値を近似値として終了する。
(4) f(x)≧0ならばx1←xとして、そうでなければx0←xとする。
(5) (2)に戻る。
ア 10
イ 20
ウ 100
エ 1000
回答・解説
この問題は、関数の値が0になる点を二分探索法によって近似的に求めるアルゴリズムの繰り返し回数について問うものです。アルゴリズムでは、探索区間を毎回半分にしていくため、何回繰り返せば区間の長さが0.001未満になるかを計算すれば答えが出ます。
初期状態では、区間の長さはx1−x0=1−0=1です。
アルゴリズムは1回ごとに区間を半分にしていくので、n回後には区間の長さが12nになります。
この長さが0.001未満になる必要があるため、次の不等式を解きます。
12n<0.001
両辺の逆数をとると
2n>1000
この不等式を満たす最小のnを求めます。
210=1024>1000
よって、n=10で条件を初めて満たすことになります。
したがって、(2)は10回実行されます。
AP過去問 令和7年度春期 午前 問1前の問題へ
AP過去問 令和7年度春期 午前 問3次の問題へ