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
感谢您的支持
发布评论