描述
计算一个浮点数的立方根,不使用库函数。
保留一位小数。
数据范围:
∣val∣≤20
输入描述:
待求解参数,为double类型(一个实数)
输出描述:
输出参数的立方根。保留一位小数。
示例1
输入:
19.9
复制
输出:
2.7
示例2
输入:
2.7
输出:
1.4
计算一个浮点数的立方根 输入正负数都有,绝对值不超过20 保留一位小数
具体做法:
如果输入的x>1,那么立方根一定在1到x之间,这是有序的,我们可以用二分法查找这之间三次方接近于x的值,当区间范围不超过0.0001表示找到了这个值。
其余的如果0<x<1,立方根在x到1之间,如果−1<x<0,立方根在−1到x之间,如果x<−1,立方根在x到-1之间,也是同上的做法,只需要更新一开始的左右区间值即可。 具体的C++实现代码如下:
#include<iostream>
#include<iomanip>
using namespace std;
double cal(double x){ //二分查找
double left = min(-1.0, x); //正负数都有
double right = max(1.0, x);
double y;
while(abs(right - left) > 0.01){ //立方根的精度值
y = (left + right) / 2; //二分中值
if(y * y * y > x) //比较选取二分哪一边
right = y;
else
left = y;
}
return y;
}
int main(){
double val;
while(cin >> val){
cout << setprecision(1) << fixed << cal(val) << endl; //控制小数位输出
}
return 0;
}
复杂度分析: 时间复杂度:O((log2n)^k),二分法的复杂度为O(log2n),但是这里的k不确定,与精度有关 空间复杂度:O(1),无额外空间
具体做法:
我们设方程f(x)=x^3 −y,当f(x)=0时的解x就是y的立方根。根据牛顿迭代法,我们有x = x − (x ^ 3 − y)/(3 ∗ x ^ 2),我们只需要控制x ^ 3和y的精度在一定范围之内迭代即可。 具体的C++实现代码如下:
#include<iostream>
#include<iomanip>
using namespace std;
double cal(double x){ //牛顿迭代法
double y = 1;
while(((y * y * y - x) >= 1e-2) || (x - y * y * y) >= 1e-2) //精度控制
y = (y - y / 3 + x / (3 * y * y));
return y;
}
int main(){
double val;
while(cin >> val){
cout << setprecision(1) << fixed << cal(val) << endl; //控制小数位输出
}
return 0;
}
复杂度分析: 时间复杂度:O((log2n) ^ k),牛顿迭代法时间复杂度与O(log2n)有关,但是这里的k不确定,与精度有关 空间复杂度:O(1),无额外空间