расчет комбинации для больших чисел
-
10-12-2019 - |
Вопрос
Я пытаюсь вычислить, делится ли определенная запись в 100-й строке треугольника Паскаля на 3 или нет. Я вычисляю это по формуле nCr, где n = 100, а r — разные записи в 100-й строке.Я использую приведенный ниже код для расчета комбинации
public static double Combination(int n, int m, double comb)
{
for (int r = -1; ++r < m; )
comb = comb * (n - r) / (r + 1);
return comb;
}
Но для таких значений, как 100C16, я получаю большое число, содержащее десятичные дроби и e.Я поискал в Интернете и обнаружил, что на самом деле есть 12 чисел, которые не делятся на 3, но моя программа выдает мне 63 числа, которые не делятся на 3 в 100-й строке, что неверно. Кто-нибудь может сказать мне, что это такое, что я поступаю неправильно.
Решение
Я предполагаю, что «nCr» — это сокращение от n-choose-r или выбрать r из N, верно?
Чтобы узнать, делится ли nCr на три, не нужно вычислять результат, достаточно выяснить, делится ли он на 3.Вы должны увидеть, сколько раз n!делится на 3, и тогда во сколько раз r!делится на 3 и сколько раз (n-r)!является.
Это действительно очень просто – 1!не делится на 3, 2!нет, 3!делится один раз.4!и 5!также делятся один раз.6!делится вдвое, как и 7!и 8!.9!делится на 4 раза и так далее.Дойдите до n (или вычислите формулу, не вычисляя постепенно, это не так уж сложно) и проверьте.
Уточнение - у меня математика изучается где-то на иврите, поэтому "Сколько раз н!делится на 3», возможно, это не совсем правильный английский способ выразить это.По "н!делится на 3 m раз» я имею в виду, что n!=3^m*k
, где k вообще не делится на 3.
РЕДАКТИРОВАТЬ:Пример.Давайте проверим, делится ли 10c4 на 3.
Давайте составим небольшую таблицу, указав, сколько раз k!делится на 3 (k!столбец предназначен только для демонстрации, он вам на самом деле не нужен при вычислении столбца делимости):
k k! Divisibility
1 1 0
2 2 0
3 6 1
4 24 1
5 120 1
6 720 2
7 5040 2
8 40320 2
9 362880 4
10 3628800 4
10c4 = 10!/ (6!*4!) .
10!делится на 4 раза (то есть 10!= 3^4 * Что -то не делится на 3), 6!делится 2 раза 4!делится 1 раз
Итак, 10!(6!* 4!) делится на 3.На самом деле это 3*70.
Другие советы
Прежде всего, вы используете удваивания, я не думаю, что это хорошая идея.Числа плавающих точек дадут ошибки через некоторое время.
Если номер не будет расти, что огромный может использовать следующий метод:
public static long nCr (int m, int n) {
long tmp = 1;
int j = 2;
int k = m-n;
for(int i = m; i > k; i--) {
tmp *= i;
while(j <= n && tmp%j == 0) {
tmp /= j++;
}
}
while(j <= n) {
tmp /= j++;
}
return tmp;
}
.
В этом случае, однако это все еще недостаточно.В этом случае можно использовать структуру BigInteger
в System.Numerics
public static BigInteger nCr (int m, int n) {
BigInteger tmp = 1;
int j = 2;
int k = m-n;
for(int i = m; i > k; i--) {
tmp *= i;
while(j <= n && tmp%j == 0) {
tmp /= j++;
}
}
while(j <= n) {
tmp /= j++;
}
return tmp;
}
.
Вы можете утверждать, что с BigInteger никому не нужно перевязать определение и умножение.Однако, если BigInteger довольно большим, операции по данным займет некоторое время (поскольку число представлено как массив ряд байтов).Удерживая его небольшим, можно избежать длительного расчета времени.