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