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、(2)を実行するたびに残り幅が半分になる。k回目の(2)の直後の判定量は1/2^kなので、終了条件0.001未満を満たすのは1/2^k<0.001、すなわち2^k>1000となる最小のkである。2^9=512、2^10=1024なのでk=10回。

選択肢ごとの解説

• ア正解。2^10=1024>1000となり、10回目で幅が0.001を下回る。
• イ20回では2^20≒10^6まで狭まり、必要以上の反復になる。
• ウ反復回数は精度の逆数に比例せず対数的に増えるので、100回は過大。
• エ1/0.001=1000をそのまま回数と見なした誤り。二分法は対数オーダー。

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6
• 配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった…2023年度 春期 午前 問7