Busca Linear
Desenvolva um programa no qual seja definido um vetor de números com quaisquer valores (pode haver valores repetidos ou não). O usuário deve ser questionado para digitar um número e em seguida o programa indica a quantidade de vezes (ou nenhuma vez) este número aparece no vetor.
Desenvolva um programa no qual seja definido um vetor de números com quaisquer valores (pode haver valores repetidos ou não). O usuário deve ser questionado para digitar um número e em seguida o programa indica a quantidade de vezes (ou nenhuma vez) este número aparece no vetor.
Passo 1
O que o enunciado pede e o que temos de dado.
- Pedido: escrever um programa que, dado um vetor de números e um número fornecido pelo usuário, indique quantas vezes esse número aparece no vetor (pode ser zero).
- Dados que o programa precisa ter ou receber: um vetor de números — vou chamar esse vetor de
— e um número digitado pelo usuário — vou chamar esse número de . - Saída esperada: um único número (ou mensagem) indicando a quantidade de ocorrências de
em .
Observação: o enunciado permite que o vetor tenha valores repetidos ou não; o programa deve contar todas as repetições.
Passo 2
Ideia geral da solução (explicada devagar, como num colega te ensinando).
- Vamos percorrer o vetor
elemento por elemento, comparando cada elemento com o valor alvo . Essa técnica chama-se busca linear. - Mantemos um contador
que começa em . Cada vez que encontrarmos um elemento igual a , aumentamos em . No fim do percurso, é a quantidade de vezes que aparece em . - Por que isso funciona? Porque ao checar todos os elementos uma vez, garantimos que nenhuma ocorrência seja perdida. É simples e direto — perfeito para a prova se não pedirem otimizações pontuais.
Passo 3
Descrição passo a passo do algoritmo (pseudocódigo com explicação linha-a-linha).
- Inicializar o contador: definir
. Aqui guarda quantas ocorrências já contamos. - Para cada índice
que percorre do primeiro ao último elemento de : faça:
a. compararcom ;
b. se, então incrementar . - Depois de verificar todos os elementos, imprimir o valor de
(ou uma frase do tipo “o número aparece vezes”).
Explicação das variáveis usadas:é o vetor (lista) de números; é o número buscado; é o contador de ocorrências; é o índice que varre o vetor. Nada de pulo de etapas — compara e incrementa.
Passo 4
Exemplo concreto (muito detalhado) para ver o processo na prática.
- Suponha o vetor
(escolhi esses números para ilustrar). - Queremos contar quantas vezes
aparece. Inicialmente . - Percurso:
-
. Comparo com . . Não mudo (continua ). -
. . Faço , então . -
. . continua . -
. Igual, então . -
. Diferente, . -
. Igual, . -
. Diferente, .
-
- Resultado: após percorrer todo
, temos . Logo o número aparece vezes no vetor.
Esse tipo de passo-a-passo é exatamente o que você pode escrever mentalmente na prova para justificar a contagem.
Passo 5
Casos especiais e detalhes práticos (para não ser pego de surpresa na prova ou no teste):
- Vetor vazio: se
tiver comprimento , o laço não executa e permanece — correto, o número aparece zero vezes. - Nenhuma ocorrência: se nenhum elemento for igual a
, fica . - Todas posições iguais: se todo elemento de
for igual a , então (onde é o tamanho de ). - Tipos de dados: se
contém inteiros e o usuário digita um número decimal, ou vice-versa, a comparação pode falhar por tipo. Na prática escolha se vai trabalhar com inteiros ou floats; no exemplo de código vou tratar como inteiros (pode adaptar). - Precisão de floats: se usar floats, cuidado com igualdade direta por causa de arredondamento; melhor usar tolerância se for esse o caso (ex.: comparar |a-b| < epsilon).
Passo 6
Complexidade e justificativa de escolha do método.
- Tempo: o algoritmo faz uma comparação por elemento, então o tempo é proporcional ao tamanho do vetor
. Chamamos isso de complexidade . - Espaço: usamos apenas um contador adicional, então espaço extra é
. - Por que não outro método? Como não há estrutura de dados prévia (por exemplo, um dicionário que já conte tudo, ou vetor ordenado para busca binária), a busca linear é a opção mais simples e garantida. Em prova, se pedirem implementar a busca manualmente, essa é a correta.
Passo 7
Como escrever isso em um programa real (orientações para implementar em qualquer linguagem).
- Crie/defina o vetor
com os números desejados (pode ser fixo no código ou lido de entrada). - Leia o número
do usuário. Converta para o tipo escolhido (ex.: inteiro). - Implemente o laço que percorre
e atualiza conforme o pseudocódigo do Passo 3. - Ao fim, mostre o resultado com uma mensagem clara.
Dica para prova: se tiver tempo e for permitido usar funções prontas, muitas linguagens têm algo comocount(ex.: em Pythonv.count(x)), mas saiba fazer o laço manualmente — isso é o que costumam cobrar.
Resposta
# Programa de busca linear que conta quantas vezes um número aparece em um vetor
# Vetor definido com quaisquer valores (pode haver repetições)
v = [2, 7, 5, 7, 3, 7, 9] # você pode trocar esses valores pelo que quiser
# Leitura do número a ser buscado (aqui trato como inteiro)
x = int(input("Digite o número a ser buscado: "))
# Inicializa contador
c = 0
# Percorre o vetor e conta ocorrências
for valor in v:
if valor == x:
c += 1
# Exibe resultado
if c == 0:
print(f"O número {x} não aparece no vetor.")
elif c == 1:
print(f"O número {x} aparece 1 vez no vetor.")
else:
print(f"O número {x} aparece {c} vezes no vetor.")