yukicoder No.550 夏休みの思い出（１）

想定解とは違うけれども大丈夫そうなので解説を書いてしまった．

問題概要

• No.550 夏休みの思い出（１） - yukicoder

三次方程式を解け．

解は整数であることが分かっている．

submission

• #192857 No.550 夏休みの思い出（１） - yukicoder

ニュートン法

ニュートン法 - Wikipediaから引用

数値解析の分野において、ニュートン法（ニュートンほう、Newton's method）またはニュートン・ラフソン法（Newton-Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。

wikipediaによれば，func(x)=0となるxを求めたいとすると，こんな感じで求めることができる．

def func(x)
    x*x*x + @a*x*x + @b*x+@c
end

# funcを微分したもの
def dfunc(x)
    3*x*x + 2*@a*x + @b
end

# ニュートン法
# 引数は初期解
def newton(x)
    x = (x).to_f
    200.times{
        return 0 if divc(x) == 0
        x = x - calc(x)/divc(x)
    }
    x
end

• ニュートン法は，初期解によって解が変わることがある．なので，乱数で頑張る．
  • 誤差対策として，next if calc(z) != 0 を忘れずに．
• ただし，#192861 No.550 夏休みの思い出（１） - yukicoderのように，適当な乱数を与えると，-1 0 1のような，解が連続したケースでうまく見つけてくれない．
• そこで，既に2つの解x1,x3が見つかっている場合を考える．アプローチは2つある．
  • 2つ解が分かっているなら，三次方程式の解と係数の関係から，残りの1つの解を導出できる（おすすめ）．
  • 一定の確率で(x1,x3)の区間から乱数を取り出す（本番の実装）．