HOME»応用情報技術者平成28年秋期»午前問2

応用情報技術者平成28年秋期 午前問2

問2

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

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

ア

解説

設問の手順で連続関数のゼロ点を近似的に求めるアルゴリズムは「二分法」と呼ばれます。簡単に手順を示します。
  1. 関数 ƒ(x) に対して、ƒ(a)＜0、ƒ(b)＞0 となるaとbを選ぶ
  2. c ← a＋b2で区間の真ん中を求める
  3. ƒ(c) を求め、誤差が条件内であればcを近似解とする
  4. ƒ(c)＜0であればa ← c、ƒ(c)＞0であればb ← cとして手順2に戻る
仮に ƒ(0.3)＝0 としてアルゴリズムを途中までトレースしていくと次のようになります。
1: x0 ← 0，x1 ← 1
2: x ← (0＋1)／2 = 0.5
3: (1－0.5)＜0.001 は偽なので処理続行する
4: ƒ(0.5)≧0 は真なので、x1 ← 0.5
　//(2)に戻る
5: x ← (0 + 0.5)／2 = 0.25
6: (0.5 - 0.25)＜0.001 は偽なので処理続行する
7: ƒ(0.25)≧0 は偽なので、x0 ← 0.25
8: x ← (0.25 + 0.5)／2 = 0.375
9: (0.5 - 0.375)＜0.001 は偽なので処理続行する
10: ƒ(0.375)≧0 は真なので、x1 ← 0.375
　//(2)に戻る
11: x ← (0.25 + 0.375)／2 = 0.3125
12: (0.375 - 0.3125)＜0.001 は偽なので処理続行する
13: ƒ(0.3125)≧0 は真なので、x1 ← 0.3125
　//以下、続く
このアルゴリズムの流れを見ると、2分探索法のように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)を繰り返すことになります。誤差は初期値を1とし、繰返しごとに2分の1ずつ小さくなるので、処理n回目での誤差は「1／2n」の式で表すことができます。

210＝1,024 であることを踏まえると、n＝10 のとき誤差0.001（1／1000）未満を達成できます。したがって「ア」が正解です。

※補足としてJavaScriptによる実行例を示しておきます。

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