20011117190054.31007.qmail@web21107.mail.yahoo.com">
ok,mas poderia explicar -me como eu resolvo por
funções geratrizes???fui procurar mais sobre isso e
encontrei alguns problemas de contagem sendo
resolvidos por estas tecnicas como abaixo:
ache o números de soluções de x_1 + x_2 + x_3 = 17
tais que 2<= x_1 <=5 , 3 <= x_2 <= 6 e 4 <= x_3 <= 7 e
x_1 ,x_2 e x_3 são naturais.
Simplesmente ele faz:
(x^2 + x^3 + x^4 + x^5)(x^3+ x^4 + x^5 + x^6)(x^4 +
x^5 + x^6 + x^7) e acha o coeficiente de x^17 que é
igual a 3 , que é a resposta do problema...
QUE MÁGICA É ESSA????
E O PIOR DE TUDO QUE AINDA HÁ GENTE QUE PREFERE
BIOLOGIA........
--- "M. A. A. Cohen" <mcohen@iis.com.br> escreveu: >
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 re
solvendo 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 escrev
emos) , 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/
_______________________________________________________________________________________________
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/