题目主要信息

1、计算一个浮点数的立方根

2、不能使用库函数

3、保留一位小数

方法一：二分

具体做法

做过求平方根的同学应该都知道，这题最先想到的应该就是二分法吧。

• 如果一个数num>1，那么这个数的立方根一定在1~num之间。
• 如果一个数num<-1，那么这个数的立方根一定在num~-1
• 如果一个数-1<num<1，那么这个数的立方根一定在-1~1之间 如num = 2.7

可以设置左边界为min(-1,2.7) = -1 右边界 max(1,2.7) = 2.7

所以left = -1，right = 2.7

执行流程

left:-1.0 mid:0.8500000000000001right:2.7
left:0.8500000000000001 mid:1.7750000000000001right:2.7
... ... 

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        double num = Double.valueOf(bf.readLine());
        //double  n = getCubeRoot(num);
        double x = Dichotomy(num);
        System.out.printf("%.1f",x);
    }
    //使用类似二分的思路
    public static double Dichotomy(double num) {
        double right , left, mid = 0.0;
        //一定要注意边界条件，输入的num可能是负数  将x<-1的边界范围定为[x,1]，x>1的边界范围定为[-1,x]
        right = Math.max(1.0,num);
        left = Math.min(-1.0,num);
        while (right - left > 0.001) {
            mid = (left + right) / 2;
            //如果乘积大于num，说明立方根在mid的左侧
            if (mid * mid * mid > num) {
                right = mid;
            }
            //如果乘积小于num，说明立方根在mid的右侧
            else if (mid * mid * mid < num) {
                left = mid;
            } else {
                return mid;
            }
        }
        return right;
    }
}

复杂度分析：

• 时间复杂度：$O(lo{g}_2(n))O(log\_2(n))$。
• 空间复杂度：$O(1)O(1)$，常数级空间。

方法二：借助牛顿法公式

具体做法

在工程优化这门课程中有学到过，除了牛顿法、还有拟牛顿法等。 求等价于求的根。根据迭代公式 一直进行迭代求解，直到不满足条件，迭代结束。

最后输出小数点后1位即可。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        double num = Double.valueOf(bf.readLine());
        double  n = getCubeRoot(num);
        System.out.printf("%.1f",n);
    }
    private static double getCubeRoot(double num) {
        //判断输入是否为0 为0直接返回
        if (num == 0) {
            return 0;
        }
        double x0 = num;
        double x1 = (2*x0 + num/(x0*x0))/3;
        //迭代结束的条件 
        while (Math.abs(x1 - x0) > 0.0001) {
            x0 = x1;
            //更新x1
            x1 = (2*x0 + num/(x0*x0))/3;
        }
        //最终结果
        return x1;
    }
}

复杂度分析

• 时间复杂度：$O(lo{g}_3(n))O(log\_3(n))$,主要是迭代截止的条件有关。
• 空间复杂度：$O(1)O(1)$，常数级别的。