我怀疑作者如何得出公式背后的直觉来计算此问题中的(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/
最佳答案
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)
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 ，因为它需要在浮点上计算，因此每次迭代都会发生舍入错误! 因此输出可能会有点小!!! 但是，这可以类似的方式在Integer上进行计算(没有任何精度损失)，但是除了在每次迭代中进行划分之外，您还可以将两个划分为公共(public)因子的划分为小数。理想情况下，前几个素数。在这里，我只是整理了一个小的C++示例(float和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位无符号整数(但可以使用任何整数变量类型)...这在nCr(32,15)之前(在32位上)正常工作此处，两者之间的比较: 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，但请始终牢记结果可能会略有差异!