令和7年春期試験問題 午前問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
広告
解説
設問の手順で連続関数のゼロ点を近似的に求めるアルゴリズムは「二分法」と呼ばれます。簡単に手順を示します。
210＝1,024 であることを踏まえると、n＝10 のとき誤差0.001（1／1000）未満を達成できます。したがって「ア」が正解です。
※補足としてJavaScriptによる実行例を示しておきます。
- 関数 ƒ(x) に対して、ƒ(a)＜0、ƒ(b)＞0 となるaとbを選ぶ
- c ← a＋b2で区間の真ん中を求める
- ƒ(c) を求め、誤差が条件内であればcを近似解とする
- ƒ(c)＜0であればa ← c、ƒ(c)＞0であればb ← cとして手順2に戻る
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ずつ狭めていっていることがわかります。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
//以下、続く
- 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／1000）未満を達成できます。したがって「ア」が正解です。
※補足としてJavaScriptによる実行例を示しておきます。
広告