2026-09-02
solve.rs
fn solve(f: impl Fn(f64) -> f64, lo: f64, hi: f64, tol: f64) -> Option<f64> {
}
連続な関数 f と、lo < hi を満たす区間の両端、正の数 tol を受け取り、lo 以上 hi 以下で f(x) = 0 となる x の近似値を返す solve を書いてください。f(lo) と f(hi) はどちらも0ではないものとし、両者の符号が同じなら None を返します。符号が異なるときは、両端で f の符号が異なるように保ったまま区間を中点で半分にすることを、区間の幅が tol 以下になるまで繰り返し、最後の区間の中点を返します。途中で中点での f の値がちょうど0になったら、その中点を返します。f は増加する関数とは限りません。
入力例 1
solve(|x| x * x - 2.0, 1.0, 2.0, 0.25)
出力例 1
Some(1.375)
入力例 2
solve(|x| 1e-200 * (0.3 - x), 0.0, 1.0, 0.25)
出力例 2
Some(0.375)
入力例 3
solve(|x| x * x + 1.0, -1.0, 1.0, 0.25)
出力例 3
None
Reference
fn solve(f: impl Fn(f64) -> f64, lo: f64, hi: f64, tol: f64) -> Option<f64> {
let lo_negative = f(lo) < 0.0;
if lo_negative == (f(hi) < 0.0) {
return None;
}
let (mut lo, mut hi) = (lo, hi);
while hi - lo > tol {
let mid = (lo + hi) / 2.0;
let y = f(mid);
if y == 0.0 {
return Some(mid);
}
if (y < 0.0) == lo_negative {
lo = mid;
} else {
hi = mid;
}
}
Some((lo + hi) / 2.0)
}
最初に f(lo) が負かどうかを lo_negative に覚えておきます。区間を縮めるとき、lo には f の符号が f(lo) と同じ点しか置かないので、この値は最後まで変わりません。中点での符号が lo と同じなら解は中点より右にあるので lo を動かし、違えば hi を動かします。「f(mid) が正なら hi を動かす」と書くと増加する関数でしか正しく動かず、入力例2のような減少する関数では解から離れていきます。
符号が同じかどうかを f(lo) * f(mid) > 0.0 で調べる書き方もよく見ますが、入力例2では f の値が10−200程度なので、積は10−401程度になります。f64 で表せる最も小さい正の数は約4.9 × 10−324なので、積は 0.0 か −0.0 に丸められ、符号が分からなくなります。参考実装のように、掛け算をせずにそれぞれを0と比べれば、値がどれほど小さくても符号を取り違えません。
f が連続で両端の符号が異なれば、その間に f(x) = 0 となる x が必ずあります。これは数学IIIで習う中間値の定理(intermediate value theorem)です。区間を中点で分けると、どちらか一方は必ず両端の符号が異なるので、解を挟んだまま幅を半分にしていけます。この方法を二分法(bisection method)といいます。
掲載したのは参考実装で、唯一の正解ではありません。符号を f64::is_sign_negative で比べても同じように動きます。tol が lo や hi の大きさに比べて小さすぎると、隣り合う f64 の間隔より幅が狭くならず、ループが終わらなくなるので、実際のコードでは繰り返しの回数にも上限を設けます。