题解 | #求解立方根#牛顿迭代法+二分查找

import java.util.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Double d = in.nextDouble();

        // System.out.println(sqrt3(d));
        // System.out.printf("%.1f\n", Math.cbrt(d));
        System.out.println(newton(d));
    }

    // 方法 1
    static String newton(Double target) {
        /**
            使用牛顿迭代法有很多限制条件
            - 初始值的单调性
            - 函数本身连续可导
            - 一阶导数不等于 0 或者逼近于零

            这里的函数是 f(x)=x^3 - d;
            f'(x) = 3x^2;
         */

        Double initValue =
            1.0;// 这里的数值不能使 f'(x) 为 0,比如不能取 0.0
        Double epsilon = 1e-3;

        Double x0 = initValue;
        Double x1 = iteration(x0, target);
        while (Math.abs(x1 - x0) > epsilon) {
            x0 = x1 ;
            x1 = iteration(x0, target);
        }

        return String.format("%.1f", x1);
    }

    static Double iteration(Double x0, Double target) {
        Double fx = Math.pow(x0, 3) - target;
        Double dx = 2 * Math.pow(x0, 2);
        return x0 - fx / dx;
    }

    // 方法 2
    static String sqrt3(Double d) {
        Double left = 1.0;
        Double right = d;
        // 这里有更简单的写法
        if (d > 1) {
            left = 1.0;
            right = d;
        } else if (d > 0) {
            left = d;
            right = 1.0;
        } else if (d > -1) {
            left = -1.0;
            right = d;
        } else {
            left = d;
            right  = -1.0;
        }

        while (!String.format("%.2f", left)
                .equals(String.format("%.2f", right))) {
            // System.out.printf("left: %.4f, right: %.4f \n", left, right);

            Double mid = (left + right) / 2;
            // y=x**3是单调递增
            if (mid * mid * mid < d ) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return String.format("%.1f", left);
    }
}