Превышение лимита времени при расчете биномиальных коэффициентов (треугольник Паскаля)

Вопрос состоял в том, чтобы вычислить количество биномиальных коэффициентов, не делящихся на заданное простое число. Например:

Для num = 5 и prime = 5 вывод должен быть:

countingBinomialCoefficient(num, prime) = 17

N = 0: [1]
N = 1: [1, 1]
N = 2: [1, 2, 1]
N = 3: [1, 3, 3, 1]
N = 4: [1, 4, 6, 4, 1]
N = 5: [1, 5, 10, 10, 5, 1]

В приведенном выше примере только 5, 10, 10, 5 делятся только из 21 чисел. Таким образом, результат равен 17.

Код, который я написал, выглядит следующим образом:

long countingBinomialCoefficient(int num, int prime) {
    long count = 0;
    for (int i = 0; i <= num; i++) {
        long nCk = 1;
        for (int j = 0; j <= i; j++) {
            if (nCk % prime != 0) count++;
            nCk = nCk * (i - j) / (j + 1);
        }
    }
    return count;
}

Правильный вывод для двух случаев:
1. countingBinomialCoefficient(5, 5) = 17
и
2.countingBinomialCoefficient(5, 7) = 21

Но он говорит, что лимит времени (= 3000 мс) превышен в случае
countingBinomialCoefficient(999999999, 7), и в этом случае вывод должен быть 2129970655314432
есть ли ошибка в моем коде? Есть ли другие более короткие методы для этого? Пожалуйста помоги. Заранее спасибо.


java arrays binomial-coefficients pascals-triangle
person FlarrowVerse    schedule 07.05.2017    source источник
comment
В вашем коде нет ошибок (за исключением некоторого переполнения числа для больших биномиальных коэффициентов), но он использует наивный алгоритм, который занимает очень много времени для больших n. Вам нужно найти лучший метод. Поэкспериментируйте с бумагой и карандашом, отмечая числа, не делящиеся на простое число, и посмотрите, сможете ли вы найти закономерность. Это должно позволить вам получить счет, не глядя на каждое число.   -  person Henry    schedule 07.05.2017
comment
Ну, мне кажется разумным, что если у вас есть двойной цикл O(n^2) code с n=1b, это может занять некоторое время...   -  person Yossi Vainshtein    schedule 07.05.2017

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы сократить время вычисления этого кода, вы можете сначала заменить внешний цикл на parallel поток. Это может сократить время вдвое или более.

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

static long countingBinomialCoefficient(int num, int prime) {
    return IntStream.rangeClosed(0, num)
            .parallel()
            .mapToLong(i -> {
                long count = 0;
                long nCk = 1;
                for (int j = 0; j <= i; j++) {
                    if (nCk % prime != 0) count++;
                    nCk = nCk * (i - j) / (j + 1);
                }
                return count;
            }).sum();
}

// test failed in my case on one computer
public static void main(String[] args) {
    long time = System.currentTimeMillis();
    System.out.println(countingBinomialCoefficient(99999, 7)); // 2214367021
    System.out.println(System.currentTimeMillis() - time); // 24941
}

См. также: Параллельное умножение матриц

person Community    schedule 19.02.2021