Re: [obm-l] Problema Subconjuntos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Helder:

Eu achei uma recorrencia diferente:

Seja A um dos T(n) subconjuntos nas condicoes do enunciado.
Existem 3 casos a considerar:

Caso 1: 
n nao pertence a A ==>
existem T(n-1) tais subconjuntos

Caso 2: 
n pertence mas n-1 nao pertence a A ==>
existem T(n-2) tais subconjuntos

Caso 3: 
n e n-1 pertencem a A ==>
n-2 nao pode pertencer a A ==>
existem T(n-3) tais subconjuntos

Logo, T(n) = T(n-1) + T(n-2) + T(n-3).

Usando o fato de que T(0) = 1, T(1) = 2 e T(2) = 4, obtemos:
T(3) = 7
T(4) = 13
T(5) = 24
T(6) = 44
T(7) = 81
T(8) = 149
T(9) = 274
...

[]s,
Claudio.


on 20.07.04 19:29, Helder Suzuki at heldersuzuki@yahoo.com.br wrote:

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