在 Java 中编码最多阶乘 23

Question

我需要写出 23 以内的阶乘！我最多可以做 20 的阶乘！但在那之后我迷路了，因为数字太大了。 我不能使用 BigInteger。

我必须从最右边的数字开始存储 0，因此示例输出：

10个！ = 3628800 --> fac=36288, num10 = 2

23个！ = 2585..976640000 --> fac= 2585..97664, num10 = 4

import java.util.Scanner;

public class Factorial10{
    public static void main(String[] args){
        long fac;       // long: factorial is very large
        long pre_fac;       // to check overflow
        int i, n;
        int num10;

        Scanner sc = new Scanner(System.in);

        System.out.print("n? ");
        n = sc.nextInt();

        // Start from fac = 0! = 1
        for(i= 1, fac= 1L; i<n; i++){
            pre_fac = fac;
            fac *= i;

            // check if overflowed
            if(pre_fac != fac /i){
                System.out.println("Overflowed at " + i + "! = " + fac);
                fac = pre_fac;      // roll back to the previous, unoverflowed
                break;
            }
        }

        System.out.println((i-1) + "! = " + fac + "(fac = , num10 = )");
    }
}
```

Answer 1

您可以使用 java.lang.math

的 class BigDecimal

但这会占用你所有的记忆。

Is there any replacement of long double in java?

Answer 2

你有没有试过用double而不是long。作为 Double.Max 中的文档 - 它最多可以容纳 1.7976931348623157e+308

Answer 3

如果你不能使用BigInteger，那么你可以尝试实现自己的大数库：

How to handle very large numbers in Java without using java.math.BigInteger

Answer 4

只需实现你自己的那种大整数：

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    int[] factorial = factorial(n);
    for (int i = factorial.length - 1; i >= 0; i--) {
      System.out.print(factorial[i]);
    }
  }

  static int[] factorial(int n) {
    int[] factorial = { 1 };
    for (int i = 1; i <= n; i++) {
      factorial = multiply(factorial, i);
    }
    return factorial;
  }

  static int[] multiply(int[] multiplicand, int multiplicator) {
    int carry = 0;
    for (int j = 0; j < multiplicand.length; j++) {
      multiplicand[j] = multiplicand[j] * multiplicator + carry;
      carry = multiplicand[j] / 10;
      multiplicand[j] %= 10;
    }
    while (carry > 0) {
      multiplicand= Arrays.copyOf(multiplicand, multiplicand.length + 1);
      multiplicand[multiplicand.length - 1] = carry % 10;
      carry /= 10;
    }
    return multiplicand;
  }
}

Try it online!

Answer 5

大多数人错过了问题的关键部分：

I have to store the 0s from the rightmost digit

10 有因数 2 和 5，所以你只需要存储 1 到 23 之间的每个数字被 2 和 5 除的频率。

例如，10:

i    1 2 3 4 5 6 7 8 9 10    SUM
div2 0 1 0 2 0 1 0 3 0  1      8
div5 0 0 0 0 1 0 0 0 0  1      2

正如我们所见，两个和的最小值是2，所以10!应该以00结束。
事实上，10! 是 3628800.
这背后的数学是 10! = x * 2^8 * 5^2，对于一些不能除以 2 或 5 的 x。

另一个观察结果是 5 的数量增加得慢得多，所以我们可以跳过计算 2。

有了这些知识，我们可以通过检查每个数字除以 5 的频率来计算结尾 0 的数量：

private static int numZerosInFactorial(int n) {
    int divBy5 = 0;
    for (int i = 1; i <= n; i++) {
         for (int j = i; (j % 5) == 0; j /= 5) {
             divBy5++;
         }
    }
    return divBy5;    
}

（您可以对上述方法做一些小的改进）

现在的另一个问题是：你真的需要n!的值吗？
如果是，精度是多少？现在用double计算n!可以吗？

感谢 from Michael，我注意到我们实际上可以计算不带零的阶乘，然后使用字符串连接来显示结果。

在计算不带零的阶乘时，我们基本上必须做与 numZerosInFactorial 中所做的相反的事情，所以我们不是乘以 5 的倍数，而是除以 2：

private static long factorialWithoutZeroes(int n) {
    long result = 1;
    for (int i = 1; i <= n; i++) {
        long div = 1;
        int j;
        for (j = i; (j % 5) == 0; j /= 5) {
            div *= 2;
        }
        result = result / div * j;
    }
    return result;
}

最终结果为：

// We have already read n from stdin
long fac = factorialWithoutZeroes(n);
int num10 = numZerosInFactorial(n);
System.out.println(n + "! = " + (fac + "0".repeat(num10)) + " (fac = " + fac + " , num10 = " + num10 + ")");

事实上，这种方法最多适用于 n == 23。输出格式很好地暗示这是预期的方法。

在 Java 中编码最多阶乘 23

Coding up to Factorial 23 in Java

java

factorial