答えを二分探索②

問題

正の整数 $ N $ が与えられます。

$ x^3 + x = N $ を満たす正の実数 $ x $ を求めて下さい。

ただし絶対誤差が $ 0.01 $ 以下であれば正解とします。

解き方・ソースコード

$ f(x) = x^3 + x $ は単調な増加関数です。

$ x $ が増えると $f(x) $ も増えます。

二分探索を使って、$ x $ の範囲を次第にせまくしていくことにより正の整数 $ N $ に答えを近づけていきます。

今回は実行回数を20回としていますが、許容できる誤差の範囲に応じて調整しましょう。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#--------- 入力例 -----------
N = 99      # 正の整数
#----------------------------
def f(x):
    return x * x * x + x

# 二分探索
Left = 0.0
Right = 100.0
for i in range(20):
    Mid = (Left + Right) / 2
    val = f(Mid)
    print(Mid, val)

    # 探索範囲を絞る
    if val > N:
        Right = Mid     # 左半分に絞られる
    else:
        Left = Mid      # 右半分に絞られる

# 出力
print('解：', Mid)
print('x={}のときf(x)は{}'.format(Mid, f(Mid)))

[実行結果]

50.0 125050.0

25.0 15650.0

12.5 1965.625

6.25 250.390625

3.125 33.642578125

4.6875 107.684326171875

3.90625 63.510894775390625

4.296875 83.63065719604492

4.4921875 95.14340162277222

4.58984375 101.28254741430283

4.541015625 98.1804946437478

4.5654296875 99.7233574045822

4.55322265625 98.94989057502244

4.559326171875 99.33611444539565

4.5562744140625 99.1428752093725

4.55474853515625 99.04635107764648

4.553985595703125 98.99811287402898

4.5543670654296875 99.02222998759483

4.554176330566406 99.01017093377199

4.554080963134766 99.0041417796431

解： 4.554080963134766

x=4.554080963134766のときf(x)は99.0041417796431

解は4.554080963134766となりました😊

実際に計算式 $ x^3 + x = N $ に当てはめると結果は99.0041417796431となり、許容誤差の0.01以下となります。