时间戳

首页 > 解决方案 > 在计算所有可能路径问题时计算 nCr

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

问题描述

我怀疑作者是如何得出公式背后的直觉来计算这个问题中的 (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); 
    }

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

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

标签： c++combinatoricsncr

解决方案

的公式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改用，但请始终牢记结果可能会略有偏差！

推荐阅读