6.AcWing790. 数的三次方根（AcWing算法基础课二刷）

方根（AcWing算法基础课二刷）"/>

6.AcWing790. 数的三次方根（AcWing算法基础课二刷）

关键词：浮点二分、迭代

地位：在算法竞赛中出现的次数比整数二分略少。

浮点二分和整数二分的思想一样，用的时间复杂度查找浮点数。在一般情况下，查找浮点数答案不适用线性算法。

浮点二分有一方面“优于“常规的二分查找：它不需要考虑边界问题，所以直接给定一个区间范围，设定初始的l和r，之后在要求精度内进行二分查找。

不过需要注意，浮点二分的while中的条件不再是l<r，而是(r-l)>eps。eps为二分精度，一般取题目要求精度的后两位。如果题目描述保留四位小数，那么eps设为1e-6；保留两位小数，那么eps设为1e-4。可以这样设置：

const double eps=1e-6;

表示eps=0.000001。

此外，浮点数可以for循环迭代100次来代替，此时区间被分成了份。

，

所以循环迭代100次一定可以获得非常好的精度效果。

（下图为迭代法求二次方根）

还有一种解法：cmath(或math.h)有cbrt()函数可以直接求三次方根（用法同sqrt()求平方根），这里不做详细介绍。因为这道题目的主要目的是让读者学会使用浮点二分查找答案。

这道题目比较简单，那我们直接上代码，先上while版本：

#include<iostream>
using namespace std;
const double eps=1e-8;//题目要求保留六位小数 这里设为8位
int main()
{double a;scanf("%lf",&a);//double用lf输入double l=-10000,r=10000,mid;while((r-l)>eps)//当r和l小于等于eps我们就认为他近似重合{mid=(l+r)/2;//浮点数不可以用>>1代替/2//如果mid的3次方相乘仍小于a 寻找范围是[mid,r]if(mid*mid*mid<a) l=mid;//否则范围是[l,mid]else r=mid;}//此时mid就是答案了printf("%.6lf",mid);return 0;
}

for循环迭代100次版本的代码：

#include<iostream>
using namespace std;
const double eps=1e-8;
int main()
{double a;scanf("%lf",&a);double l=-10000,r=10000,mid;for(int i=1;i<=100;i++){mid=(l+r)/2;if(mid*mid*mid<a) l=mid;else r=mid;}printf("%.6lf",mid);return 0;
}

参考链接/文献：

Ⅰ.AcWing——算法基础课，2019，闫学灿 活动 - AcWing

Ⅱ.AcWing790.数的三次方根 活动 - AcWing

感谢您的支持