RES: problema

["M. A. A. Cohen" <mcohen@xxxxxxxxxx>]

Como vc nao disse nada sobre qtos tipos de cada operador vc tem vou supor
que os operadores e os operandos estao fixos, e seu objetivo eh descobrir de
qtos maneiras pode colocar parenteses pra realizar essa operacao (se vc
quiser mudar as ordens dos operadores ou inserir diferentes tipo de
operando, o problema nao muda mto. o dificil acho que serah exatamente esse
problema final).
Esse, se nao me engano, eh um problema famoso. A resposta eh o q se costuma
chamar de n-o numero de Catalan (vale
[Binomial(2n,n)]/(n+1).
Uma maneira de se provar isso eh considerar a funcao geratriz F cujo
coeficiente de x^n eh a resposta do problema para cada n. Ai vc nota que
sempre existe exatamente UM operando fora de todos os parenteses (que serve
para ligar duas contas grandes). entao, C_n = C_0 * C_n-1 + C_1 * C_n-2 +
... + C_n-1 * C0  (q notacao horrivel!).
Enfim, vc pediu uma dica neh :)
Vc consegue achar uma equacao do segundo grau em F(x) e resolvendo e usando
binomio de Newton vc encontra finalmente que o coeficiente de x_n eh sempre
aquele numero la de cima.
Tem um jeito de resolver esse problema sem usar funcoes geratrizes. Eu li
uma vez no livro "Matematica Concreta", mas nao lembro agora como se faz...
Abracos,
Marcio

-----Mensagem original-----
De: owner-obm-l@sucuri.mat.puc-rio.br
[mailto:owner-obm-l@sucuri.mat.puc-rio.br]Em nome de Carlos Maçaranduba
Enviada em: quarta-feira, 14 de novembro de 2001 17:44
Para: obm-l@mat.puc-rio.br
Assunto: problema


Quem não conseguir fazer pelo menos diga uma
idéia.Esta forma é a chamada forma infixa(forma no
qual nós escrevemos) , mas existem as formas prefixa e
posfixa(esta última usada em expressoes algébricas em
compiladores pois se trata de uma forma mais eficiente
de interpretar uma expressão algébrica).Depois digo
como é a forma posfixa.Mas por favor tentem resolver
essa questào para mim.


Seja uma sequencia de operandos e operadores mostrados
como abaixo:

A+B.C;

Separando por parenteses poderiamos obter duas
expressões algébricas: (A+B).C ou A+(B.C);
Repare que temos três operandos e dois
operadores(multiplicação e soma).Dada uma sequencia de
n operandos e n-1 operadores ,de quantas formas
diferentes se pode formar expressões algébricas
separadas por parenteses???

obs:Obviamente que a sequencia começa por um operando
e termina com outro operando.

____________________________________________________________________________
___________________
Yahoo! GeoCities
Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo!
GeoCities. É fácil e grátis!
http://br.geocities.yahoo.com/