アルゴリズム (全79問中7問目)

No.7

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

〔アルゴリズム〕
  • x0←0,x1←1とする。
  • x←x0+x12とする。
  • x1−x<0.001ならばxの値を近似値として終了する。
  • ƒ(x)≧0ならばx1←xとして,そうでなければx0←xとする。
  • (2)に戻る。
  • 10
  • 20
  • 100
  • 1,000
  • [出典]
  • 午前免除試験 R2-7月 問4
  • 応用情報技術者 H28秋期 問2と同題

分類

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

正解

解説

仮に ƒ(0.3)=0 としてアルゴリズムを途中までトレースしていくと次のようになります。
1: x0←0,x1←1
2: x←(0+1)/2 //x=0.5
3: (1−0.5)<0.001 は偽なので処理続行する
4: ƒ(0.5)≧0 は真なので、x1←0.5
  //(2)に戻る
5: x←(0+0.5)/2 //x=0.25
6: (0.5−0.25)<0.001 は偽なので処理続行する
7: ƒ(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: ƒ(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: ƒ(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(1/1,000)未満を達成できます。したがって「ア」が正解です。

※補足としてJavaScriptによる実行例を示しておきます。
04a.gif/image-size:376×410
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop