Какой лучший способ расчета nCr

Ответ 1

Оба подхода сэкономят время, но первая из них очень подвержена целочисленному переполнению.

Подход 1:

Этот подход сгенерирует результат в кратчайшие сроки (не более, чем в n/2 итерациях), и возможность переполнения может быть уменьшена путем тщательного умножения:

long long C(int n, int r) {
    if(r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

Этот код начнет умножение числителя с меньшего конца, и поскольку произведение любых целых чисел k делится на k!, проблема делимости не будет. Но возможность переполнения все еще существует, другой полезный трюк может делить n - r + i и i на их GCD, прежде чем выполнять умножение и деление (и может продолжаться переполнение).

Подход 2:

В этом подходе вы фактически создадите Pascal Triangle. Динамический подход намного быстрее, чем рекурсивный (первый - O(n^2), а другой - экспоненциальный). Однако вам также потребуется использовать O(n^2) память.

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

Затем вы можете найти любой C(n, r) в O(1) время.

Если вам нужен конкретный C(n, r) (т.е. полный треугольник не нужен), тогда потребление памяти может быть сделано O(n), переписав ту же строку треугольника сверху вниз.

# define MAX 100
long long row[MAX + 1]; // initialized with 0 by default if declared globally

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

Внутренний цикл запускается с конца, чтобы упростить вычисления. Если вы запустите его из индекса 0, вам понадобится другая переменная для хранения перезаписываемого значения.

Ответ 2

Я думаю, что ваш рекурсивный подход должен эффективно работать с DP. Но он начнет давать проблемы после увеличения ограничений. См. http://www.spoj.pl/problems/MARBLES/

Вот функция, которую я использую в онлайн-судьях и конкурсах кодирования. Таким образом, он работает довольно быстро.

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

Это эффективная реализация для вашего подхода № 1

Ответ 3

Ваш рекурсивный подход хорош, но использование DP с вашим подходом еще раз уменьшит накладные расходы на решение подзадач. Теперь, поскольку у нас уже есть два условия -

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

Теперь мы можем легко построить решение DP, сохранив наши подвыборы в двухмерном массиве -

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

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

Самый быстрый метод, который я знаю, - это метод Владимира. Один избегает деления, разлагая nCr на простые множители. Поскольку Владимир говорит, что вы можете сделать это довольно эффективно, используя сито Eratosthenes. Также используйте небольшую теорему Ферма для вычисления nCr mod MOD (где MOD - простое число).

Ответ 4

unsigned long long ans = 1,a=1,b=1;
        int k = r,i=0;
        if (r > (n-r))
            k = n-r;
        for (i = n ; k >=1 ; k--,i--)
        {
            a *= i;
            b *= k;
            if (a%b == 0)
            {
                a = (a/b);
                b=1;
            }
        }
        ans = a/b;