Leia N valores. Apresente ao final a frequência de cada valor informado.
Passo 1
O enunciado pede o seguinte, de forma simples: leia
valores e, ao final, apresente a frequência de cada valor informado.
Informações relevantes que o enunciado fornece (ou que devemos considerar para resolver):
Informações relevantes que o enunciado fornece (ou que devemos considerar para resolver):
- Existe um inteiro
que indica quantos valores serão lidos. - Em seguida serão fornecidos
valores (podem ser inteiros, strings, reais — o enunciado não especificou). - A saída deve mostrar, para cada valor distinto lido, quantas vezes ele apareceu (a frequência).
Não estamos resolvendo um caso numérico específico: o objetivo é definir um procedimento (algoritmo) que, dado qualquer entrada com
valores, produza as frequências corretas.
Passo 2
Escolha do método: vou usar um dicionário (também chamado de mapa, tabela de símbolos ou hash map). Por quê? Porque é a forma mais prática e eficiente para contar ocorrências:
- Enquanto lemos cada valor, podemos atualizar sua contagem em tempo médio constante.
- O algoritmo fica simples, direto e funciona tanto para números quanto para palavras.
Alternativa: ordenar os dados e depois contar repetições consecutivas. Isso também funciona, mas envolve custo de ordenação () e é mais trabalhoso se você só precisa das frequências. Portanto escolhemos o dicionário (mapa).
Passo 3
Conceito que precisamos entender: o que é um dicionário/mapa e quais operações usamos.
- Um dicionário associa chaves a valores. Aqui a chave será o valor lido (por exemplo,
) e o valor associado será a contagem (um inteiro). - Operações essenciais:
- verificar se uma chave
já existe no dicionário (lookup); - inserir uma nova chave com contagem inicial
; - atualizar a contagem existente, somando
.
- verificar se uma chave
- Complexidade típica: cada operação é em média
(constante) se o mapa for implementado por hash table. Logo o algoritmo todo fica em média para leitura e contagem, mais para percorrer as chaves distintas na saída.
Passo 4
Passo a passo do algoritmo em palavras (o que você deve fazer na prova):
- Leia
. - Crie um dicionário vazio chamado, por exemplo,
contagem. - Para cada
de até :
a) Leia o valor.
b) Sejá está em contagem, façacontagem[x] = contagem[x] + 1.
c) Caso contrário, façacontagem[x] = 1. - Depois de ler todos os
valores, percorra todas as chaves em contageme imprimae contagem[k](ou apenas a frequência, conforme pedido).
Dica prática: na prova, escreva a operação de teste/incremento de forma clara; por exemplo: "se
então
senão
".
Passo 5
Casos especiais e decisões de formato de saída (coisas que costumam estar ambíguas em enunciados e que você precisa decidir ou perguntar ao professor, mas aqui eu explico as opções):
- Ordem da saída:
- ordem de primeira ocorrência (preservar a ordem em que valores distintos apareceram): use um dicionário que preserve inserção (ou mantenha uma lista com a ordem das chaves).
- ordem crescente dos valores: após contar, ordene as chaves e depois mostre (custo adicional
). - ordem por frequência (maior para menor): ordene as tuplas
pelo segundo elemento.
Escolha a que a prova pedir; se não pedir, explique qual você usou.
- Valores heterogêneos (números e strings): trate-os como chaves comparáveis ou como strings normalizadas.
-
: simplesmente não imprime nada (ou imprime mensagem “nenhum valor”) — concorde com o formato esperado.
Passo 6
Exemplo prático (mão na massa, para você entender como o dicionário muda ao longo da leitura).
Suponha e que os valores lidos sejam, nesta ordem:
.
Vamos simular a variável
Suponha
Vamos simular a variável
contagem:- ler
: contagem = {1: 1} - ler
: contagem = {1: 1, 2: 1} - ler
: contagem = {1: 1, 2: 2} - ler
: contagem = {1: 1, 2: 2, 3: 1} - ler
: contagem = {1: 2, 2: 2, 3: 1} - ler
: contagem = {1: 2, 2: 3, 3: 1} - ler
: contagem = {1: 2, 2: 3, 3: 1, 4: 1} - ler
: contagem = {1: 2, 2: 4, 3: 1, 4: 1} - ler
: contagem = {1: 2, 2: 4, 3: 2, 4: 1} - ler
: contagem = {1: 3, 2: 4, 3: 2, 4: 1}
Saída (uma forma razoável) seria listar cada valor e sua frequência:
Passo 7
Complexidade e por que dá para fazer na prova sem calculadora:
- Cada leitura e atualização é
em média; com leituras o total é . - Percorrer as
chaves distintas para imprimir é . - Memória usada é proporcional a
(nº de valores distintos).
Isso é simples de explicar e suficiente para justificar a escolha do método em uma prova.
Passo 8
Pseudocódigo compacto que você pode escrever na prova (use este formato se pedirem algoritmo). Aqui uso
e
como variáveis matemáticas, conforme combinado:
ler
inicializar dicionário vazio
para de
até
faça
\quad ler
\quad se então
\quad\quad
\quad senão
\quad\quad
para cada chave em
faça
\quad imprimir ,
inicializar
para
\quad ler
\quad se
\quad\quad
\quad senão
\quad\quad
para cada chave
\quad imprimir
Resposta
ler
inicializar dicionário vazio
para de
até
faça
\quad ler
\quad se então
senão
para cada chave em
faça imprimir
,
inicializar
para
\quad ler
\quad se
para cada chave