题意

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

限制: 传入的数的绝对值不大于20320^3

方法

二分

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

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

以题目的样例数据216为例

l r mid mid的三次方 判断
-30.000000000000000 30.000000000000000 0.000000000000000 0.000000000000000 在右区间
0.000000000000000 30.000000000000000 15.000000000000000 3375.000000000000000 在左区间
0.000000000000000 15.000000000000000 7.500000000000000 421.875000000000000 在左区间
0.000000000000000 7.500000000000000 3.750000000000000 52.734375000000000 在右区间
3.750000000000000 7.500000000000000 5.625000000000000 177.978515625000000 在右区间
5.625000000000000 7.500000000000000 6.562500000000000 282.623291015625000 在左区间
5.625000000000000 6.562500000000000 6.093750000000000 226.284027099609375 在左区间
5.625000000000000 6.093750000000000 5.859375000000000 201.165676116943359 在右区间
5.859375000000000 6.093750000000000 5.976562500000000 213.478624820709229 在右区间
5.976562500000000 6.093750000000000 6.035156250000000 219.819165766239166 在左区间
5.976562500000000 6.035156250000000 6.005859375000000 216.633430682122707 在左区间
5.976562500000000 6.005859375000000 5.991210937500000 215.052171028219163 在右区间
5.991210937500000 6.005859375000000 5.998535156250000 215.841835495666601 在右区间
5.998535156250000 6.005859375000000 6.002197265625000 216.237391601680429 在左区间
5.998535156250000 6.002197265625000 6.000366210937500 216.039553195287226 在左区间
5.998535156250000 6.000366210937500 5.999450683593750 215.940679259432500 在右区间
5.999450683593750 6.000366210937500 5.999908447265625 215.990112455560990 在右区间
5.999908447265625 6.000366210937500 6.000137329101562 216.014831882438415 在左区间
5.999908447265625 6.000137329101562 6.000022888183594 216.002471933257766 在左区间
5.999908447265625 6.000022888183594 5.999965667724609 215.996292135474476 在右区间
5.999965667724609 6.000022888183594 5.999994277954102 215.999382019632321 在右区间
5.999994277954102 6.000022888183594 6.000008583068848 216.000926972761590 在左区间
5.999994277954102 6.000008583068848 6.000001430511475 216.000154495276092 在左区间
5.999994277954102 6.000001430511475 5.999997854232788 215.999768257223991 在右区间
5.999997854232788 6.000001430511475 5.999999642372131 215.999961376192488 在右区间
5.999999642372131 6.000001430511475 6.000000536441803 216.000057935719894 在左区间
5.999999642372131 6.000000536441803 6.000000089406967 216.000009655952596 在左区间
5.999999642372131 6.000000089406967 5.999999865889549 215.999985516071661 在右区间
5.999999865889549 6.000000089406967 5.999999977648258 215.999997586011887 在右区间
5.999999977648258 6.000000089406967 6.000000033527613 216.000003620982170 在左区间
5.999999977648258 6.000000033527613 6.000000005587935 216.000000603497028 在左区间
5.999999977648258 6.000000005587935 5.999999991618097 215.999999094754457 在右区间

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

代码

#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=x3X = x^3 实际是 f(x)=x3X=0 f(x) = x^3 - X = 0的解

考虑在ff

x=x0x=x_0处做切线,有切线方程 y=f(x0)(xx0)+y0 y = f'(x_0)(x-x_0) + y_0

其 交x轴于x=x0y0f(x0)=x0x03X3x02 x = x_0 - \frac{y_0}{f'(x_0)} = x_0 - \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)