アルゴリズム (全82問中5問目)

No.5

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

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

仮に 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による実行例を示しておきます。
02a.gif/image-size:376×410
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop