题目描述
给定一个浮点数n,求它的三次方根。
输入格式
共一行,包含一个浮点数n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留6位小数。
数据范围
$−10000≤n≤10000$
样例
输入样例:
1000.00
输出样例:
10.000000
算法1
(浮点数二分法) $O(n)$
这个其实蛮好理解的,因为涉及到开放,所以求得的数避免不了是浮点数。
根据题目给的区间范围进行缩小,如果三次方大于或者等于该数,则区间应该缩小到[left,mid],包含mid,否则区间缩小到[mid,righlt],也包含mid,当区间缩小到精确范围后两位时(即代码中的eps)认为mid就是我们求的数。
时间复杂度
$O(n)$
C++ 代码
#include <iostream>
using namespace std;
double n;
int main()
{
//避免同时使用流式io和格式化io时造成反效果,使io效率降低
std::ios::sync_with_stdio(false);
cin >> n;
double l = -10000 , r = 10000;
double 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;
}