递归算法计算平方根和立方根

Question

当我运行我的代码时，有时可以正常工作，但是其他时候会出现以下错误：

Exception in thread "main" java.lang.StackOverflowError       
at squareroot.SquareRoot.GetSquareRoot (SquareRoot.java: 9)   
at squareroot.SquareRoot.GetSquareRoot (SquareRoot.java: 13)   
at squareroot.SquareRoot.GetSquareRoot (SquareRoot.java: 13)`

我在检查代码时发现进入了无限循环，请问该如何解决这个问题？谢谢。

public static double GetSquareRoot(double n, double low, double high) {
    double sqrt = (low + high) / 2;
    if (sqrt*sqrt > n)
        return GetSquareRoot(n, low, sqrt);
    if (sqrt*sqrt < n)
        return GetSquareRoot(n, sqrt, high);
    return sqrt;
}
public static double Sqrt(double n){
    return GetSquareRoot(n, 0, n);
}

public static double GetCubicRoot(double n, double low, double high) {
    double cbrt = (low + high) / 2;
    if (cbrt*cbrt*cbrt > n)
        return GetCubicRoot(n, low, cbrt);
    if (cbrt*cbrt*cbrt < n)
        return GetCubicRoot(n, cbrt, high);
    return cbrt;
}
public static double Cbrt(double n) {
    return GetCubicRoot(n, 0, n);
}

public static void main(String[] args) {
    Scanner Input = new Scanner(System.in);

    double n = Input.nextDouble();
    double sqrt = Sqrt(n);
    double cbrt = Cbrt(n);

    System.out.println("Raiz cuadrada igual a: "+ sqrt);        
    System.out.println("Raiz cubica igual a: "+ cbrt);  

}

- user2121539

---

你可能想近似比较 sqrt*sqrt == n，因为浮点数比较并不精确。 - dchhetri

Answer 1

你的结果很可能永远不会达到结束条件，因为乘法不太可能产生精确的数字，你必须引入误差范围，因为平方根通常不是精确的，浮点运算由于浮点限制使用近似值。

public static double GetSquareRoot(double n, double low, double high) {
    double errorMargin = 0.001;        
    double sqrt = (low + high) / 2;
    double diff = sqrt*sqrt - n;
    if ( diff > errorMargin)
        return GetSquareRoot(n, low, sqrt);
    if ( -diff > errorMargin)
        return GetSquareRoot(n, sqrt, high);
    return sqrt;
}

- Ruan Mendes

Answer 2

您的停止条件是 "if n == num"，其中 n 和 num 都是双精度数字。双精度或浮点数已知不精确，因此可能永远无法满足此条件。相反，请使用以下条件：

if(Math.abs(sqrt*sqrt - n) < .001)
     return sqrt;

这将停止在两个数字之间的差异变得“足够小”的时候。

- Joe

Answer 3

在使用double类型时，应该使用delta double值。因为你计算出来的值可能不会和你预期的完全相等。

bool CompareDoubles2 (double A, double B) 
{
   diff = A - B;
   return (diff < EPSILON) && (-diff > EPSILON);
}

- Ahmet Karakaya