如何在 Java 中求一个数的平方根？

用 Java 或 C++ 编写计算数字平方根的程序是许多科技公司和投资银行编程面试中最受欢迎的编码面试问题之一。这个问题可能看起来很容易，因为你可能知道如何找到数字的方根，但事实并非如此。事实上，这是很多人在编程求职面试中遇到的棘手问题之一。你真的记得怎么算平方根吗？很多程序员都不知道。也许他们以前学过，但当你让他们计算平方根时，很多人都不记得他们在学校或大学里学过的算法了。

有些人可能会用它java.lang.Math sqrt()函数来计算 Java 虽然这也是正确的，但面试官并没有问。他会要求你用算法开发的方法来计算平方根。

聪明的程序员会想出一些方法，比如用牛顿法计算平方根。如果你记得并使用牛顿法，你可以向面试官解释，他们可能不太了解。

编程/编码面试前，尽可能多地练习数据结构和算法，以充分利用所学知识。还可以参加综合数据结构和算法课程，填补知识空白。

当有人问我这个问题时，我对此一无所知。和大多数人一样，我也忘记了手动计算平方根的算法，但突然我想到了x = sqrt(y)和x^2 = y即这里的 X 它是平方根，你可以通过计算找到平方根 x 检查它是小于还是等于 Y。一旦它大于 Y，可以停止循环。这个计划对我来说是可行的，所以我开始编程。

public static float root(int number) {float root = 0.0f;float square = root;while (square < number) {root++;square = root * root;}return root;}

Output

4

9

16

25

26

Square root

2

3

4

5

6

虽然它不高效，只适用于完美的正方形，但我很高兴在我还没有准备好的问题上继续前进。然后面试官问，对于一个不完美的数字，平方根差 1.如何纠正？我回答说，我们可以通过使用自定义精度来缩小差距。

下一个可能的平方根不断增加 1.如果我们使用它，我们得到的答案远非近似值 0.5 或 0.1，我们将得到更类似的答案，如下所示。

public static float root(int number) {if (number < 0)return -1;if (number == 0 || number == 1)return number;float root = 0.0f;float precision = 0.1f;float square = root;while (square < number) {root = root + precision;square = root * root;}return root;}

Output

4

5

6

7

8

9

Square root

2.0000002

2.3

2.4999998

2.6999996

2.8999994

3.0999992

虽然答案并不完美，结果也不是很相似，但我们可以通过使用较低的精度来使平方根更接近正确的值。当被问及解决方案的时间复杂性时，我认为它是线性的，因为我们一步一步地接近正确的答案。

我们能让它变得更好吗？是的，我们知道对数时间比线性时间好，也就是说O(logN)比O(N)好吧，当我想到的时候 logN 当时我想到的算法是二进制搜索。为什么不用二进制搜索找平方根呢？这是朝着正确方向迈出的又一小步，从而产生了以下解决方案:

public static float sqrt(int number) {if (number < 0)return -1;if (number == 0 || number == 1)return number;float start = 0.0f;float end = number;float precision = 0.001f;float middle = start;float difference = (float) Math.abs(Math.pow(middle, 2) - number);while (difference >= precision) {  middle = (start + end) / 2.0f;  if (Math.pow(middle, 2) > number) {    end = middle;  } else {    start = middle;  }  difference = (float) Math.abs(Math.pow(middle, 2) - number);}return middle;}

Output

4

5

6

7

8

9

Square root

2.0

2.236023

2.449585

2.645935

2.8283691

3.0000916

目前，该算法在运行中更好，但仍存在一个关键问题，可能导致程序一直在运行，这取决于精度和数字的平方根。例如，如果将精度更改为 0.00000001f 并尝试计算 5 由于条件差异，平方根将进入无限循环 >= 精度永远不会变成false。我们需要在这里使用它Float.compareTo()比较浮点值的方法不大于运算符 (>) 。

在此处比较 Java 避免浮点数中的无限循环。这是一个值得研究和理解的好话题。

顺便说一句，这个解决方案可能会帮助你找到一个 Java 应用程序开发角色的工作，但不会帮助你在游戏编程或定量领域找到工作，他们非常重视快速和准确的算法。你可以通过提出解决方案并稍微改进它来得到一些分数，这表明你有很好的学习能力，但视频游戏是不同的。

正如我在第一段所说，这个问题可能看起来很简单，但事实并非如此，你需要很好地理解编程语言中的浮点操作。