Lista sobre Pesquisa

Prévia do material em texto

Exercícios – Pesquisa 
 
------------------------------------ PARTE 1 -------------------------------------------------------------- 
 
1) Considere o vetor de 11 elementos abaixo e marque quantas comparações de igualdade serão 
necessárias para a pesquisa sequencial/linear, pesquisa ordenada e para pesquisa binária na tentativa 
de se encontrar os valores: 2, 25 e 70. Demonstre como você chegou a este resultado. 
 
 
N° de comparações para encontrar o 2: 
Sequencial: 2; Ordenada: 2; Binária: 4; 
N° de comparações para encontrar o 25: 
Sequencial: 12; Ordenada: 12; Binária: 5; 
Como o número não está presente no vetor a pesquisa irá retornar todas as comparações +1, sendo 
assim uma pesquisa sem sucesso. 
N° de comparações para encontrar o 70: 
Sequencial: 9; Ordenada: 9; Binária: 2; 
 
2) Acesse o link https://pt.khanacademy.org/computing/computer-science/algorithms/binary-
search/e/running-time-of-binary-search e faça os exercícios propostos. Observe as dicas para 
resolução dos exercícios. 
 Feito. 
 
3) Uma loja de peças tem hoje 45000 peças em seu cadastro. Responda as questões abaixo, 
procurando demonstrar como você chegou aos resultados. 
 
a) Se as peças estiverem ordenadas qual seria a melhor pesquisa a ser aplicada? Justifique sua 
resposta. 
 A pesquisa binária, pois seriam realizadas menos comparações para encontrar determinado 
valor. No pior caso, seriam realizadas 16 comparações. 
b) Considerando aplicar a busca binária nesta lista ordenada, quantos itens seriam examinados para 
encontrar a localização de uma peça no pior caso? 
16 Comparações. 
 
 
https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/e/running-time-of-binary-search
https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/e/running-time-of-binary-search
c) Considerando aplicar a busca binária nesta lista ordenada, quantos itens seriam examinados para 
encontrar a localização de uma peça no melhor caso? 
1 comparação, o melhor caso seria se o elemento procurado estivesse no meio do vetor. 
d) Considerando aplicar a busca sequencial desordenada, quantos itens na lista, seria examinado 
para encontrar a localização de uma peça? 
As comparações para este caso, será o número do índice que a peça se localiza mais 1. Por 
exemplo, se a peça está no índice 9, seriam necessárias 10 comparações para localizar a peça. 
e) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seriam 
examinados para encontrar a localização de uma peça no melhor caso? 
 Para o melhor caso seria realizada apenas uma comparação. 
f) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seriam examinados 
para encontrar a localização de uma peça no pior caso? 
 No pior caso, seriam realizadas 45000 comparações. 
g) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seriam 
examinados para encontrar a localização de uma peça no caso médio? 
 Seriam realizadas 22501 comparações. 
 
4) Max criou uma lista composta por cada um dos DDDs dos telefones encontrados no site da 
agência. Por exemplo, o conteúdo da lista seria [11,19,12,13,19,...]. A partir disso, Max gostaria de 
fazer uma função que recebe uma lista de inteiros (contendo um determinado telefone) e uma chave 
de busca com um inteiro. A função deve implementar o algoritmo de Busca Sequencial, 
retornando−1 se a chave não existir na lista, e X caso ela exista, onde X é a posição (índice) da 
ocorrência do primeiro elemento da chave na lista. 
 
Como exemplo de chamada da função busca_sequencial, considere o seguinte programa: 
 
lista = [11, 19, 12, 13, 19, 43, 32, 41, 11, 12, 24] 
chave = 12 
pos = busca_sequencial (lista, chave) 
if (pos == -1): 
 print ("Não existe") 
else: 
 print ("Chave localizada na posição = ", pos) 
 
Max faltou à aula em que foi ensinado o algoritmo de Busca Sequencial. Então ele ligou para seu 
amigo Joff que sugeriu que ele implementasse uma função com o algoritmo de Busca Binária — 
segundo ele mais eficiente que a busca sequencial. Você considera que é possível implementar a 
Busca Binária na situação descrita no programa dado? 
 
Ou seja, a 3a linha do programa dado seria substituída por: 
X 
 
pos = busca_binaria (lista, chave) 
 
Responda SIM ou NÃO e justifique sua escolha. 
 Não, não seria possível porque os dados do vetor estão desordenados. 
 
------------------------------------ PARTE 2 -------------------------------------------------------------- 
 
Implementação 
 
 
 O usuário deverá escolher um tipo de pesquisa (Menu) 
 
