[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Re: N/A
Oi João!
Na mensagem do Morgado, ele escreveu:
"Seja f(n) a resposta para uma sequencia de n bits. Ou a seq. começa em 1 ou
começa em 01.
Logo, f(n)=f(n-1)+f(n-2).
Como f(1) = 2 e f(2) = 3, f(3) = 2+3=5, f(4) = 5+3 = 8, f(5) = 8+5 = 13,
f(6)=13=8 = 21, f(7) = 21+13 = 44 e f(8) = 44+21 = 65."
Há um pequeno erro de contas. Onde diz 21 + 13 o resultado é 34 e não 44, aí
a resposta final são os mesmos 55 que você encontrou. Aproveitando a deixa,
do modo como eu havia feito (contando as seqüências com uma quantidade x de
zeros), eu esqueci de contar três seqüências com quatro zeros:
(01101010)
(01011010)
(01010110)
Eu havia contado apenas 52, com mais essas 3, fecho os 55.
Seu método, o do Morgado e o piorzinho dos três, o meu, estão corretos e
levam ao mesmo resultado.
Abração!
Duda.
From: "João Gilberto Ponciano Pereira" <jopereira@vesper.com.br>
> Pessoal
>
> Sem querer ser chato, mas cheguei ao resultado de 55. O processo é um
pouco
> "feio", mas chega lá.
>
> "De quantas maneiras podemos formar uma sequencia de oito bits(0 ou 1) de
> forma que nunca apareça nesta sequencia zeros adjacentes"
>
> Seja A(n) o número de combinações dentro das regras que terminam com o bit
> 1, e B(n) os que terminem com o bit 0.
>
> É fácil ver que:
> 1) A(n+1) = A(n) + B(n)
> 2) B(n+1) = A(n)
>
> Logo:
> A(n+1) + B(n+1) = 2*A(n) + B(n)
> e substituindo, temos:
> A(n+2) = 2*A(n) + A(n-1)
>
> Sabendo que:
> A(1) = 1 ==> (1)
> A(2) = 2 ==> (01, 11)
> A(3) = 3 ==> (011, 101, 111) obs: "001" não vale!
> podemos seguir com a recorrência até A(9) = A(8) + B(8) = 55
>
> Um abraço!
> JG
>
> -----Original Message-----
> From: Augusto Cesar de Oliveira Morgado [mailto:morgado@centroin.com.br]
> Sent: Monday, November 03, 2003 9:29 PM
> To: obm-l@mat.puc-rio.br
> Subject: Re: [obm-l] Re: N/A
>
>
> Recebi a mensagem que enviei com um rosto amarelo com cara de idiota
> sorrindo
> no lugar em que digitei o numero 8. Desculpas a todos.
> Morgado
>
>
> --
> CIP WebMAIL - Nova Geração - v. 2.1
> CentroIn Internet Provider http://www.centroin.com.br
> Tel: (21) 2542-4849, (21) 2295-3331 Fax: (21) 2295-2978
> Empresa 100% Brasileira - Desde 1992
>
>
> ---------- Original Message -----------
> From: "Augusto Cesar de Oliveira Morgado" <morgado@centroin.com.br>
> To: obm-l@mat.puc-rio.br
> Sent: Mon, 3 Nov 2003 20:59:29 -0200
> Subject: [obm-l] Re: N/A
>
> > Seja f(n) a resposta para uma sequencia de n bits. Ou a seq. começa
> > em 1 ou começa em 01. Logo, f(n)=f(n-1)+f(n-2). Como f(1) = 2 e f(2)
> > = 3, f(3) = 2+3=5, f(4) = 5+3 = 8, f(5) = 8+5 = 13, f(6)=13=8 = 21,
> > f(7) = 21+13 = 44 e f(8) = 44+21 = 65.
> >
> > --
> > CIP WebMAIL - Nova Geração - v. 2.1
> > CentroIn Internet Provider http://www.centroin.com.br
> > Tel: (21) 2542-4849, (21) 2295-3331 Fax: (21) 2295-2978
> > Empresa 100% Brasileira - Desde 1992
> >
> > ---------- Original Message -----------
> > From: "Daniel Faria" <faria_mat@hotmail.com>
> > To: obm-l@mat.puc-rio.br
> > Sent: Mon, 03 Nov 2003 19:16:55 -0200
> > Subject: N/A
> >
> > > Ainda nao consegui finalizar este exercício:
> > >
> > > De quantas maneiras podemos formar uma sequencia de oito bits(0 ou 1)
> > > de forma que nunca apareça nesta sequencia zeros adjacentes ( _ _
> > > 0 0 _ _ _ _ ).
> > >
> > > Obrigado.
> > >
> > > _________________________________________________________________
> > > MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.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
> > >
> =========================================================================
> > ------- End of Original Message -------
> >
> >
=========================================================================
> > 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
> >
=========================================================================
> ------- End of Original Message -------
>
> =========================================================================
> 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
> =========================================================================
>
>
=========================================================================
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
=========================================================================