AcWing算法基础课-790数的三次方根-Java题解

Java资料网推荐AcWing算法基础课-790数的三次方根-Java题解这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

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

❓题目描述

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

输入格式

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

输出格式

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

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

数据范围

−10000 ≤ n ≤ 10000

输入样例：

1000.00

输出样例：

10.000000

💡算法思路

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

具体实现步骤：

1. 读取输入：

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

2. 初始化二分法：

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

3. 二分法迭代：

   • 在 while 循环中，当区间长度 r - l 大于精度 esp 时，继续二分：
     • 计算区间的中点 mid，即 (l + r) / 2。
     • 判断 mid 的立方是否大于等于 n：
       • 如果是，说明 mid 的三次方根在当前中点的左侧，因此将右边界 r 移动到 mid。
       • 如果不是，说明 mid 的三次方根在当前中点的右侧，因此将左边界 l 移动到 mid。
   • 这个过程不断缩小搜索区间，直到区间长度小于等于精度 esp，此时 l 即为 n 的三次方根的近似值。

4. 输出结果：

   • 在 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

---

🔍推荐阅读

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

欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~
你们的点赞👍 收藏⭐ 留言🗨️ 关注✅
是我持续创作，输出优质内容的最大动力！谢谢！

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

文章来源:https://blog.csdn.net/coder_heweilai/article/details/142367812
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！