1- Pesquisa sequencial 
2- Pesquisa ordenada 
3- Pesquisa binária 
4- Sair 
 
e também informar um número que será pesquisado. 
 
Quando o usuário escolher a opção deverá ser executado a função do tipo da pesquisa selecionado. 
Utilize um vetor de inteiros com 16 elementos (utilize a dica abaixo). Mas lembre-se que para 
sequencial o vetor não está ordenado e na binária considere ele ordenado. O usuário deverá 
informar um número (chave) que será então realizado a pesquisa. 
Informe ao final se encontrou (qual a posição) ou não o elemento procurado bem como a quantidade 
de comparações que o método precisou fazer. 
Caso a opção escolhida seja diferente do Menu acima informar que está incorreta a opção. O 
usuário poderá executar várias vezes. 
 
Dica : defina os vetores (desordenado e ordenado) para os testes para que não seja necessário 
o usuário entrar com os valores . 
 
int v[]={14,21,5,45,12,3,86,98,46,53,24,2,1,15,90,47}; 
int v_ord[]={1,2,3,5,12,14,15,21,24,45,46,47,53,86,90,98}; 
 
#include <stdio.h> 
#include <stdlib.h> 
#define TAM 16 
int cont = 0; 
int main() 
{ 
 int num, op; 
 int v[TAM] = {14,21,5,45,12,3,86,98,46,53,24,2,1,15,90,47}; 
 int v_ord[TAM] = {1,2,3,5,12,14,15,21,24,45,46,47,53,86,90,98}; 
 printf("Digite um numero inteiro (entre 1 e 100): "); 
 scanf("%d", &num); 
 do 
 { 
 printf("\n MENU:\n"); 
 printf("\n 1 - Pesquisa Sequencial"); 
 printf("\n 2 - Pesquisa Ordenada"); 
 printf("\n 3 - Pesquisa Binaria"); 
 printf("\n 4 - Sair"); 
 scanf("%d", &op); 
 cont = 0; 
 switch(op) 
 { 
 case 1 : 
 Pesquisa_Linear(v, num); 
 printf("\n Foram realizadas %d comparacoes.\n", cont + 1); 
 system("pause"); 
 system("cls"); 
 break; 
 case 2 : 
 Pesquisa_Ordenada(v_ord, num); 
 printf("\n Foram realizadas %d comparacoes.\n", cont + 1); 
 system("pause"); 
 system("cls"); 
 break; 
 case 3 : 
 Pesquisa_Binaria(v_ord, num); 
 printf("\n Foram realizadas %d comparacoes. \n", cont + 1); 
 system("pause"); 
 system("cls"); 
 break; 
 case 4 : 
 break; 
 default : 
 printf("\n Opcao invalida"); 
 } 
 } 
 while(op != 4); 
 return 0; 
} 
int Pesquisa_Linear(int *v, int num1) 
{ 
 int cont1; 
 for(cont1 = 0 ; cont1 <= TAM ; cont1++) 
 { 
 if(num1 == v[cont1]) 
 { 
 return printf("\nPosicao do numero: %d\n", cont1 + 1);; 
 } 
 else if((cont1 == TAM) && (num1 != v[cont1])) 
 { 
 return printf("\nNumero nao encontrado.\n");; 
 } 
 cont = cont + 1; 
 } 
} 
int Pesquisa_Ordenada(int *v_ord, int num2) 
{ 
 int cont2; 
 for(cont2 = 0 ; cont2 <= TAM ; cont2++) 
 { 
 if(num2 == v_ord[cont2]) 
 { 
 return printf("\n Posicao do numero: %d\n", cont2 + 1);; 
 } 
 else if((cont2 == TAM) && (num2 != v_ord[cont2])) 
 { 
 return printf("\nNumero nao encontrado.\n");; 
 } 
 cont = cont + 1; 
 } 
} 
int Pesquisa_Binaria(int *v_ord, int num3){ 
 int inicio, meio, fim; 
 inicio = 0; 
 fim = TAM - 1; 
 while(inicio <= fim) 
 { 
 meio = (inicio + fim)/2; 
 if(num3 == v_ord[8]) 
 { 
 return printf("\n Posicao do numero: %d\n", meio+1);; 
 } 
 else if(num3 < v_ord[meio]) 
 fim = meio - 1; 
 else if(num3 > v_ord[meio]) 
 inicio = meio + 1; 
 else 
 return printf("\n Posicao do numero: %d\n", meio+1);; 
 cont = cont + 1; 
 } 
 return printf("\n Numero nao encontrado.\n"); 
}