题目链接

AcWing 790.数的三次方根

引用

引用一下还不错的题解

第一WA者金银花 AcWing 790. 数的三次方根

zning AcWing 790. 浮点数二分法_Java

modeming AcWing 790. 数的三次方根(牛顿迭代法)

题目描述

给定一个浮点数n,求它的三次方根。

样例

输入格式

共一行,包含一个浮点数n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留6位小数。

数据范围

$−10000≤n≤10000$

输入样例:

$1000.00$

输出样例:

$10.000000$


算法

(浮点数二分) $O(n)$

关于浮点数二分就没什么好说的了,因为精度问题,像三次方根平方根这些都只能找到大概的范围,所以我们只要不断缩小范围即可,设定一个精度eps,如果题目说精确到6位,那我们设置的精度就为 $1e-8$。

有一个需要注意的点是,求平方根时,如果输入的数是 $< 1 && >0$,那么计算的时候就要注意了,比如0.1的平方根,那么答案肯定是在0.1到1之间,所以应该特殊处理区间更新方式

时间复杂度 $O(n)$

最多查找 $n/2$ 次,所以时间复杂度是线性的

C++ 代码

#include <cstdio>

using namespace std;

double n;

int main()
{
    scanf("%lf" , &n);
    
    double l = -1000 , r = 1000 , eps = 1e-8;
    
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    
    printf("%.6lf" , l);
    
    return 0;
}

Q.E.D.


都懂一点,不是很懂的小捞仔