Se nao me engano isto e um numero de Catalan.Tente criar uma bije�aocom o problema dos trenzinhos que o Helder suzuki postou na lista. Qiue tal a gente colecionar na lista varios problemas de Catalan?
-- Mensagem original -- >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). > >========================================================================= >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 >========================================================================= > ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br ========================================================================= 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 =========================================================================
