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
Sem resumo de edição
Linha 1:
== Problem 369: Combinations ==
== Índice ==
 
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çoes é o coeficiente binomial:<br> <center> [[Image:coefBin.png]] </center>
#[[CC:RP:introducao|Introdução]]
 
#[[CC:RP:estrategias|Formato de competições e estratégias]]
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 números muito grandes: os fatoriais. Tome por exemplo o valor exato de 100!:
#[[CC:RP:linguagem|Recursos de linguagens de programação]]
 
#[[CC:RP:baixa|Problemas de baixa complexidade]]
100! =
##[[CC:RP:baixa:geometricos|Resolução de problemas geométricos]]
: 93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,<br>
##[[CC:RP:baixa:numericos|Resolução de problemas numéricos]]
: 468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,<br>
##[[CC:RP:baixa:diversos|Resolução de outros tipos de problemas]]
: 697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
#[[CC:RP:media|Problemas de complexidade média]]
 
##[[CC:RP:media:geometricos|Resolução de problemas geométricos]]
Um valor que certamente não caberá em um 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)?
##[[CC:RP:media:numericos|Resolução de problemas numéricos]]
 
##[[CC:RP:media:diversos|Resolução de outros tipos de problemas]]
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>
#[[CC:RP:alta|Problemas de complexidade alta]]
 
##[[CC:RP:alta:geometricos|Resolução de problemas geométricos]]
Abaixo segue uma possível implementação em C para o cálculo de combinações à partir do '''Triângulo de Pascal''':
##[[CC:RP:alta:numericos|Resolução de problemas numéricos]]
 
##[[CC:RP:alta:diversos|Resolução de outros tipos de problemas]]
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 são sempre preenchida com 1.
 
Em seguida, apenas imprimos na tela a combinação de N tomados K a K vezes.