on 02.12.03 19:17, niski at [EMAIL PROTECTED] 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 ?
>
> * Defini��o de pilha :
> Uma pilha � uma estrutura de dados que admite remo��o de elementos e
> inser��o de novos elementos. Mais especificamente, uma pilha (= stack)
> � uma estrutura sujeita � seguinte regra de opera��o: sempre que
> houver uma remo��o, o elemento removido � o que est� na estrutura h�
> menos tempo.
>
> Em outras palavras, o primeiro objeto a ser inserido na pilha � o �ltimo
> a ser removido. Essa pol�tica � conhecida pela sigla LIFO (=
> Last-In-First-Out).
>
Oi, Niski:
Soh pra clarificar: dada uma permutacao fixa "p" de {1,2,...,n}, digamos:
1 -> p(1), 2 -> p(2), ..., n -> p(n),
voce tem que empilhar 1, 2, ..., n nessa ordem e desempilhar estes numeros
na ordem p(1), p(2), ..., p(n).
O problema eh determinar todas as p (ou pelo menos quantas delas) para as
quais isso eh possivel.
De bate pronto, eu diria que uma condicao necessaria pra p ser realizavel
eh: p(k) - p(k+1) <= 1, para k = 1, 2, ..., n-1.
Por exemplo, se p(1) = 3 e p(2) = 1, a sequencia serah (E(x) = empilha x;
D(x) = desempilha x):
E(1), E(2), E(3), D(3) e travamos, pois antes de D(1) seremos obrigados a
D(2).
Serah que essa condicao tambem eh suficiente?
Um abraco,
Claudio.
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
