如何修复此组合计算(NCr)程序？

Question

我用c创建了这个简单的程序来计算组合。但是每当我输入大的值，比如20,30,40.对于变量'n‘和'r’程序输出不是真。但是这个程序对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()。分步骤形成积/商。
• 使用浮点数学，容忍不精确。

让我们进入第二道门，在每一步中使用*和/。

例如，有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;
}