ATPS etapa 2
Por: matheuslemos2003 • 6/4/2015 • Trabalho acadêmico • 1.242 Palavras (5 Páginas) • 289 Visualizações
Aula02- Exercicios
Escreva uma função, em português estruturado ou código em C, que realize uma pesquisa sequencial.
Usando uma Função que recebe três parâmetros:
um ponteiro para o vetor a ser pesquisado, o tamanho do vetor (tam) e o valor que se deseja pesquisar (chave).
Ela retorna a posição da chave no vetor, se for encontrada ou -1, caso contrário.
Exemplo:
int pesquisa(char *vetor, int tam, char chave)
{
register int i;
for(i=0; i
if(chave == vetor[i]) {
return i;
}else{
return -1 /* não encontrou */
}
}
int pesquisa (int valorBuscado, int vetor[x], int x){
int i;
for (i=0; i < x; i++){
if (valorBuscado == vetor [i]){
return i;
}
}
Return -1;
}
[pic 1]
Análise do exemplo:
No melhor caso, a chave será localizada já na primeira posição e no caso médio, tam/2 iterações serão feitas.
Na pior das hipóteses, a chave estará na última posição, o que levará o algoritmo a executar TAM iterações.
Para vetores não ordenados e relativamente pequenos, apesar de pouco sofisticada, a pesquisa sequencial se mostra eficaz. Para vetores demasiadamente grandes, recomenda-se primeiro aplicar um algoritmo de ordenação.
Exercício 2 – Em grupo – Para entregar:
Em sua opinião, como este método funcionaria para localizar um nome num catálogo de telefones? Como você implementaria ou alteraria este algoritmo? Comente a eficiência do mesmo.
R: Sim, porem de pouca eficiência, pois o catalogo está em ordem alfabética, e é uma grande massa de dados.
Utilizando ponteiros para cada letra do alfabeto, sendo cada letra um vetor. E a busca direcionada para letra em questão de forma sequencial.
Dividir a massa de dados em blocos ganhando tempo para pesquisa
Exercício 3 – Em grupo – Para entregar:
Se você fosse implementar um algoritmo para realizar esta busca, como ele procederia? Qual seria a chave de busca? Discuta com seu grupo e forneça uma ou mais soluções.
Aula 03 – Exercicios
Implemente em C ou em Português estruturado uma Pesquisa Binária.
Exemplo de Resposta para o Exercício Proposto:
Possível resolução para implementação em C de uma Pesquisa Binária.
Esta função irá receber três argumentos: um ponteiro para o vetor a ser pesquisado, o número total de elementos armazenados neste vetor e o dado a ser pesquisado.
pesq_bin(char *vetor, int tam, char chave)
{
int max, min, meio;
min = 0;
max = tam-1;
while(min <= max) {
meio = (min + max) / 2;
if(chave < vetor[meio])
max = meio - 1;
else
if(chave > vetor[meio])
min = meio + 1;
else return meio; /* encontrou */
}
return -1;
}
Análise do algoritmo:
A cada iteração do algoritmo, o tamanho da tabela é dividido ao meio. O número de vezes que o tamanho da tabela é dividido ao meio é cerca de log n.
O custo para manter a tabela ordenada é alto: a cada inserção na posição p da tabela implica no deslocamento dos registros a partir da posição p para as posições seguintes. Consequentemente, a pesquisa binária não deve ser usada em aplicações muito dinâmicas.
Inicio
Min=0, max = 8
Chave = caractere
então
Meio = (min+max)/2
Se meio = chave então retorna meio senão
Se meio > chave então
Min = meio + 1 entao
Meio = ( min+max)/2
Se meio = chave então retorna meio senão
Se meio < chave então
Max = meio – 1
Então
Meio = ( min+max)/2
Se meio = chave então retorna meio senão
...