Кодирование до факториала 23 в Java

Question

Мне нужно записать факториал до 23! Я могу сделать факториал до 20! но после этого я теряюсь, потому что число становится слишком большим. Я не могу использовать BigInteger.

Я должен хранить 0 с самого правого di git, поэтому пример выводит:

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

Большинство пропускают важную часть вашего вопроса:

Я должен хранить 0 с самого правого ди git

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.

Другое наблюдение состоит в том, что число 5 увеличивается намного медленнее, поэтому мы можем пропустить подсчет 2 с.

С этим знанием мы можем вычислить число конечных 0, проверяя, как часто каждое число делится на 5:

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!?
И если да, то с какой точностью? Можно ли рассчитывать n! с double сейчас?

---

Благодаря комментарию от Майкл , я заметил, что мы на самом деле можем рассчитать факториал без нулей, а затем использовать конкатенацию строк для отображения результата.

При вычислении факториала без нулей мы должны в основном делать то, что мы делали в 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. И выходной формат - хороший намек на то, что это ожидаемый подход.

Answer 2

Просто реализуйте свой собственный вид большого целого числа:

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;
  }
}

Попробуйте онлайн!

Answer 3

Если вы не можете использовать BigInteger, то вы можете попробовать реализовать собственную библиотеку больших чисел:

Как обрабатывать очень большие числа в Java без использования java .math .BigInteger

Answer 4

Вы пытались использовать double вместо long. Как документация в Double.Max - он может вместить до 1.7976931348623157e + 308

Answer 5

Как уже упоминалось выше в комментариях, вы можете использовать BigInter для хранения больших значений. Вот пример кода:

 for (i = 1, fac = new BigInteger("1"); i < n; i++) {
        pre_fac = fac;
        fac = fac.multiply(BigInteger.valueOf(i));

}

Answer 6

Вы можете использовать класс BigDecimal java.lang.math

Но это может занять всю вашу память.

Есть ли замена long double в java