расчет комбинации для больших чисел

Question

Я пытаюсь вычислить, делится ли определенная запись в 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-й строке, что неверно. Кто-нибудь может сказать мне, что это такое, что я поступаю неправильно.

Answer 1

Я предполагаю, что «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.

Answer 2

Прежде всего, вы используете удваивания, я не думаю, что это хорошая идея.Числа плавающих точек дадут ошибки через некоторое время.

Если номер не будет расти, что огромный может использовать следующий метод:

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 довольно большим, операции по данным займет некоторое время (поскольку число представлено как массив ряд байтов).Удерживая его небольшим, можно избежать длительного расчета времени.