Мне нужно вычислить n!/(n-r)!r!
в С#. Легко вычислить с помощью функции факториала для небольших чисел, но когда число становится больше, например, 100, это не работает. Есть ли другой способ, с помощью которого мы можем вычислить комбинации для больших чисел?
Как рассчитать биномиальные коэффициенты для больших чисел
Ответы (4)
Во-первых, отмечу, что вы пытаетесь вычислить биномиальный коэффициент, поэтому назовем его так.
Вот несколько способов сделать расчет. Если вы используете BigInteger, вам не нужно беспокоиться о переполнении:
Способ первый: используйте факториал:
static BigInteger Factorial(BigInteger n)
{
BigInteger f = 1;
for (BigInteger i = 2; i <= n; ++i)
f = f * i;
return f;
}
static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
return Factorial(n) / (Factorial(n-k) * Factorial(k));
}
Способ второй: используйте рекурсию:
static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
if (n == 0) return 1;
if (k == 0) return 0;
return BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k)
}
Однако этот метод не быстрый, если вы не запомните результат.
Метод третий: будьте более умны в минимизации количества умножений и делении раньше. Это делает цифры небольшими:
static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
// (n C k) and (n C (n-k)) are the same, so pick the smaller as k:
if (k > n - k) k = n - k;
BigInteger result = 1;
for (BigInteger i = 1; i <= k; ++i)
{
result *= n - k + i;
result /= i;
}
return result;
}
Так, например, если вы вычисляли (6 C 3), вместо вычисления (6 х 5 х 4 х 3 х 2 х 1) / ((3 х 2 х 1) х (3 х 2 х 1)), вы вычисляете (((4 / 1) * 5) / 2) * 6) / 3, что позволяет по возможности уменьшить числа.
if( k == 0 )...
, что и выше, решает эту проблему.
- person LBushkin; 09.03.2012
k==0
должен дать результат 1
. | Очень интересно, что метод 3 работает. Для меня не очевидно, что деление на i
никогда не оставляет остатка.
- person CodesInChaos; 10.03.2012
(((n) / 1) * (n+1)) / 2
. Ясно, что либо n, либо n+1 делится на два. Предположим, у нас есть ((((n) / 1) * (n+1)) / 2) * (n+2) / 3
— мы уже позаботились о 2. Очевидно, что одно из n, n+1 или n+2 делится на 3. И так далее. Каждый раз мы делим на значение, которое должно появляться как фактор в текущем или предыдущем термине.
- person Eric Lippert; 13.03.2012
Следуя тому, что сказал Эрик, раннее деление очень помогает, вы можете улучшить это, деля от большего к меньшему. Таким образом, вы можете рассчитать любой результат, если конечный результат соответствует Long. Вот код, который я использую (извиняюсь за Java, но преобразование должно быть простым):
public static long binomialCoefficient(int n, int k) {
// take the lowest possible k to reduce computing using: n over k = n over (n-k)
k = java.lang.Math.min( k, n - k );
// holds the high number: fi. (1000 over 990) holds 991..1000
long highnumber[] = new long[k];
for (int i = 0; i < k; i++)
highnumber[i] = n - i; // the high number first order is important
// holds the dividers: fi. (1000 over 990) holds 2..10
int dividers[] = new int[k - 1];
for (int i = 0; i < k - 1; i++)
dividers[i] = k - i;
// for every divider there always exists a highnumber that can be divided by
// this, the number of highnumbers being a sequence that equals the number of
// dividers. Thus, the only trick needed is to divide in reverse order, so
// divide the highest divider first trying it on the highest highnumber first.
// That way you do not need to do any tricks with primes.
for (int divider: dividers)
for (int i = 0; i < k; i++)
if (highnumber[i] % divider == 0) {
highnumber[i] /= divider;
break;
}
// multiply remainder of highnumbers
long result = 1;
for (long high : highnumber)
result *= high;
return result;
}
Для .net 4.0 и выше используйте класс BigInteger вместо int/long.
Для других .net используйте собственный класс больших чисел, например, из IntX: http://www.codeplex.com/IntX/
Я думаю, это будет эффективно
Это O(k)
заметьте н! / р! р! просто отменяет последний r из n
так что 7 3
7 x 6 x 5 x 4 x 3 x 2 x 1
over
4 x 3 x 2 x 1
public static uint BinomialCoeffient(uint n, uint k)
{
if (k > n)
return 0;
uint c = n;
for (uint i = 1; i < k; i++)
{
c *= n - i;
c /= i + 1;
}
return c;
}
BigInteger
, но я не знаю, насколько большими они могут стать. Вы также можете создать n-битный массив и сохранить число как двоичное число, но установить ячейки массива, но это потребует дополнительных вычислений. - person twain249   schedule 08.03.2012