4

这是一个相当理论化的问题，因此尽管该语言专门是 Java，但任何通用解决方案都足够了。

假设我想写一个微不足道的阶乘函数：

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }
    return p;
}

但是现在，我还想检查阶乘是否溢出（而不是简单地硬编码 MAX_FACTORIAL_PARAMETER 或类似的东西）。通常，在乘法过程中检查溢出就像检查原始输入的结果一样简单，但在这种情况下，由于溢出可能发生在任何时候，因此在每个循环中执行更多的除法和比较会相当昂贵。

那么问题是双重的——有没有办法解决溢出的阶乘问题，而不需要在每一步检查乘法溢出或硬编码最大允许参数？

一般来说，我应该如何处理涉及迭代/递归的多个阶段的问题，这些阶段可能会在每个阶段静默失败，而不会通过在每个阶段引入昂贵的检查来影响性能？

4

6 回答 6

1

这取决于您的具体问题。也许你可以做曲线草图或其他一些数学分析。

在您给定的示例中，最好只检查每个循环。它不是那么耗时，因为它甚至不会修改您的复杂性类（因为 O(n) = O(n+n) = O(2n) = O(n)）。在大多数情况下，做一个简单的检查也是最好的选择，因为它可以让你的代码保持干净和可维护。

于 2011-07-17T01:47:40.357 回答
1

虽然 Java 不能帮助您解决这个问题，但肯定有一些语言可以帮助您解决溢出问题。例如，C# 提供了checked 关键字。下面，此功能可能使用溢出标志形式的硬件支持。

于 2011-07-17T05:40:27.187 回答
1

在这种特定情况下，最简单的做法是硬编码最大“n”值。如果速度对您很重要，您会将所有可能的值存储在一个数组中（没有很多）并且不计算任何东西。;)

如果您想改进方法使用long结果（不是更好，而是一个简单的更改）或使用没有溢出问题的 BigInteger。;)

于 2011-07-17T06:46:43.327 回答
0

有没有办法解决溢出的阶乘问题，而不需要在每一步检查乘法溢出或硬编码最大允许参数？

不。

一般来说，我应该如何处理涉及迭代/递归的多个阶段的问题，这些阶段可能会在每个阶段静默失败，而不会通过在每个阶段引入昂贵的检查来影响性能？

我不认为你可以在 Java 中。

如果前一个整数算术运算溢出，一些机器指令集会设置一个“oveflow”位，但大多数编程语言不提供使用它的方法。C# 是一个例外，(IIRC) Ada 也是一个例外。

于 2011-07-17T04:07:06.147 回答
0

从 Java 8 开始，Java 就有了Math.multiplyExact()方法。这会在内部检查溢出。由于该方法是“内在的”（请参阅​​此处的列表），如果可能，Java 实现将被专用的低级机器指令取代，可能只是检查 CPU 溢出标志，从而使检查速度非常快。

顺便说一句，请注意，与 JDK 1.0.8_05 相比，这在 JDK 1.8.0_40 上似乎要快得多。

于 2016-08-23T14:00:46.440 回答
-1

在 Java 中，溢出应该给你一个否定的结果，所以你可以用它作为检查：

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }

    if (p < 0)
    {
        throw new ArithmeticException("factorial: Overflow");
    }

    return p;
}

或者，对于具有正溢出的语言，因为 n! > (n - 1)！你可以试试：

long factorial(int n)
{
    //handle special cases like negatives, etc.

    if (n == 1 || n == 2) { return n; }

    // Calculate (n-1)!
    long p = 2;
    for(int i = 3; i < n; i++)  // Note changes to loop start and end.
    {
        p = p * n;
    }

    long previous = p;  // (n-1)!

    p = p * n;  // Calculate n!

    if (p < previous)
    {
        throw new ArithmeticException("factorial: Overflow");
    }
    return p;
}

这些方法只需要对每个阶乘进行一次检查。

于 2011-07-17T09:48:51.937 回答