Resolução de problemas/Combination
Combinação
[editar | editar código-fonte]
Na análise combinatória, a combinação C(n, k) (lê-se: n elementos tomados k a k vezes) define um subconjunto de n com k elementos. O número de combinações é o coeficiente binomial:
Problemas que envolvem a formação de subconjuntos à partir de um determinado espaço amostral podem ser resolvidos usando-se combinação. Por exemplo:
- Dado grupo de 100 pessoas, deseja-se formar comissões de 20 pessoas cada. Quantas comissões diferentes podem ser formadas?
- R: C(100,20)
- Numa escolinha de basquete 30 alunos estão inscritos. Sabendo-se que uma equipe de basquete é composta por 5 atletas, quantas equipes diferentes podemos formar (independente das posições)?
- R: C(30, 5)
Perceba que nos problemas de combinação a ordem dos elementos dentro de um subconjunto não importa.
Para calcularmos computacionalmente o valor exato de n elementos tomados k a k vezes usando a fórmula binomial acima pode tornar-se impossível quando trabalhamos com valores de n e k muito grandes, visto que estamos trabalhando com fatoriais. Tome por exemplo o valor exato de 100!:
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
Um valor que certamente não caberá em um long long int do C. Mesmo que o valor final da combinação caiba em uma variável do tipo long long int, perceba que no denominador da fração há uma multiplicação de fatoriais! Assim, os valores intermediários podem ultrapassar a faixa de valores desse tipo de dados, causando um overflow. Vale salientar que na resolução desse problema a utilização de tipos ponto-flutuante não é permitida.
Então, como fazemos para calcularmos combinações com valores de n e k muito grandes? Por exemplo, C(100, 10)?
Uma possível solução é usarmos o Triângulo de Pascal: um triângulo numérico infinito formados por binômios , em que n representa o número da linha e k o número da coluna.
Calculando o valor dos binômios, temos o seguinte triângulo:
Agora, se quisermos calcular C(100,10) basta calcularmos o elemento que está na 100ª linha e 10ª coluna. Todavia, não é necessário calcularmos o valor de todos os binômios, apenas precisamos conhecer a Relação de Stiffel: cada número do Triângulo de Pascal é igual à soma do número imediatamente acima e seu antecessor.
Abaixo segue uma possível implementação em C para o cálculo de combinações à partir do Triângulo de Pascal:
int main(){
long long int p[MAX+1][MAX+1], N, K;
int i, j;
for(i = 0; i < MAX+1; i++){
for(j = 0; j <= i; j++){
if(j == 0 || j == i) p[i][j] = 1;
else p[i][j] = p[i-1][j] + p[i-1][j-1];
}
}
while(1){
scanf("%lld %lld",&N, &K);
if(N == 0 && K == 0) break;
printf("%lld things taken %lld at a time is %lld exactly.\n", N, K, p[N][K]);
}
return 0;
}
No primeiro trecho do programa, preenchemos o Triângulo de Pascal conforme a Relação de Stiffel. Observe que a 1ª coluna e a diagonal principal devem ser sempre preenchidas com 1.
Em seguida, apenas imprimos na tela a combinação de N tomados K a K vezes.
Veja esse problema em: http://acm.uva.es/p/v3/369.html