Leia N valores. Apresente ao final a frequência de cada valor informado.

Passo 1

O enunciado pede o seguinte, de forma simples: leia \,N\, 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):
  • Existe um inteiro \,N\, que indica quantos valores serão lidos.
  • Em seguida serão fornecidos \,N\, 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 \,N\, 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 ( O(N\log N)) 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, x) e o valor associado será a contagem (um inteiro).
  • Operações essenciais:
    • verificar se uma chave x já existe no dicionário (lookup);
    • inserir uma nova chave com contagem inicial \,1\,;
    • atualizar a contagem existente, somando \,1\,.
  • Complexidade típica: cada operação é em média O(1) (constante) se o mapa for implementado por hash table. Logo o algoritmo todo fica O(N) em média para leitura e contagem, mais O(M) para percorrer as M chaves distintas na saída.

Passo 4

Passo a passo do algoritmo em palavras (o que você deve fazer na prova):
  1. Leia \,N\,.
  2. Crie um dicionário vazio chamado, por exemplo, contagem.
  3. Para cada i de 1 até \,N\,:
    a) Leia o valor x.
    b) Se x já está em contagem, faça contagem[x] = contagem[x] + 1.
    c) Caso contrário, faça contagem[x] = 1.
  4. Depois de ler todos os \,N\, valores, percorra todas as chaves k em contagem e imprima k e 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 x \in \text{contagem} então \text{contagem}[x] \leftarrow \text{contagem}[x]+1 senão \text{contagem}[x]\leftarrow 1".

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 O(M\log M)).
    • ordem por frequência (maior para menor): ordene as tuplas (valor, frequência)ê 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.
  • \,N=0\,: 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 \,N=10\, e que os valores lidos sejam, nesta ordem: \,1,2,2,3,1,2,4,2,3,1\,.
Vamos simular a variável contagem:
  • ler 1: contagem = {1: 1}
  • ler 2: contagem = {1: 1, 2: 1}
  • ler 2: contagem = {1: 1, 2: 2}
  • ler 3: contagem = {1: 1, 2: 2, 3: 1}
  • ler 1: contagem = {1: 2, 2: 2, 3: 1}
  • ler 2: contagem = {1: 2, 2: 3, 3: 1}
  • ler 4: contagem = {1: 2, 2: 3, 3: 1, 4: 1}
  • ler 2: contagem = {1: 2, 2: 4, 3: 1, 4: 1}
  • ler 3: contagem = {1: 2, 2: 4, 3: 2, 4: 1}
  • ler 1: contagem = {1: 3, 2: 4, 3: 2, 4: 1}
Saída (uma forma razoável) seria listar cada valor e sua frequência:
  • \,1: 3\,
  • \,2: 4\,
  • \,3: 2\,
  • \,4: 1\,

Passo 7

Complexidade e por que dá para fazer na prova sem calculadora:
  • Cada leitura e atualização é O(1) em média; com \,N\, leituras o total é O(N).
  • Percorrer as M chaves distintas para imprimir é O(M).
  • Memória usada é proporcional a M (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 \,N\, e x como variáveis matemáticas, conforme combinado:
ler \,N
inicializar \text{contagem} \leftarrow dicionário vazio
para i de 1 até \,N faça
\quad ler x
\quad se x \in \text{contagem} então
\quad\quad \text{contagem}[x] \leftarrow \text{contagem}[x] + 1
\quad senão
\quad\quad \text{contagem}[x] \leftarrow 1
para cada chave k em \text{contagem} faça
\quad imprimir k, \text{contagem}[k]

Resposta

ler N
inicializar \text{contagem} \leftarrow dicionário vazio
para i de 1 até N faça
\quad ler x
\quad se x \in \text{contagem} então \text{contagem}[x] \leftarrow \text{contagem}[x] + 1 senão \text{contagem}[x] \leftarrow 1
para cada chave k em \text{contagem} faça imprimir k, \text{contagem}[k]

Exercícios relacionados