c++ - 在计算所有可能路径问题时计算 nCr

Question

我怀疑作者是如何得出公式背后的直觉来计算这个问题中的 (m + n -2)C n-1 - https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

请使用组合学向下滚动到解决方案。

特别是说，我不明白下面的代码是如何为基本上是 nCr 的

 for (int i = n; i < (m + n - 1); i++) { 
        path *= i; 
        path /= (i - n + 1); 
    } 

我的意思是，如果我把值(value)观放进去，我就会明白。但是，如果你理解我的痛苦，如果我不知道，我将如何达到这个目标。搜索如何计算 nCr 给出了不同的解决方案。

这是一些付诸实践的观察。即使任何人都可以为我指出一个不同的直接公式来计算相同的东西也会很棒。毕竟，如果没有可能需要时间的观察，要消耗它并不是那么容易。只是同时好奇为什么不能使用标准方法来解决 nCr。就像这里的 - https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/

Answer 1

nCr(n,k) 的公式是:

| n |      n!
|   | = ---------
| k |   k!.(n-k)!

问题是阶乘很快就会变得非常大，即使对于小的输入也会溢出标准变量。为了避免这种情况，我们只是消除了冗余操作......我可以重写为:

| n |      n!       1*2*3*...*n
|   | = --------- = -----------------------------
| k |   k!.(n-k)!   1*2*3*...*k * 1*2*3*...*(n-k)

现在我们可以看到第一个 n-r或 k (取决于哪个更大)除法两边的乘法相同，因此我们可以跳过它们(以 k>=n-r 为例):

| n |      n!       (k+1)*(k+2)*(k+3)*...*n
|   | = --------- = -----------------------------
| k |   k!.(n-k)!       1*2*3*...*(n-k)

此外，如果我们在循环中执行此操作并在每次乘法后除法，则子结果将保持较小:

| n |      n!       (k+1)   (k+2)   (k+3)          (n)
|   | = --------- = ----- * ----- * ----- * ... * -----
| k |   k!.(n-k)!     1       2       3           (n-k)

是的，该部门的两侧都有相同数量的therms。如果我理解正确，您的代码应该是 nCr(m+n-2,n-1)所以匹配公式的替换将是:

n` = m+n-2
k` = n-1

重写为:

| m+n-2 |   (n-1+1)   (n-1+2)   (n-1+3)           (m+n-2)
|       | = ------- * ------- * ------- * ... * -----------
|  n-1  |     1          2         3            (m+n-2-n+1)

| m+n-2 |   (n)   (n+1)   (n+2)         (m+n-2)
|       | = --- * ----- * ----- * ... * -------
|  n-1  |    1      2       3            (m-1)

所以你的循环正在做 PI的 i/(i-n+1)在哪里 i={ n,n+1,...,m+n-1 }符合上面的等式...
注意这不准确nCr 因为它需要在浮点上计算，所以每次迭代都会出现舍入错误!!! 所以输出可能会稍微偏离一点!!! 然而，这可以以类似的方式在整数上计算(没有任何精度损失)，但不是在每次迭代中除法，而是将两个除数与公约数除以保持它们“小”。理想情况下是前几个素数。这里有一个小的 C++ 示例(浮点和 int 版本)，我只是匆匆忙忙:

//---------------------------------------------------------------------------
//
//  | n |      n!       combinations = fact(n)/(fact(k)*fact(n-k))
//  |   | = ---------   how many combinations of k items from n items are possible
//  | k |   k!.(n-k)!   when order does not matter
//
DWORD nCr(DWORD n,DWORD k)
    {
    DWORD a,b,ia,ib,j,m,p;
    const DWORD prime[]={2,3,5,7,11,13,17,19,23,29,31,0};
    if (k> n) return 0;
    if (k==n) return 1;
    m=n-k;
    for (a=1,b=1,ia=k+1,ib=2;(ia<=n)||(ib<=m);)
        {
        if ((b<=a)&&(ib<=m)){ b*=ib; ib++; }    // multiply the smaller number if possible
        else     if (ia<=n) { a*=ia; ia++; }
        for (;((a|b)&1)==0;a>>=1,b>>=1);        // divide a,b by 2 if possible
        for (j=1;;j++)                          // divide a,b by next few prmes (skip 2) if possible
            {
            p=prime[j];
            if (!p) break;
            if (a<p) break;
            if (b<p) break;
            for (;(a%p)+(b%p)==0;a/=p,b/=p);
            }
        }
    return a/b;
    }
//---------------------------------------------------------------------------
float nCr_approx(DWORD n,DWORD k)
    {
    if (k> n) return 0;
    if (k==n) return 1;
    float c;
    DWORD i,m=n-k;
    for (c=1.0,i=1;i<=m;i++)
        {
        c*=(k+i);
        c/=(i);
        }
    return c;
    }
//---------------------------------------------------------------------------

在哪里 DWORD是 32 位无符号整数(但可以使用任何整数变量类型)...这可以正常工作(在 32 位上)直到 nCr(32,15)下面是两者的对比:

 n    k   nCr(n,k)     nCr_approx(n,k)
 32   0          1               1.000 
 32   1         32              32.000 
 32   2        496             496.000 
 32   3       4960            4960.000 
 32   4      35960           35960.000 
 32   5     201376          201376.000 
 32   6     906192          906191.938  *** float is off
 32   7    3365856         3365856.000 
 32   8   10518300        10518300.000 
 32   9   28048800        28048802.000  *** float is off 
 32  10   64512240        64512240.000 
 32  11  129024480       129024488.000  *** float is off 
 32  12  225792840       225792864.000  *** float is off 
 32  13  347373600       347373632.000  *** float is off 
 32  14  471435600       471435584.000  *** float is off 
 32  15  565722720       565722688.000  *** float is off 
 32  16   64209478       601080384.000  *** int overflow
 32  17  565722720       565722752.000  *** float is off  
 32  18  471435600       471435584.000  *** float is off 
 32  19  347373600       347373600.000 
 32  20  225792840       225792832.000  *** float is off  
 32  21  129024480       129024488.000  *** float is off  
 32  22   64512240        64512236.000  *** float is off  
 32  23   28048800        28048800.000 
 32  24   10518300        10518299.000  *** float is off  
 32  25    3365856         3365856.000 
 32  26     906192          906192.000 
 32  27     201376          201376.000 
 32  28      35960           35960.000 
 32  29       4960            4960.000 
 32  30        496             496.000 
 32  31         32              32.000 
 32  32          1               1.000 

是的，您可以使用 double相反，但请始终牢记结果可能会略有偏差!