Re: RES: [obm-l] Problema Subconjuntos

[Helder Suzuki <heldersuzuki@xxxxxxxxxxxx>]

Eh, eu fiz uma confusao ali

<quote>
imagine que temos os subconjnutos de {1, 2, ..., n-3}
e 
queremos adicionar os elementos n-1 e n-2 a esses
subconjuntos ao mesmo tempo, nesse caso só nao
poderemos adicionar n-1 e n-2 aos subconjuntos que tem
o elemento n-3, 
<errado>
entao teremos T[n-3] - T[n-4] subconjuntos com os
elementos n-1 e n-2: 
X = T[n-3] - T[n-4]
</errado> 
</quote>

<correcao>
T[n-3] - T[n-4] eh o numero de subconjuntos que tem o
elemento n-3. podemos adicionar n-1 e n-2 a todos os
outros subconjuntos, entao podemos adicionar n-1 e n-2
a T[n-3] - (T[n-3] - T[n-4]) = T[n-4]
entao X = T[n-4]
e T[n] = 2*T[n-1] - T[n-4]
</correcao>

--- "David M. Cardoso" <david-obm@suati.com.br>
escreveu: > 
> Cara, muito obrigado..
> Sendo que ta dando trabalho pra eu entender algumas
> coisas,
> como "teremos T[n-3] - T[n-4] subconjuntos com os
> elementos n-1 e n-2"..
> hora eu penso que entendi, hora eu não entendo mais
> e fico tentando lembrar
> pq eu fico entendido antes, talvez seja o
> nervosismo, talvez seja apenas
> porque o raciocinio eh complicado demais pra mim..
> 
> Outra duvida que tenho é se é possível transformar a
> recorrência num
> "polinomiozinho" em função de n ou se uma resposta
> desse tipo já esta
> completa o suficiente..
> 
> []'s
> David
> 
> > -----Mensagem original-----
> > De: owner-obm-l@mat.puc-rio.br 
> > [mailto:owner-obm-l@mat.puc-rio.br] Em nome de
> Helder Suzuki
> > Enviada em: terça-feira, 20 de julho de 2004 19:30
> > Para: obm-l@mat.puc-rio.br
> > Assunto: Re: [obm-l] Problema Subconjuntos
> > 
> > vamos ver, seguindo a dica de usar recorrencia
> > 
> > se T[n] for igual ao numero de subconjuntos do
> conjunto {1, 
> > 2, ..., n} que nao contem 3 inteiros consecutivos.
> > temos que:
> > T[0] = 1
> > {}
> > 
> > T[1] = 2
> > {} e {1}
> > 
> > T[2] = 4
> > {}, {1},
> > {2} e {1, 2}
> > 
> > T[3] = 7
> > {}, {1}, {2}, {1, 2},
> > {3}, {1, 3}, {2, 3}
> > 
> > T[4] = 13
> > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4},
> {1, 4}, {2, 
> > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}
> > 
> > bom, suponha que sabemos o valor de T[n-1],
> T[n-2], ..., 
> > T[1]; como podemos achar T[n] em funcao de T[n-1]?
> humm...
> > considere todos subconjuntos de {1, 2, 3, 4, ...,
> n-1} que 
> > satisfazem a condicao do enunciado.
> > se adicionarmos um elemento n, em quais desses
> subconjuntos o 
> > n pode entrar e quais ele nao pode(para manter a
> condicao do 
> > enunciado)?
> > se n nao pode entrar em X subconjuntos, temos que
> T[n] = 
> > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o
> numero de 
> > subconjuntos que tem os elementos
> > n-1 e n-2.
> > 
> > imagine que temos os subconjnutos de {1, 2, ...,
> n-3} e 
> > queremos adicionar os elementos n-1 e n-2 a esses 
> > subconjuntos ao mesmo tempo, nesse caso só nao
> poderemos 
> > adicionar n-1 e n-2 aos subconjuntos que tem o
> elemento n-3, 
> > entao teremos T[n-3] - T[n-4] subconjuntos com os
> elementos n-1 e n-2:
> > X = T[n-3] - T[n-4]
> > 
> > entao nossa recorrencia fica:
> > T[n] = 2*T[n-1] - T[n-3] + T[n-4]
> > 
> > []'s,
> > Helder
> > 
> > --- "David M. Cardoso" <david-obm@suati.com.br>
> > escreveu: > 
> > > 
> > > Olá,
> > > 
> > > Alguem pode me ajudar? Não consegui resolver o
> seguinte problema:
> > > 
> > > "Quantos subconjuntos o conjunto {1,2,3,...,n}
> tais que não contêm 
> > > três inteiros consecutivos?"
> > > 
> > > A dica dada na questão é: "Encontre uma
> recorrência." 
> > Porém, qualquer 
> > > solução (sem/com recorrência) vai ajudar.
> > > 
> > > []'s
> > > David
> > 
> > 
> > 	
> > 	
> > 		
> >
>
_______________________________________________________
> > Yahoo! Mail agora com 100MB, anti-spam e antivírus
> grátis!
> > http://br.info.mail.yahoo.com/
> >
>
==============================================================
> > ===========
> > 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
> >
>
==============================================================
> > ===========
> > 
> 
> 
>
=========================================================================
> 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
>
=========================================================================
> bm-l.html
>
=========================================================================
>  


	
	
		
_______________________________________________________
Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis!
http://br.info.mail.yahoo.com/
=========================================================================
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
=========================================================================