Re: [obm-l] Permutaçoes_com_pilhas.

[Guilherme Carlos Moreira e Silva <luis_e_rosa@xxxxxxxxxxxx>]

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