题目描述
给定一个浮点数 n,求它的三次方根。
输入格式
共一行,包含一个浮点数 n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留 6 位小数。
数据范围
−10000≤n≤10000
样例
输入样例:
1000.00
输出样例:
10.000000
算法1
(二分) $O(n)$:
注:单调必可以二分,二分不一定要单调
(1)确定边界,不写加一
(2)观察两边的条件
(3)看模板,决定是否补加一
(4)合理输出
如果mid符合条件Mid是在右半区符合性质的半区中。要找左边界点的范围则更新为r = mid(包含Mid)。如果mid不符合条件,我们要找符合性质的左端点则l = mid + 1(已经确定mid是不符合的就从mid+1开始算)
注意:是否可以找到X元素
找到符合性质的左半区的右边界点。对mid进行判断来获得结果:如果mid符合条件,则mid就在左半区,那么我们要找的右边界点就可以更新为(mid,r)l = mid。
如果mid不满足条件,则mid必然在右半区间,而我们要找的符合要求的左半区间性质的右端点就是(l,mid-1)。r = mid - 1;
模板二要防止死循环:当mid = l + r >> 1时,加入l = r - 1当判断mid满足性质在左半区会更新为l = mid;而mid = (r - 1 + r)/2 = r - 0.5 = r - 1 = l(向下取整),则更新完仍然是l = r- 1没变化会死循环
C++ 代码
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
double my(double a){return aaa;}
int main()
{
double n;
cin>>n;
double l = -10000,r = 10000;
while(r - l>=1e-7)
{
double mid = (l + r)/2;//通过两个double型除2来找mid浮点数
if(my(mid) >= n )r = mid;
else l = mid ;//这里和整数模板不同,不可加一,防止加过头
}
cout<<fixed<<setprecision(6)<<l<<endl;//需要与fixed合用,防止科学技术表示
return 0;
}