Projete um algoritmo em pseudocódigo que, dado um dado string com texto, conte a frequência de letras sem…

Questão

Projete um algoritmo em pseudocódigo que, dado um dado string com texto, conte a frequência de letras sem distinguir maiúsculas/minúsculas e retorne as três letras mais frequentes em ordem decrescente. Descreva também as variáveis e a complexidade temporal.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: entrada s:string s <- lower(s) contagens <- dicionário vazio (char -> inteiro) para c em s: se c é letra: contagens[c] <- contagens.get(c,0)+1 lista <- ordenar pares(contagens) por valor decrescente retornar primeiros 3 chaves(lista) Variáveis: s (string de entrada), contagens (map de char->int), lista (array de pares). Complexidade: percorrer s é O(n); ordenar m pares custa O(m log m), onde m = 26; portanto custo prático O(n) para alfabeto fixo. Espaço O(m).

Explicação

O pseudocódigo apresentado utiliza uma abordagem eficiente para contar a frequência das letras, convertendo a string para minúsculas e utilizando um dicionário para armazenar as contagens, o que permite acesso rápido e atualização das frequências. A ordenação dos pares de frequência garante que as três letras mais frequentes sejam retornadas em ordem decrescente. A análise de complexidade temporal demonstra que o algoritmo é eficiente, especialmente considerando o alfabeto fixo, resultando em um desempenho prático de O(n).

Raio-X da questão

Questões parecidas com resolução

• Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
• Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
• Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
• Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
• — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
• — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…

Todas as questões de Programação - Algoritmos clássicos