面試題：不使用數(shù)學(xué)庫(kù)求平方根

此題考查的是面試者的二分法和迭代相關(guān)的數(shù)學(xué)邏輯能力。

思路說明

每次查找區(qū)間內(nèi)的中間值，判斷他是否能夠達(dá)到標(biāo)準(zhǔn)。假如要查找2的平方根，我們?nèi)?和2的中間數(shù)1.5，而1.5^2=2.25 大于2，則我們需要從1和1.5區(qū)間內(nèi)在找一個(gè)中間值1.25。而1.25^2=1.5625，小于2，所有我們?nèi)?.25到1.5的中間數(shù)，然后一直繼續(xù)下去，直到滿足我們的要求。

代碼示例

package top.enjoyitlife.interview;

/**
 * @ClassName: CalculateApproximateValue
 * @Description: 求近似值。不使用數(shù)學(xué)公式求得平方根的近似值
 * @Author: MegaSlark
 * @Date: 2019/12/23
 */
public class CalculateApproximateValue {


    public static void main(String[] args) {
        //使用數(shù)學(xué)計(jì)算公式 這里就是提一下 通過自帶的函數(shù)庫(kù)得到的值
        double result = Math.sqrt(2);
        System.out.println(result);

        //二分法迭代
        CalculateApproximateValue cav = new CalculateApproximateValue();
        cav.nums = 2;
        cav.precision = 0.00000000001d;
        double myResult = cav.calculate(cav.nums);
        System.out.println(myResult);

    // for循環(huán)方式
        double myResult2 = cav.calculateSquareRoot2(2, cav.precision);
        System.out.println(myResult2);
    }


    //    方法計(jì)算次數(shù)
    private int calculateTimes;
    //    精度誤差
    private double precision;
    //    需要求近似值的元數(shù)據(jù)
    private double nums;

    /***
     * 迭代法求近似值的方法
     * @param num
     * @return double 平方根
     */
    private double calculate(double num) {
        return calculateSquareRoot(1, num);
    }

     /***
     * 迭代法求近似值的方法
     * @param num
     * @return double 平方根
     */
    public double calculateSquareRoot(double min, double max) {
        calculateTimes++;
        double mid = (min + max) / 2;
        double tempNums = mid * mid;
        if (Math.abs(tempNums - nums) > precision) {
            if (mid * mid < nums) {
                min = mid;
            } else {
                max = mid;
            }
            return calculateSquareRoot(min, max);
        } else {
            return mid;
        }
    }

    /***
    *for循環(huán)計(jì)算平方根近似值
    */
    private double calculateSquareRoot2(double num,  double precision) {
        double min = 1d;
        double max = num;
        for (;;) {
            double middle = (min + max) / 2;
            double square = middle * middle;
            double delta = Math.abs((square / num) - 1);
            if (delta <= precision) {
                return middle;
            } else {
                if (square > num) {
                    max = middle;
                } else {
                    min = middle;
                }
            }
        }
    }
}

說明

上面的代碼提供了兩種實(shí)現(xiàn)的方式，一種是通過迭代的方式，一種是通過for循環(huán)的方式，當(dāng)然我們也可以將for換成while循環(huán)的方式，這兩個(gè)方式略有差異，但是本質(zhì)就是上面說的思路，不斷的計(jì)算中間值，直到滿足我們需要的精度標(biāo)準(zhǔn)。

補(bǔ)充

這里在補(bǔ)充一點(diǎn)，Java里面的double類型數(shù)據(jù)，是雙精度64bit浮點(diǎn)數(shù)，通常10進(jìn)制的有效位數(shù)只有14位下，超過14位就會(huì)失真，所以14位是許多軟件推薦的最大顯示位，如果將題目的精度要求到15位，那么我們就需要將double類型改為bigdecimal，可以保留15位10進(jìn)制有效數(shù)字。