c - 如何修复此组合计算（nCr）程序？

Question

我使用 c 创建了这个简单的程序来计算组合。但是，每当我为变量“n”和“r”输入较大的值（如 20、30、40..）时，程序输出都是不正确的。但是这个程序适用于像 5,7,10 这样的小数字......我如何解决这个问题以找到组合，甚至输入大数字 n 和 r ？

我也想在这个程序中使用 nCr = n-1Cr + n-1Cr-1 规则，我正在使用 C 语言

#include <stdio.h>

int fact(int i){             

    if(i <= 1){
        return 1;       
    }
    return i * fact(i-1);
} 


int nCr(int n,int r){

    int nCr;

    if(r == 0 || n == r){
        nCr = 1;
    }else{

        nCr = (fact(n-1)/(fact(r) * fact(n-1-r))) + (fact(n-1)/(fact(r-1) * fact(n-r)));

    }
    return nCr;
}

int main(){

    int n,r;

    printf("Enter n : ");
    scanf("%d",&n);
    printf("Enter r : ");
    scanf("%d",&r);

    printf("nCr value : %d\n",nCr(n,r));
    return 0;
}

非常感谢您的回答。

Answer 1

我该如何解决这个问题以找到组合，甚至输入大数字 n 和 r ？

• 使用更广泛的整数类型。32位int只好到fact(12).

• 计算nCr(int n,int r)而不使用fact(). 逐步形成产品/商。

• 使用浮点数学并容忍不精确性。

让我们去 2 号门。在每个步骤中使用的想法*和。/

例如，有 52 张牌，就有2,598,960种不同的强力牌。

uintmax_t nCr(unsigned n, unsigned r) {
  uintmax_t y = 1;
  if (r <= n) {
    if (n - r + r < r + r) {
      r = n - r;
    }
    for (unsigned i = 1; i <= r; i++) {
      y = y * (n - r + i) / i;
    }
  }
  return y;
}

int main(void) {
  printf("%ju\n", nCr(52, 5));  // 2598960
  return 0;
}

Answer 2

对于大量使用long long int而不是int. 试试这个：

#include <stdio.h>

long long int fact(long long int i){             

if(i <= 1){
    return 1;       
}
   return i * fact(i-1);
} 


long long int nCr(long long int n,long long int r){

long long int nCr;

if(r == 0 || n == r){
    nCr = 1;
}else{

    nCr = (fact(n-1)/(fact(r) * fact(n-1-r))) + (fact(n-1)/(fact(r-1) * fact(n-r)));

}
    return nCr;
}

int main(){

    long long int n,r;

    printf("Enter n : ");
    scanf("%lld",&n);
    printf("Enter r : ");
    scanf("%lld",&r);

    printf("nCr value : %lld\n",nCr(n,r));
    return 0;
}