Mudanças entre as edições de "Tópicos Adicionais I"
Linha 39: | Linha 39: | ||
Exercício 1: Implementar em sala a função acima usando a Linguagem C. Demonstrar o resultado para pelo menos 4 vetores de tamanhos diferentes. Inicie estes vetores com valores para evitar entrada de dados com scanf. | Exercício 1: Implementar em sala a função acima usando a Linguagem C. Demonstrar o resultado para pelo menos 4 vetores de tamanhos diferentes. Inicie estes vetores com valores para evitar entrada de dados com scanf. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Busca Linear Simples em vetor - Versão mais eficiente mas com elementos "destruturantes"= | =Busca Linear Simples em vetor - Versão mais eficiente mas com elementos "destruturantes"= |
Edição das 14h41min de 12 de abril de 2022
ReferÊncias
CORMEN, Thomas. Desmistificando Algoritmos. [Digite o Local da Editora]: Grupo GEN, 2013. 9788595153929. Disponível em: https://app.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em: 12 abr. 2022.
Objetivos
Após esta aula o aluno deverá ser capaz de:
- Explicar o funcionamento de um algoritmo de busca linear em vetor
- Aplicar a busca em problemas práticos.
Busca Linear Simples em vetor - Modo Ineficiente
Trata-se de um algoritmo que busca um determinado item armazenado em um vetor. O algoritmo realiza uma busca desde o início do vetor até o final, comparando item por item.
Suponha um vetor que armazena somente números inteiros POSITIVOS (incluindo 0). Uma busca linear neste
FUNCAO busca_linear
DADOS DE ENTRADA:
V: Vetor de itens /* para manter conformidade com o C, assumimos que a indexação começa em 0 */
inteiro n: tamanho do vetor
inteiro x: valor a ser procurado
DADOS DE SAÍDA
inteiro indice: índice do item encontrado (-1 se não encontrado)
VARIÁVEIS
inteiro i,
indice;
INÍCIO
indice=-1;
PARA cada i variando de 0 a N-1 FAZ
SE V[i] == X ENTÃO
indice = i;
retorna indice
FIM
Discussão: por que esta solução é ineficiente?
Exercício 1: Implementar em sala a função acima usando a Linguagem C. Demonstrar o resultado para pelo menos 4 vetores de tamanhos diferentes. Inicie estes vetores com valores para evitar entrada de dados com scanf.
Busca Linear Simples em vetor - Versão mais eficiente mas com elementos "destruturantes"
O algoritmo acima pode ser melhorado com um retorno ou interrupção assim que o item for encontrado. Em C pode-se também interromper o laço com o comando break.
Exercício 2: Modificar o exercício anterior usando um return dentro do laço
Exercício 3: Modificar o exercício anterior usando um break para interromper o laço.