基本情報技術者令和2年免除 問4
問4
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 としてアルゴリズムを途中までトレースしていくと次のようになります。
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による実行例を示しておきます。