计算在C二项式系数 [英] Computing the binomial coefficient in C

问题描述

我发现下面的code计算 nCr的，但不明白的其背后的逻辑。为什么这code的工作？

 长长COMBI（INT N，INT K）
{
    长长的ANS = 1;
    K = K＆GT; N-K N-K：K;
    INT J = 1;
    对于（; J＆LT; = K，J ++，N--）
    {
        如果（N引用％j == 0）
        {
            ANS * = N / J;
        }其他
        如果（ANS引用％j == 0）
        {
            ANS = ANS / J * N;
        }其他
        {
            ANS =（ANS * N）/ J;
        }
    }
    返回答;
}
 

解决方案

这是一个聪明的code！

在一般它的目的是计算公式如下：

  ANS = N！ /（K！）（N-K）！
 

这等于：

  ANS = N（N-1）（N-2）...（NK）... 1 / K（K-1）... 1 *（NK） （NK-1）1 ...
 

和明显的后取消：

  ANS = N（N-1）（N-2）..（N-K + 1）/ K！
 

现在注意到，提名和分母有相同数量的元素（K元素）

所以ANS的计算将是这样的：

  ANS = 1 //开始
ANS * = N / 1
答* =（N-1）/ 2
答* =（N-2）/ 3
。
。
。
答* =（N-K + 1）/ K
 

在code再看看，你注意的是：

1. 答正在乘以 N 在每次迭代


2. N 减1在每次迭代（ N - ）


3. 答是在每次迭代
分Ĵ

这是究竟是什么在公布的code做的，现在让我们看看在不同条件的含义在循环，以提名人从 N 和分母开始1 K ，所以变量Ĵ分配给分母吧？

1）如果（N引用％j == 0）

此时如果ñ/ J 是（可计算的），所以我们计算它第一次在这里比乘以整个答，这种做法保持在结果的最小可能值。

2）否则如果（ANS引用％j == 0）

在每一步，如果我们无法计算ñ/ J ，但实际上可以计算 ANS / J 所以这是不坏的说：

  ANS / = j的; //首先我们把
ANS * = N; //然后我们乘
 

这是始终保持我们的整体输出尽可能小，对吧？

3）最后一个条件

在每一步，如果我们不能计算既不ñ/ J 也不 ANS / J 在这种情况下，我们不是幸运地先分再乘（因此保持小的结果）。但同时，我们需要进行有选择只有一个偶数，虽然我们留下这是

  ANS * = N; //先乘
ANS / = j的; //然后鸿沟
 

ET瞧！

示例
考虑的情况下 3C7
我们知道，答案是7！/ 3！* 4！
因此： ANS = 7 * 6 * 5/1 * 2 * 3

让我们来看看在每次迭代发生什么：

  // 1
ANS = 1// 2
N = 7
J = 1
ANS = ANS * N / J
第一个计算7/1 = 7
再乘到ANS
ANS = 1 * 7
ANS = 7// 3
N = 6
J =
ANS = ANS * N / J评价N / J = 6/2（又可）
         N / J = 3
ANS = ANS *（N / J）
    = 7 * 3
    = 21// 4
N = 5
J = 3ANS = ANS * N / J
评价N / J = 5/3 oppsss！ （第一IF）
评估ANS / J = 21/3 = 7 YES（第二IF）ANS =（ANS / J）* N
    = 7 * 5
    = 35//迭代结束
 

请注意，在最后一次迭代，如果我们计算直线前进，我们会说：

  ANS = ANS * N / J
    = 21 * 5/3
    =三分之一百○五
    = 34
 

是的，它确实找到了不错的成绩，但同时该数值又回到了前35苍蝇达105现在想象一下，计算实大数？！

结论
这code为计算仔细二项式系数试图保持输出尽可能小在计算的每一步，它是通过检查，如果有可能分裂（ INT ），然后执行，因此它是能够计算的一些非常大的 KCN 的简单的编码不能处理（溢出，可能会出现）

I found the following code for computing nCr, but don't understand the logic behind it. Why does this code work?

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;
}

解决方案

that's a clever code!

In general it aims to calculate the following formula:

ans = n! / (k!)(n-k)!

It is equal to:

ans = n(n-1)(n-2) ... (n-k)...1 / k(k-1)...1 * (n-k)(n-k-1) ... 1

And after obvious cancellation:

ans = n(n-1)(n-2)..(n-k+1) / k!

Now notice that nominator and denominator have the same number of elements (k element)

So the calculation of ans will be like the following:

ans  = 1 // initially
ans *= n/1
ans *= (n-1)/2
ans *= (n-2)/3
.
.
.
ans *=  (n-k+1)/k

take a look again at the code and you notice that:

1. ans is being multiplied by n at each iteration
2. n is reduced by 1 at each iteration (n--)
3. ans is divided by j at each iteration

This is exactly what is done by the posted code, Now let's see the meanings of different conditions in the loop, with nominator starting from n and denominator from 1 to k, so variable j is assigned to denominator right?

1) if(n%j==0)

at each step if n/j is (computable) So we calculate it first here than multiply to the whole ans, this practice keeps the result at its smallest possible value.

2) else if(ans%j==0)

at each step if we couldn't calculate n/j but actually can calculate ans/j so that's not bad to say :

ans /= j; //first we divide
ans *= n; //then we multiply

This is always keeping our overall output as small as possible, right?

3) last condition

at each step, if we couldn't compute neither n/j nor ans/j in this case we are not lucky enough to divide first then multiply (hence keeping the result small). But well we need to carry on even-though we are left with only one choice which is

ans *= n; // multiply first
ans /= j; // then divide

ET VOILA!

Example consider the case 3C7 we know that the answer is 7!/ 3!*4! hence : ans = 7*6*5 / 1*2*3

let's see what happen at each iteration:

//1 
ans = 1

//2 
n = 7
j = 1
ans = ans * n/j 
first compute 7/1 = 7
then multiply to ans
ans = 1*7
ans = 7

//3
n = 6
j = 2
ans = ans* n/j

evaluate n/j = 6/2 (can be divided)
         n/j = 3
ans = ans *(n/j)
    = 7 * 3
    = 21

// 4
n = 5
j = 3

ans = ans * n/j
evaluate n/j = 5/3 oppsss!! (first if)
evaluate ans/j = 21/3 = 7 YES (second if)

ans = (ans/j)*n
    = 7*5
    = 35

// end iterations

Note that in last iteration if we calculate straight forward we would say:

ans = ans*n/j
    = 21 * 5 / 3
    = 105 / 3
    = 34 

yes it does find right result but meanwhile the value flies up to 105 before getting back to 35. Now imagine calculating real large numbers?!

Conclusion This code is computing carefully the binomial coefficients trying to keep the output as small as possible at each step of calculation, it does that by checking if it is possible to divide (int) then execute, hence it is capable of calculating some very big kCn that the straightforward coding cannot handle (OverFlow may occur)

这篇关于计算在C二项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！