Re: [obm-l] Re:your mail (sequencias de bits sem 00)

["Domingos Jr." <dopikas@xxxxxxxxxx>]

primeiramente verifique que h� 3 sequ�ncias de 2 bits sem 00,
defina f(k) := n�mero de seq��ncias de k bits sem 00 (k >= 1)
f(0) = 1, f(1) = 2, f(2) = 3

depois veja que se temos uma seq��ncia de n bits sem 00 ent�o
se o final dos bits � 01 ent�o devemos ter 101 como final e n-3 bits
precedentes sem 00, logo h� f(n-3) seq��ncias desse tipo.
se o final for 10 ou 11 o que vem antes deve ter qualquer seq��ncia de n-2
bits sem 00, logo h� f(n-2)*2 seq. desse tipo.

f(n) = f(n-3) + 2*f(n-2) para n >= 3.

tente resolver a recorr�ncia pra obter uma f�rmula geral...


----- Original Message ----- 
From: <peterdirichlet2002@zipmail.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, November 04, 2003 1:45 PM
Subject: [obm-l] Re:your mail (sequencias de bits sem 00)


Bem, neste tipo de coisa e util usar um grafo que te diga como produzir
boas sequencias.Imagine um multigrafo cujos vertices sao 0 e 1 e que uma
aresta liga dois numeros que podem ser consecutivos, como 01,10,11. Agora
usando recorrencias ou matrizes de adjacencia da pra determinar o numero
de caminhos de tamanho n.
-- Mensagem original --

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

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