題目

已知 sqrt (2)約等于 1.414，要求不用數(shù)學(xué)庫(kù)，求 sqrt (2)精確到小數(shù)點(diǎn)后 10 位

考察點(diǎn)

1. 基礎(chǔ)算法的靈活應(yīng)用能力，二分法學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)都知道，但不一定往這個(gè)方向考慮；如果學(xué)過(guò)數(shù)值計(jì)算的同學(xué)，應(yīng)該還要能想到牛頓迭代法并解釋清楚

2. 退出條件設(shè)計(jì)

解決辦法

1. 已知 sqrt(2)約等于 1.414，那么就可以在(1.4, 1.5)區(qū)間做二分

查找，如： a) high=>1.5 b) low=>1.4 c) mid => (high+low)/2=1.45 d) 1.45*1.45>2 ? high=>1.45 : low => 1.45 e) 循環(huán)到 c)

2. 退出條件

a) 前后兩次的差值的絕對(duì)值<=0.0000000001, 則可退出

const double EPSILON = 0.0000000001;

double sqrt2() {
    double low = 1.4, high = 1.5;
    double mid = (low + high) / 2;

    while (high - low > EPSILON) {
        if (mid * mid > 2) {
            high = mid;
        } else {
            low = mid;
        }
        mid = (high + low) / 2;
    }

    return mid;
}