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: <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> 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 =========================================================================
