华为机试题 HJ107 求解立方根
华为机试题 HJ107 求解立方根
ccf19881030
发布于 2023-02-26 16:35:25
发布于 2023-02-26 16:35:25
华为机试 HJ107 求解立方根
题目描述：
描述
计算一个浮点数的立方根，不使用库函数。
保留一位小数。
数据范围：
∣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)，无额外空间
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-02-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录