Classificação e pesquisa etapa 1

Páginas: 6 (1344 palavras) Publicado: 9 de abril de 2014
INTRODUÇÃO

É muito comum na área da informação a necessidades de pesquisas e com isso, a necessidade de algoritmos eficientes para a realização das mesmas. A disciplina de Classificação e Pesquisa tem como intuito o desenvolvimento dos algoritmos de busca e ordenação, assim como o entendimento dos mesmos. Na primeira etapa da ATPS serão abordados os conceitos de busca (pesquisa)binária e sequencial. Na segunda etapa os métodos de ordenação serão estudados, quer seja Ordenação por meio de seleção e troca, Ordenação por distribuição, Ordenação por inserção e Ordenação por intercalação. Na terceira e quarta etapa serão arvores binárias, AVL e Tabelas Hash. Todos os algoritmos serão implementados na linguagem C e utilizaremos o conhecimento da disciplina de Estrutura de Dados paraimplementar as estruturas e listas necessárias para a realizações de pesquisas e ordenação.
Relatório 1 – Pesquisa de Dados.

Para a realização dessa etapa da ATPS foi necessário a leitura dos conteúdos estipulados no primeiro passo. Após lermos o conteúdo, começamos a desenvolver o segundo passo que era a implementação de uma função de números inteiros randômicos. Após o segundo passo,implementamos a estrutura Residência, estrutura essa que representa abstratamente uma casa com suas informações de rua, número da casa, numero do medidor e medida de consumo. Para preencher as informações da estrutura Residência, foi utilizada a função desenvolvida no segundo passo da ATPS, pois a lista (vetor) utilizada contém o tamanho 1000 e não seria tão simples informar todos os valoresmanualmente. Foi desenvolvido um programa em C que gera uma lista estática sequencial utilizando a estrutura Residência e logo em seguida preenche a lista com informações randômicas da função RandomInteger, no entanto os números das casas são usados sequencialmente, pois para que o método de busca binária possa ser realizado, é necessário que a lista (vetor) esteja ordenado. No programa desenvolvidoexiste um menu com três opções: Buscar residências (Busca Sequencial), Buscar residências (Busca Binaria) e Imprimir lista de residências.
Foram realizados vários testes e podemos notar as diferenças de desempenho entre os tipos de busca sequencial e binária através de uma variável que é incrementada a cada comparação. No caso da busca sequencial o melhor caso de busca ocorrerá quando a residênciaprocurada estiver no primeiro espaço do vetor e o pior caso ocorrerá se a residência procurada estiver no último espaço do vetor. Na busca binária o melhor caso ocorrerá se a residência procurada estiver no meio do vetor e o pior caso ocorrerá quando a residência estiver no primeiro ou no último espaço do vetor. Em ambas as pesquisas vale salientar que ocorre o pior caso quando o elementoprocurado não estiver no vetor, pois todas as comparações possíveis serão realizadas.
Segue abaixo o código fonte do programa:
#include
#include
#include
#include
#define MAX 1000
//variaveis globais
int cont;
//

struct Residencia{
char rua[25];
int numCasa;
int numMedidor;
float medidaConsumo;
};
typedef struct Residencia residencia;

struct Lista{int qtd_res;
residencia casas[MAX];
};
typedef struct Lista Lista;

int RandomInteger (int low, int high){
int k;
double d;
d = (double)rand () / ((double) RAND_MAX + 1);
k = d * (high - low + 1);
return low + k;
}

void inicializa(Lista * L){
L->qtd_res=0;
}

int listaCheia(Lista * L){
return(L->qtd_res >=MAX);
}

int listaVazia(Lista * L){
return(L->qtd_res == 0);
}

void preencheLista(Lista * L){
int i;
for(i=0;icasas[i].rua,"Alameda dos Anjos");
L->casas[i].numCasa = i + 1; //RandomInteger (101,500);
L->casas[i].numMedidor = RandomInteger (1000,2000);
L->casas[i].medidaConsumo = RandomInteger (1,10000);
L->qtd_res++;
}
}...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Atps classificacao e pesquisa etapa 1
  • ATPS Classificação e Pesquisa
  • Atps classificação e pesquisa etapa 1 e 2
  • PESQUISA OPERACIONAL ETAPA 1
  • Pesquisa Etapas 1
  • Etapa 1 ATPS pesquisa operacional
  • ATPS CLASSIFICA O E PESQUISA ETAPA 1
  • 1 E 2 Etapa ATPS Pesquisa Operacional

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!