Сочетание с повторением, различия в расчете

Question

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

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.

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

Answer 1

С 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;
}

Answer 2

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