Рекурсивная функция для вычисления комбинации и факториала

Я использую следующие две функции для вычисления факториалов и комбинаций.Рекурсивная функция для вычисления комбинации и факториала

public static long Factorial(long n) 
{ 
    if (n == 0) 
     return 1; 
    else 
     return n * Factorial(n-1); 

} 

public static long combinations (long n, long k) 
{  
    return Factorial(n)/(Factorial(k) * Factorial(n - k));  
}

Я проверяю его с помощью:

long test = combinations((long)21, (long)13);

Это похоже на работу для небольших чисел, таких как 5,2. Но если я попробую 21,13, я получаю неправильные ответы (отрицательные или 0).

Кто-нибудь знает, что здесь происходит?

источник

2014-12-12 Anonymous

Какой язык/платформы это такое? –

Ваш ответ может быть здесь: http://stackoverflow.com/questions/849813/large-numbers-in-java –

Не уверен, что мне не хочется его вычислять, но я уверен, что вы столкнулись с условие переполнения. В принципе, долго не хватает мощности для хранения чрезвычайно большого числа, которое является 21 факториалом и, возможно, 13 факториалом. Для больших чисел, подобных этим, используйте класс BigInteger. –

Максимальное значение long в java составляет 2^63.

Это безопасно приведет вас к факториалу 20. Однако факторный коэффициент 21 составляет около 2^65, поэтому вы превышаете максимальное значение, которое может быть представлено.

См. this question для обсуждения того, что происходит в java, если вы выполняете умножение, которое приводит к переполнению.

источник

2014-12-12 01:53:16

Это главным образом из-за переполнения от long (64-битная подпись). Вы можете посмотреть BigDecimal или BigInteger для использования в этом случае.

источник

2014-12-12 01:58:05

BigInteger было бы более подходящим – etherous

Вам нужно деление на служение. –

Я видел, как он использовал длинное разделение, поэтому я понял, что он этого хочет. Вы можете использовать оба варианта: BigInteger для факториала и BigDecimal для комбинаций. Дополнительный кредит для тех, кто использует длинный, обнаруживает переполнение и при необходимости обновляет – etherous

Поскольку другие пользователи уже давно не могут использовать Factorial (21). Я переписал ваш Factorial метод с помощью BigInteger и, похоже, работает, хотя вам нужно передать BigInteger в качестве параметра.

public static BigInteger Factorial(BigInteger n) 
{ 

    if (n.equals(BigInteger.ZERO)) 
     return BigInteger.ONE; 
    else 
     return n.multiply(Factorial(n.subtract(BigInteger.ONE))); 
}

Затем переписать метод комбинации с помощью BigInteger:

public static BigInteger combinations (BigInteger n, BigInteger k) 
{ 
     return Factorial(n).divide(Factorial(k).multiply(Factorial(n.subtract(k)))); 

}

В основной метод я назвал метод сочетания, как этот

System.out.print(combinations(new BigInteger("21"), new BigInteger("13")));

источник

2014-12-12 02:12:42

Рекурсивная функция для вычисления комбинации и факториала

ответ

Смежные вопросы