Пояснение к расчету 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;
}

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

0

Решение

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

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) но для процессора эта оптимизация просто добавит лишнюю операцию.

0

Другие решения

Как и состояние в ссылке, многократное условие в цикле должно обрабатывать переполнение при выполнении 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! / (н-р)! р! и большинство факторов могут быть упрощены.

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

0

По вопросам рекламы [email protected]