Cálculo do número de combinações

O número de combinações  C(n,k) conta quantas maneiras podemos selecionar k elementos distintos em conjunto com n elementos, onde a ordem não importa. Em outras palavras, C(n,k) representa a quantidade de subconjuntos de k elementos de um conjunto com n elementos que pode ser descrito pela seguinte fórmula:

Fato 1:  A quantidade de subconjuntos vazio é igual a 1.

Fato 2: Só existe um subconjunto com n elementos de um conjunto com n elementos.

Fato 3:
Para cada subconjunto com k elementos de um conjunto S com n elementos existe um subconjunto com n-k elementos.

Fato 4:
O número de subconjuntos de um conjunto com n elementos é .

No problema Combination, você precisa calcular C(n,k) para 5<=k<=n<=100 sabendo que este valor pode ser representado em um inteiro de 32 bit.

Mas o valor exato de 100!=93.326.215.443.944.152.681.699.238.856.266.700.490.715.968.264.381.621.468.592.963.895.217.599.993.229.915.608.941.463.976.156.518.286.253.697.920.827.223.758.251.185.210.916.864.000.000.000.000.000.000.000.000

não pode ser representado.

Vamos utilizar a definição recursiva do número de combinação para driblar este problema.

Fato 5:
O número de combinação C(n,k) pode ser computado pela seguinte fórmula recursiva:

Seja x um elemento qualquer do conjunto com n elementos:
Caso 1: Se x pertence ao subconjunto com k elementos então precisamos escolher k-1 elementos de um conjunto com n-1 C(n-1,k-1).
Caso 2: Se x não pertence ao subconjunto com k elementos então precisamos escolher k elementos de um conjunto com n-1 elementos C(n-1,k).

Observe que nesta solução, nenhuma multiplicação ou divisão é necessária apenas adições são realizadas.

#define MAXIMO 100
int main(){
  int c[101][101];
  //fato 1
  for (int i=0;i<=MAXIMO;i++)
  c[i][0]=1;
  //fato 2
  for (int i=0;i<=MAXIMO;i++)
  c[i][i]=1;
  //fato 5
  for (int i=1;i<=MAXIMO;i++)
     //fato 4: a soma dos elementos das linhas é igual 2**i
     for (int k=1;k<=i;k++)
       c[i][k]=c[i-1][k-1]+c[i-1][k];
  while(1){
    int n,m;
    scanf("%d %d",&n,&m);
    if(n==0 && m==0) break;
    printf("%d things taken %d at a time is %d exactly.\n",
n,m,c[n][m]);
  }
}

O cálculo do número de combinações C(n,k) é um problema simples, mas que dependendo da sua implementação pode resultar em um número grande de operações de multiplicação e divisão. Dependendo da ordem em que as operações são realizadas no seu algoritmo e como a linguagem implementa estas instruções, o seu algoritmo pode “estourar” a capacidade de representação numérica do seu tipo de dado (overflow). Para resolver este problema, precisamos cancelar e simplificar a fórmula do número de combinação na medida do possível.

Observe que o produto de quaisquer i termos consecutivos é sempre divisível por i.


int main(){
  while(1){
    int n,k,i;
    long long int res;
    scanf("%d %d",&n,&k);
    if(n==0 && k==0) break;
    //Fato 3 C(n,k)=C(n,n-k)
    if(k > n-k ) k = n-k; 
    res = 1LL;
    for(i=1;i<=k;i++){
      res = res*(n-i+1);
      res = res/i;
    }
    printf("%d things taken %d at a time is %lld exactly.\n",
n,k,res);
  }
}