HOME»ネットワークスペシャリスト平成28年秋期»午前Ⅰ 問1
ネットワークスペシャリスト平成28年秋期 午前Ⅰ 問1
問1
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
- [出典]
- 応用情報技術者
平成28年秋期 問2と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
仮に ƒ(0.3)=0 としてアルゴリズムを途中までトレースしていくと次のようになります。
210=1,024 であることを考えれば、n=10 のとき誤差0.001(1/1,000)未満を達成できます。したがって「ア」が正解です。
※補足としてJavaScriptによる実行例を示しておきます。
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ずつ狭めていきます。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
//以下、続く
- 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)
210=1,024 であることを考えれば、n=10 のとき誤差0.001(1/1,000)未満を達成できます。したがって「ア」が正解です。
※補足としてJavaScriptによる実行例を示しておきます。