Resolução de problemas: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Linha 1:
== [[Problem 369: Combinations ==Combination]]
 
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:<br> <center> [[Image:coefBin.png]] </center>
 
No entanto, calcular computacionalmente o valor exato de n elementos tomados k a k vezes usando a fórmula acima pode ser 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,<br>
: 468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,<br>
: 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. 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]]. Se quisermos calcular C(100,10) basta calcularmos o elemento que está na 100ª linha e 10ª coluna. Para tanto, 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.<br> <center> [[Image:stiffel1.png]] + [[Image:stiffel2.png]] = [[Image:stiffel3.png]]</center>
 
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 preenchida 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