平成28年秋期試験午前問題 午前Ⅰ 問1

午前Ⅰ 問1解説へ
0≦x≦1の範囲で単調に増加する連続関数f(x)が f(0)≦0≦f(1) を満たすときに,区間内で f(x)=0 であるxの値を近似的に求めるアルゴリズムにおいて,(2)は何回実行されるか。

〔アルゴリズム〕
  • x0←0,x1←1とする。
  • x←am1/02.gifとする。
  • x1-x<0.001ならばxの値を近似値として終了する。
  • f(x)≧0ならばx1←xとして,そうでなければx0←xとする。
  • (2)に戻る。

  • 10
  • 20
  • 100
  • 1,000
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
仮に f(0.3)=0 としてアルゴリズムを途中までトレースしていくと次のようになります。
1: x0←0,x1←1
2: x←(0+1)/2 //x=0.5
3: (1-0.5)<0.001 は偽なので処理続行する
4: f(0.5)≧0 は真なので、x1←0.5
  //(2)に戻る
5: x←(0+0.5)/2 //x=0.25
6: (0.5-0.25)<0.001 は偽なので処理続行する
7: f(0.25)≧0 は偽なので、x0←0.25
  //(2)に戻る
8: x←(0.25+0.5)/2 //x=0.375
9: (0.5-0.375)<0.001 は偽なので処理続行する
10: f(0.375)≧0 は真なので、x1←0.375
  //(2)に戻る
11: x←(0.25+0.375)/2 //x=0.3125
12: (0.375-0.3125)<0.001 は偽なので処理続行する
13: f(0.3125)≧0 は真なので、x1←0.3125
  //以下、続く
このアルゴリズムでは2分探索法のように(2)~(5)を繰り返すごとにxの範囲を1/2ずつ狭めていきます。
  • 1回目 0≦x≦0.5 (最大誤差0.5)
  • 2回目 0.25≦x≦0.5 (最大誤差0.25)
  • 3回目 0.25≦x≦0.375 (最大誤差0.125)
  • 4回目 0.25≦x≦0.3125 (最大誤差0.0625)
このアルゴリズムの終了条件は誤差が0.001です。つまり1/1000未満になるまで(2)~(5)を繰り返します。上記の誤差の推移に注目すれば、処理回数n回目での誤差は次の式で表せることが分かります。

 1/2n

210=1,024 であることを考えれば、n=10 のとき誤差0.001未満を達成できます。したがって「ア」が正解です。

※補足としてJavaScriptによる実行例を示しておきます。
am1/02a.gif

Pagetop