Mudanças entre as edições de "Tópicos Adicionais I"
(4 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
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"= | ||
+ | |||
+ | 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. | ||
<syntaxhighlight lang=C> | <syntaxhighlight lang=C> | ||
Linha 90: | Linha 98: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | + | =Busca Linear com Sentinela= | |
+ | |||
+ | Esta versão da busca linear visa eliminar um dos dois testes realizados no "loop" da verão anterior. Note que a cada iteração existe um teste devido ao comando de repetição 'for' (teste de se i < n) e um teste de verificação de ocorrência do item (if (v[i] == x)). | ||
+ | |||
+ | Na vesão com sentinela o item é colocado no final do array, substituindo o último elemento do array. Obviamente, este elemento deve ser salvo. | ||
+ | |||
+ | <syntaxhighlight lang=C> | ||
+ | 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 AUXILIARES | ||
+ | inteiro i, | ||
+ | ultimo; | ||
+ | INÍCIO | ||
+ | ultimo = A[n-1] /* salva o último na variável auxiliar */ | ||
+ | i=0; | ||
+ | ENQUANTO A[i] != x FAÇA /* procura pelo elemento - observe que em algum momento ele será encontrado... */ | ||
+ | incremente i | ||
− | + | SE i<n-1 OU A[n-1]==ultimo | |
+ | retorna i | ||
+ | SENAO | ||
+ | retorna -1 /* não encontrado */ | ||
+ | |||
+ | FIM | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | EXERCÍCIO 4 | ||
− | + | Implementar em C uma função para realizar busca linear com sentinela. |
Edição atual tal como às 14h16min de 14 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.
#include <stdio.h>
int busca_linear_inef(int v[], int n, int x)
{
int i, indice;
indice = -1;
for(i=0;i<n;i++) {
if (v[i] == x)
indice = i;
}
return indice;
}
int busca_linear_efv1(int v[], int n, int x)
{
int i;
for(i=0;i<n;i++) {
if (v[i] == x)
return i;
}
return -1;
}
int busca_linear_efv2(int v[], int n, int x)
{
int i, indice;
indice = -1;
for(i=0;i<n;i++) {
if (v[i] == x) {
indice = i;
break;
}
}
return indice;
}
int main()
{
int alfa[5]={31,97,156,91,8};
int pos;
pos=busca_linear_efv2(alfa,5,156);
printf("O item 156 está na posicao %d\n", pos);
pos=busca_linear_efv2(alfa,5,230);
printf("O item 230 está na posicao %d\n", pos);
return 0;
}
Busca Linear com Sentinela
Esta versão da busca linear visa eliminar um dos dois testes realizados no "loop" da verão anterior. Note que a cada iteração existe um teste devido ao comando de repetição 'for' (teste de se i < n) e um teste de verificação de ocorrência do item (if (v[i] == x)).
Na vesão com sentinela o item é colocado no final do array, substituindo o último elemento do array. Obviamente, este elemento deve ser salvo.
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 AUXILIARES
inteiro i,
ultimo;
INÍCIO
ultimo = A[n-1] /* salva o último na variável auxiliar */
i=0;
ENQUANTO A[i] != x FAÇA /* procura pelo elemento - observe que em algum momento ele será encontrado... */
incremente i
SE i<n-1 OU A[n-1]==ultimo
retorna i
SENAO
retorna -1 /* não encontrado */
FIM
EXERCÍCIO 4
Implementar em C uma função para realizar busca linear com sentinela.