题意

不用库,自己实现一个立方根函数

限制: 传入的数的绝对值不大于$20^{3}20^3$

方法

二分

注意到,一个数的三次方是单调递增函数.单调性的函数可以使用二分

每次把猜测的区间二分, 根据其中点三次方的值和要求的值的大小关系,来判断要求的值是在左区间还是右区间

以题目的样例数据216为例

这时,我们取其 一位小数即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    double val;
    cin>>val;
    double l = -30; // 左边界
    double r = 30; // 右边界
    while(val-l*l*l > 0.000001){ // 精度控制
        double mid = (l+r)/2;
        if(mid*mid*mid < val){ // 判断结果在 左区间还是右区间
            l = mid;
        }else{
            r = mid;
        }
    }
    printf("%.1f\n",l);
    return 0;
}

复杂度分析

时间复杂度: 我们对于区间采取二分,所以时间复杂度为$O(log(n))O(log(n))$

空间复杂度: 我们用了常数个变量来实现逻辑,所以空间复杂度为$O(1)O(1)$

牛顿切线

我们先看三次方程,在正的部分的曲线是凸函数(下凸函数), 负的部分是凹函数(上凸函数)

要求$X=x^{3}X\; =\; x^3$ 实际是 $f(x)=x^3-X=0f(x)\; =\; x^3\; -\; X\; =\; 0$的解

考虑在$ff$上

点$x=x_{0}x=x\_0$处做切线,有切线方程 $y=f^{\mathrm{\prime }}(x_0)(x-x_0)+y_{0}y\; =\; f\text{'}(x\_0)(x-x\_0)\; +\; y\_0$

其 交x轴于$x=x_0-\frac{y_0}{f^{\mathrm{\prime }}(x_0)}=x_0-\frac{x_0^3-X}{3x_0^2}x\; =\; x\_0\; -\; \backslash frac\{y\_0\}\{f\text{'}(x\_0)\}\; =\; x\_0\; -\; \backslash frac\{x\_0^3\; -\; X\}\{3x\_0^2\}$

因此 我们有了递推式.

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    double val;
    cin>>val;
    double ans = val > 0?30:-30;
    while(abs(ans*ans*ans - val) > 0.000001 ){
        ans = ans - (ans*ans*ans - val) / (3*ans*ans); // 基于牛顿切线的递推式
    }
    printf("%.1f\n",ans);
    return 0;
}

复杂度分析

时间复杂度: 我们采取牛顿切线法,所以时间复杂度为$O(log(n))O(log(n))$

空间复杂度: 我们用了常数个变量来实现逻辑,所以空间复杂度为$O(1)O(1)$