Flashcard FC303162
Como contar sequências com dois símbolos em que uma sequência de comprimento k aparece pela primeira vez como sufixo, sem que a sequência contrária ocorra antes?
Sequências de Números, Figuras, Letras e Palavras
FGV · 2023
Como contar sequências com dois símbolos em que uma sequência de comprimento k aparece pela primeira vez como sufixo, sem que a sequência contrária ocorra antes?
Mostrar resposta e comentário
Resposta
Gerando todas as sequências cujo sufixo final é o padrão alvo e garantindo que o prefixo não contenha nem esse padrão nem o oposto; soma‑se por comprimento.Explicação:
Para um padrão de comprimento k e máximo de comprimentos até N:
1) Para cada n de k a N, conte sequências de comprimento n cujo sufixo final (últimos k símbolos) é o padrão alvo.
2) Exija que nenhum bloco de tamanho k comece antes do sufixo final igual ao padrão alvo ou ao padrão oposto — isto restringe os prefixos válidos.
3) Some as quantidades obtidas para cada n.
Esse procedimento pode ser feito por enumeração direta para k pequeno ou usando um autômato/recorrência para k maior.
exemplo:
Alfabeto {X,Y}, alvo = XX (k=2), máximo de 4 símbolos.
n=2: apenas XX → 1 sequência.
n=3: formas a b X com últimos 2 = XX; evitar ocorrência em posições 1–2 → só YXX → 1 sequência.
n=4: formas a b X X; para evitar blocos anteriores deve ser X Y X X → 1 sequência.
Total: \(1+1+1=3\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300252
Conteúdo do catálogo FC Concursos · Atualizado em