"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).
========================================================================= 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 =========================================================================
