Как я могу исправить эту программу расчета комбинаций (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

Для больших чисел используйте 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;
}

Answer 2

Как я могу решить эту проблему, чтобы найти комбинации, даже вводя большие числа для n и r?

• Используйте более широкий целочисленный тип. 32-битный int подходит только для fact(12).

• Вычислить nCr(int n,int r) без использования fact(). Постепенно сформируйте произведение / частное.

• Используйте математику с плавающей запятой и допускайте неточность.

Давайте go для двери №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;
}