On 12/02/03 19:17:46, niski wrote:
Em uma aula de computação me deparei com o seguinte problema :
"Suponha que os inteiros 1, 2, 3 e 4 são lidos nesta ordem. Considerando todas as possíveis seqüências de operações de empilhar e desempilhar, decida quais da 4! (=24) permutações de 1,2,3,4 podem ser obtidas na saída de uma pilha. Por exemplo, a permutação 2,3,1,4 pode ser obtida da seguinte forma: empilha 1, empilha 2, desempilha 2, empilha 3, desempilha 3, desempilha 1, empilha 4, desempilha 4. "
Fiz na força bruta. Me parece que são 10 permutacoes possiveis.
Pergunto mais genericamente agora...se eu tivesse os inteiros 1,2...n lidos nesta ordem, QUANTAS das n! permutacoes de 1,2,3...n podem ser obtidas na saida de uma pilha ?
[...]
Uma resposta final está definida unicamente por uma seqüência de 2n caracteres, n E e n D, que equivalem às operações Empilhar e Desempilhar. É obvio, a pilha secundária nunca pode ser desempilhada quando está vazia, logo temos que remover estas possibilidades.
Represente graficamente o processo -- em um instante qualquer, após i operações, plote o ponto (i, e-d), onde e é o número de Es que já foram executados e d o número de Ds. Termine conectando pontos adjacentes. Queremos saber o número de gráficos que tem todas as coordenadas y positivas, i.e. que não tocam a reta (x, -1).
Este problema é um problema clássico de combinatória, e sua resposta vale 1/n C(2n;n-1). Vale a pena tentar demosntrar isso sozinho.
Você tem certeza de que são só 10?
1. EDEDEDED 2. EDEDEEDD 3. EDEEDEDD 4. EDEEDDED 5. EDEEEDDD 6. EEDEDEDD 7. EEDEDDED 8. EEDEEDDD 9. EEDDEDED 10. EEDDEEDD 11. EEEDEDDD 12. EEEDDEDD 13. EEEDDDED 14. EEEEDDDD
Eu conto 14, que é justamente o que a resposta prevê.
[]s,
-- Fábio "ctg \pi" Dias Moreira GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net)
pgp00000.pgp
Description: PGP signature
