解题思路
这是一个求解立方根的问题,要求不使用库函数,需要自己实现计算方法。可以使用二分法或牛顿迭代法求解。
关键点
- 数据范围:
- 输出要求:保留一位小数
- 不能使用库函数
- 需要处理正负数
代码
#include <iostream>
#include <iomanip>
using namespace std;
// 使用二分法求解立方根
double getCubeRoot(double num) {
// 处理特殊情况
if (num == 0) return 0;
// 确定二分查找的范围
double left = min(-1.0, num);
double right = max(1.0, num);
// 精度设置
const double eps = 0.0001; // 误差范围
while (right - left > eps) {
double mid = (left + right) / 2;
double cube = mid * mid * mid;
if (cube > num) {
right = mid;
} else {
left = mid;
}
}
return left;
}
int main() {
double num;
while (cin >> num) {
double result = getCubeRoot(num);
cout << fixed << setprecision(1) << result << endl;
}
return 0;
}
import java.util.*;
public class Main {
// 使用牛顿迭代法求解立方根
public static double getCubeRoot(double num) {
if (num == 0) return 0;
double x = num; // 初始值
double eps = 0.0001; // 精度
while (true) {
double nextX = (2 * x + num / (x * x)) / 3;
if (Math.abs(nextX - x) < eps) {
return nextX;
}
x = nextX;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
double num = sc.nextDouble();
System.out.printf("%.1f%n", getCubeRoot(num));
}
}
}
def get_cube_root(num):
if num == 0:
return 0
# 二分法求解
left = min(-1, num)
right = max(1, num)
eps = 0.0001 # 精度
while right - left > eps:
mid = (left + right) / 2
cube = mid * mid * mid
if cube > num:
right = mid
else:
left = mid
return left
while True:
try:
num = float(input())
result = get_cube_root(num)
print(f"{result:.1f}")
except:
break
算法及复杂度
算法分析
-
二分法思路:
- 确定初始范围
- 不断二分逼近结果
- 直到达到指定精度
-
牛顿迭代法思路:
- 迭代直到收敛
复杂度分析
-
二分法:
- 时间复杂度:
-
是数值范围,
是精度
- 空间复杂度:
- 时间复杂度:
-
牛顿迭代法:
- 时间复杂度:
- 但实际收敛速度更快
- 空间复杂度:
- 时间复杂度: