Пояснение к расчету ncr

Я читал возможные эффективные методы вычисления ncr, когда наткнулся на этот пост.

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

Второй ответ, данный здесь, я не могу этого понять. Код:

long long combi(int n,int k)
{
    long 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;
}

И в чем будет сложность для этого? Я попытался сделать это на примере, и ответ получился правильным, но каковы эти условия?


c++ binomial-coefficients
person chan chong    schedule 03.10.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

это просто результат оптимизации, он вычисляет

n! / k! (n-k)! = n * (n-1) * ... (n - k + 1) / k * (k-1) * ... * 1

Во-первых: алгоритмическая оптимизация: как C n k = C n (n-k): вычислить тот, у которого меньше терминов - хорошо.

Следующие оптимизации вычислений: при вычислении ans * n / j попытайтесь упростить дробь перед выполнением операции - ИМХО, это очень спорный вопрос, потому что это то, как это сделал бы человек (вы и я вычисляем быстрее 6 / 3, чем 12345678 / 9), но для процессора эта оптимизация просто добавляет лишняя операция.

person Serge Ballesta    schedule 03.10.2014

arrow_upward
0
arrow_downward

Как указано в ссылке, множественное условие в цикле заключается в обработке переполнения при выполнении ans = (ans * n) / j.

Итак, функция:

long long ans = 1;
k = std::min(k, n-k);
int j = 1;
for (; j <= k; j++, n--) {
    ans = (ans * n) / j;
}
return ans;

Имеем C(n, r) = n! / (н-р)! r! и большинство факторов можно упростить.

И сложность k.

person Jarod42    schedule 03.10.2014