Re: [obm-l] Permuta�oes_com_pilhas.

[Guilherme Carlos Moreira e Silva]

>Eu estava dando o seguinte tratamento (p/ n = 4)
>Para gerar uma permutacao de 4 elementos, necessito de 8 >operacoes.
>E1 D1 E2 E3 D3 D2 E4 D4 -> gera 1 3 2 4

A id�ia � boa. Estava caminhando nesta dire��o, mas descobri que n�o sabia contar isto.

 

Pensei no seguinte:sejam & e % os operadores empilhar e desempilhar, respectivamente.

 

Minha pilha � construida da seguinte forma: sempre empilho um n�mero e depois escolho desempilh�-lo ou empilhar outro.

 

Desta forma, meu objetivo, agora, � contar de quantas formas posso orgnizar os operadores & e %.

 

Observe que:

1) devo come�ar com & e terminar com %;

2) temos iguais quantidades de & e %;

3) para uma dada posi��o da sequ�ncia, n�o pode ter aocorrido mais % do que &.

>Essa mesma sequencia pode ser gerada de outra forma?
>Qualquer outra sequencia pode ser gerada de outra forma?

� f�cil ver que n�o.

 

>>>Eu estava dando o seguinte tratamento (p/ n = 4)

>Para gerar uma permutacao de 4 elementos, necessito de 8 >operacoes.

>E1 D1 E2 E3 D3 D2 E4 D4 -> gera 1 3 2 4

Pensei mais . . . poder�amos pensar que & e % definem, respectivamente, um inicio e um fim para uma "sub-sequ�ncia" dos n�meros dados.

ponto 1) o operador % aparece para teminar a grava��o de uma sub-sequ�ncia e inicio de sua escrita quando antecedido por &;

ponto 2) o operador % aparece para t�rmino da escrita das sub-sequ�ncias que porventura tenham sido impedidas de ser escritas quando entecedidos por %.

 

Note no seu exemplo: &%( veja ponto 1)&&%%(veja ponto 2)&%

=========================================================================
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
=========================================================================

---

Yahoo! Mail - 6MB, anti-spam e antiv�rus gratuito. Crie sua conta agora!