Re: [obm-l] Problema Subconjuntos

[Helder Suzuki <heldersuzuki@xxxxxxxxxxxx>]

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