大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》790 题——数的三次方根。本题考查算法为<code>浮点数二分查找。本文详细介绍了一个使用二分法计算浮点数三次方根的算法。通过逐步逼近目标值，程序能够在给定的区间内精确计算出结果，并保留 6 位小数。文章从输入处理、二分法初始化、迭代过程到输出结果，全面解析了算法的实现步骤。

文章目录

❓题目描述💡算法思路✅Java代码🔗参考

❓题目描述

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

−10000 ≤ n ≤ 10000

输入样例：

1000.00

输出样例：

10.000000

💡算法思路

对数据进行输入处理使用二分法计算浮点数的三次方根对结果进行输出处理

具体实现步骤：

读取输入：

程序首先创建一个 StreamTokenizer 对象，用于从标准输入读取数据。通过 nextDoule 方法读取一个双精度浮点数 n，这个数是我们要计算三次方根的目标值。

初始化二分法：

程序定义了一个 solution 方法，用于计算 n 的三次方根。在 solution 方法中，初始化搜索区间为 [-10000, 10000]，即从 -10000 到 10000。设置一个精度 esp 为 1e-8，用于判断二分法是否达到所需精度。

二分法迭代：

在 while 循环中，当区间长度 r - l 大于精度 esp 时，继续二分：

计算区间的中点 mid，即 (l + r) / 2。判断 mid 的立方是否大于等于 n：

如果是，说明 mid 的三次方根在当前中点的左侧，因此将右边界 r 移动到 mid。如果不是，说明 mid 的三次方根在当前中点的右侧，因此将左边界 l 移动到 mid。 这个过程不断缩小搜索区间，直到区间长度小于等于精度 esp，此时 l 即为 n 的三次方根的近似值。

输出结果：

在 main 方法中，调用 solution 方法计算 n 的三次方根，并使用 System.out.printf 方法输出结果，保留6位小数。

时间复杂度：O(n log n)

空间复杂度：O(n)

✅Java代码

import java.io.*;

public class Aw790 { -- -->

// 创建一个StreamTokenizer对象，用于读取输入流

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

// 读取下一个双精度浮点数

static double nextDoule() throws IOException {

in.nextToken(); // 获取下一个输入标记

return in.nval; // 返回当前标记的值

}

static double n; // 存储输入的数值

public static void main(String[] args) throws IOException {

n = nextDoule(); // 读取输入的数值

// 调用solution方法计算三次方根，并输出结果，保留6位小数

System.out.printf("%.6f", solution(-10000, 10000, n));

}

// 使用二分法计算三次方根

static double solution(double l, double r, double x) {

final double esp = 1e-8; // 定义精度，用于判断二分法是否达到所需精度

// 这里有一个小技巧，当题目要求结果精确到n位小数时，我们将精度多设置2位

// 这样就能够得到精确的结果

while (r - l > esp) { // 当区间长度大于精度时，继续二分

double mid = (l + r) / 2; // 计算区间的中点

if (mid * mid * mid >= x) { // 如果中点的立方大于等于目标值

r = mid; // 将右边界移动到中点

// 这里的区间缩小不需要像整数二分那么精确，只需要将区间缩小一半即可

} else {

l = mid; // 否则将左边界移动到中点

}

}

return l; // 返回左边界，即三次方根的近似值

}

}

🔗参考

https://www.acwing.com/problem/content/792/

作者：程序员何未来-heweilai.com

🔍推荐阅读

AcWing算法基础课-789数的范围-Java题解AcWing算法基础课-788逆序对的数量-Java题解内容为王，推广为后：技术博客文章推广全攻略

欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~

你们的点赞👍 收藏⭐ 留言🗨️ 关注✅

是我持续创作，输出优质内容的最大动力！谢谢！

文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课