Расчет комбинации для больших чисел - PullRequest
Новая
       22

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

0 голосов
/ 10 марта 2012

Я пытаюсь вычислить, делится ли конкретная запись в сотой строке треугольника Паскаля на 3 или нет. Я рассчитываю это, используя формулу nCr, где n = 100, а r - разные записи в сотой строке. , Я использую приведенный ниже код для расчета комбинации 

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

Ответы [ 2 ]

1 голос
/ 10 марта 2012

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

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

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

1 голос
/ 10 марта 2012

Я предполагаю, что "nCr" является сокращением для n-choose-r, или выберите r из N, верно?

Чтобы увидеть, делится ли nCr на три, вам не нужно вычислять результат, вам просто нужно выяснить, делится ли он на 3. Вы должны увидеть, сколько раз n! делится на 3, а затем, сколько раз г! делится на 3 и сколько раз (n-r)! есть.

Это действительно довольно просто - 1! не делится на 3, 2! нет, 3! делится один раз. 4! и 5! также делятся один раз. 6! делится в два раза, и 7 тоже! и 8 !. 9! делится в 4 раза и так далее. Перейдите полностью к n (или выработайте формулу без пошаговых вычислений, это не так уж сложно) и проверьте.

Разъяснение - моя математика учится где-то на иврите, так что "Сколько раз n! Делится на 3" может не быть правильным английским способом сказать это. Под "n! Делится в 3 раза" я имею в виду 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.

...