题目的主要信息：

计算一个浮点数的立方根，不使用库函数。

方法一：

牛顿迭代法。设 $f (x) = x^{3} - y$ , 求 $f (x) = 0$ 时的解x，即为y的立方根。根据牛顿迭代思想， $x_{n+1}=x_n-f(x_n)/f'(x_n)$ 即 $x = x - (x^{3} - y) / (3 * x^{2})$ 。不断更新x的值，直到误差小于0.000001。

具体做法：

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    double d;
    double x=1;
    cin>>d;
    while(abs(x*x*x-d)>0.000001){//误差要小于0.00001
        x=x-(x*x*x-d)/(3*x*x);//更新x的值
    } 
    printf("%.1lf\n",x);
    return 0;
}

复杂度分析：

时间复杂度： $O (l o g_{2} n)$ ，需要不断更新x的值。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

用二分法查找。关键在于确定初始的查找边界，有以下几种情况：

x>1，x的立方根的范围为[1,x]。
-1<x<1，x的立方根范围为[-1,1]。
x<-1，x的立方根范围[x,-1]。

为了减少判断，我们将x<-1的边界范围定为[x,1]，x>1的边界范围定为[-1,x]。然后再不断判断中间值和立方根之间的差距，缩小范围，直至达到精度。 alt

具体做法：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

#define eps 1e-9//精度

int main(){
    double num,l,r,mid;
    while(cin>>num){ 
        l = min(-1.0,num);//左边界
        r = max(1.0,num);//右边界
        while(fabs(r-l)>eps){//二分法不断缩小区间
            mid = (r + l)/2;
            if(mid * mid * mid < num){
                l = mid;//让下一步mid的值更大
            }else{
                r = mid;
            }
        }
    }
    printf("%.1f",mid);
    return 0;
}

复杂度分析：

时间复杂度： $O (l o g_{2} n)$ ，二分查找。
空间复杂度： $O (1)$ ，只用了常数空间。

题解 | #求解立方根#

题目的主要信息：

方法一：

方法二：