0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに、区間内でf(x)=0であるxの値を近似的に求めるアルゴリズムにおいて、(2)は何回実行されるか。 〔アルゴリズム〕 (1) x0←0, x1←1とする。 (2) x←(x0+x1)/2とする。 (3) x1−x＜0.001ならばxの値を近似値として終了する。 (4) f(x)≧0ならばx1←xとして、そうでなければx0←xとする。 (5) (2)に戻る。

選択肢

• ア10
• イ20
• ウ100
• エ1,000

正解と解説

正解：ア 10

これは二分法（区間二分法）で、1回処理するごとに解の存在する区間が半分になります。初期区間の幅は1で、(2)をk回実行した時点での x1−x は 2 の −k 乗になります。終了条件 2 の −k 乗 < 0.001 を満たす最小の k は、2 の −10 乗 ≒ 0.000977 より k=10 です。よって(2)は10回実行されます。

選択肢ごとの解説

• ア正解。区間幅が 2 の −10 乗まで縮んで初めて 0.001 を下回ります。
• イ1回で区間が10分の1になるわけではないので、回数を過大に見積もっています。
• ウ区間が半分ずつ縮むことを踏まえておらず、桁が合いません。
• エ0.001 の逆数をそのまま回数とした誤りで、二分法の収束の速さを無視しています。

この問題に出た用語

• ニュートン法と二分法（方程式の数値解法）

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値…2025年度 春期 午前 問2
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6