Блог

У меня есть небольшая программа. Я должен вычислить комбинацию с повторением.
Мой код:

 int factorial(int a){

    if (a<0)
    return 0;
    if (a==0 || a==1)
    return 1;
    return factorial(a-1)*a;
}
long int combinationWithRepetion(int n, int k){
    long int a,b,wyn=0;

    wyn=factorial(n (k-1))/(factorial(k)*factorial(n-1));

    return wyn;
}
int main()
{
    int k,n=0;
    cout<<"Give n: ";
    cin>>n;
    cout<<"Give k: ";
    cin>>k;
    cout<<"combination With Repetion for n="<<n<<
    " k="<<k<<".n Is equal to "<<combinationWithRepetion(n,k)<<endl;
    return 0;
}
  

Для n = 9 и k = 6 в Wolfram alfa я получаю 3003, но в этой программе результат равен 44.

Для меня код в порядке.

С помощью n=9 и k=6 вы вычисляете, factorial(14) что 87,178,291,200 из того, что переполнит 4 байта int . Вам нужно использовать что-то вроде long long , чтобы получить 8-байтовую int формулу, если вы хотите использовать эту формулу.

Существуют лучшие формулы для вычисления биномиальных коэффициентов, которые не зависят от вычисления полных факториалов, а затем выполнения деления. Смотрите Биномиальный коэффициент в языках программирования, прямой метод (вместо использования рекурсии).

В C вы можете использовать:

 int binomial(int N, int K) {
  if( K > N - K )
    K = N - K;
  int c = 1;
  for(int i = 0; i < K;   i) {
    c *= (N - i);
    c /= (i   1);
  }
  return c;
}
  

Итак, вы вычисляете (n k-1), выбираете k . Заменяя n = 9, k = 6, получается 14choose6 (= 3003). Но 14! для представления требуется более 36 бит, но ваш int имеет только 32 бита. Лучшей реализацией было бы упростить n!/ ((n-k)!k!) до n(n-1)…(n-k 1) / k!. Или вы можете использовать pascal triangle.