题目的主要信息：

• 计算一个浮点数的立方根
• 输入正负数都有，绝对值不超过20
• 保留一位小数

方法一：二分查找

具体做法：

如果输入的$x>1x>1$，那么立方根一定在1到$xx$之间，这是有序的，我们可以用二分法查找这之间三次方接近于$xx$的值，当区间范围不超过0.0001表示找到了这个值。

其余的如果，立方根在$xx$到1之间，如果，立方根在$-1-1$到x之间，如果，立方根在$xx$到-1之间，也是同上的做法，只需要更新一开始的左右区间值即可。

#include<iostream>
#include<iomanip>
using namespace std;

double cal(double x){ //二分查找
    double left = min(-1.0, x); //正负数都有
    double right = max(1.0, x);
    double y;
    while(abs(right - left) > 0.01){ //立方根的精度值
        y = (left + right) / 2; //二分中值
        if(y * y * y > x) //比较选取二分哪一边
            right = y;
        else
            left = y;
    }
    return y;
}

int main(){
    double val;
    while(cin >> val){
        cout << setprecision(1) << fixed << cal(val) << endl; //控制小数位输出
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O((lo{g}_{2}n{)}^k)O((log\_2n)^k)$，二分法的复杂度为$O(lo{g}_{2}n)O(log\_2n)$，但是这里的$kk$不确定，与精度有关
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：牛顿迭代法

具体做法：

我们设方程$f(x)=x^3-yf(x)=x^3-y$，当$f(x)=0f(x)=0$时的解$xx$就是$yy$的立方根。根据牛顿迭代法，我们有$x=x-(x^3-y)\mathrm{/}(3\ast x^2)x=x-(x^3-y)/(3*x^2)$，我们只需要控制$x^{3}x^3$和$yy$的精度在一定范围之内迭代即可。

#include<iostream>
#include<iomanip>
using namespace std;

double cal(double x){ //牛顿迭代法
    double y = 1;
    while(((y * y * y - x) >= 1e-2) || (x - y * y * y) >= 1e-2) //精度控制
        y = (y - y / 3 + x / (3 * y * y));
    return y;
}

int main(){
    double val;
    while(cin >> val){
        cout << setprecision(1) << fixed << cal(val) << endl; //控制小数位输出
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O((lo{g}_{2}n{)}^k)O((log\_2n)^k)$，牛顿迭代法时间复杂度与$O(lo{g}_{2}n)O(log\_2n)$有关，但是这里的$kk$不确定，与精度有关
• 空间复杂度：$O(1)O(1)$，无额外空间