Exercícios de Computação II (2)

Prévia do material em texto

1) Faça um comparativo explicando o comportamento entre as pesquisas linear (desordenada), pesquisa sequencial (ordenada) e a pesquisa binária. Para auxiliar sua descrição utilize como exemplos os vetores v1 e v2. (0,5)
A pesquisa sequencial é utilizada para expressar valor por valor de vetores, de modo crescente e proporcional, onde no melhor caso o elemento procurado é o primeiro, e no pior caso é o último. 
Em v1, o ponto de partida é o primeiro elemento (43), e sequencialmente o número ao lado (41) e assim por diante.
A mesma coisa acontece em v2. O ponto inicial é o 2, o próximo o 6 e assim sucessivamente.
A pesquisa linear desordenada é a mesma coisa da sequencial, mas com um porém. Os valores dos vetores estão desordenados como o próprio nome já diz. A busca é realizada de acordo com a crescente dos elementos.
A pesquisa binária é mais utilizada quando a lista de vetores é ordenada. Ao iniciar, se o elemento chave for maior que o elemento do meio, a primeira metade dos vetores é descartada, assim como acontece se o elemento chave estiver antes do meio, da primeira metade para a segunda metade válida dos elementos. Assim acelerando o processo. 
Em v1, a busca é iniciada no elemento do meio (23), depois para o 67 ou 21, pois são os meios das segundas metades.
2) Responda as questões abaixo descrevendo exatamente o processo necessário para chegar ao resultado que você apresentou. O valor “X” corresponde ao “Num” na lista de acadêmicos (arquivo de apoio): (0,8) 
a) Sendo aplicado a pesquisa linear em v1, v2 e v3 quantas comparações será necessário para encontrar o valor X?
Serão necessárias 14 comparações para v1, v2 e v3
b) Sendo aplicado a pesquisa linear ordenada em v1, v2 e v3 quantas comparações será necessário para encontrar o valor X?
Não é possível fazer a pesquisa em v1, pois os elementos estão desordenados
Serão necessárias 14 comparações em v2
Serão necessárias 14 comparações em v3
c) Sendo aplicado a pesquisa binária ordenada em v1, v2 e v3 quantas comparações será necessário para encontrar o valor X?
Não é possível fazer a pesquisa em v1, pois os elementos estao desordenados
Serão necessárias 14 comparações em v2 e no v3, a partir do ponto médio dos vetores. A análise da primeira metade dos vetores, caso o elemento chave esteja nessa metade a pesquisa continua a partir da metade dessa segunda fragmentação, caso não esteja ela é descartada e a pesquisa parte da metade da outra fragmentação dos vetores.
d) Sendo aplicado as três pesquisas para encontrar o valor 97 no v2, quantas comparações serão realizadas até que ele informe que o valor não se encontra no vetor?
Pesquisa linear: 13 comparações, ponto inicial no 2.
Pesquisa linear desordenada: não é possível, pois os vetores estão ordenados.	
Pesquisa binária: 3 comparações, ponto inicial no 34.
3) Indique e demonstre o que deverá ser alterado no código em C, de cada função, para que possa ser aplicado a busca linear (desordenada), busca linear ordenada e a busca binária utilizando o v3. Explique e indique qual(is) a(s) linha(s) deve(m) ser alterada(s) no código e o porquê ocorre esta alteração. (0,9)
Na pesquisa linear ordenada deve-se alterar todo o código para que possa ler os vetores de forma desordenada como está em v3
Na pesquisa binária a linha 31 a chave é virada para o outro lado: “<”
4) Um supermercado tem um cadastro com Y itens que são comercializados no estabelecimento. (0,4) 
a) Se o cadastro estivesse ordenado, considerando a complexidade de algoritmos qual o máximo de comparações seria realizada para que ele encontre um produto qualquer? Explique como você chegou neste resultado.
Tomando como exemplo o elemento 15 da lista de acadêmicos como produtos.
 Se estivesse organizado de forma ordenada seria necessária 18 comparações no máximo para achar este elemento.
b) Se o cadastro não estivesse ordenado, considerando a complexidade de algoritmos qual o máximo de comparações seria realizada para que ele encontre um produto qualquer? Explique como você chegou neste resultado
Se os vetores estivessem organizados de acordo como está a lista de acadêmicos seria necessárias 15 comparações até achar o elemento procurado.
5) Critique a seguinte a seguinte versão da Pesquisa linear desordenada: (0,4)
O elemento i deve ser = 0
 Return -1;