ATPS Contabilidade Classificação e Pesquisa

Classificação e Pesquisa

Hélio Filho

[e-mail]

Site: https://sites.google.com/a/aedu.com/heliofilho/

Ementa        

Métodos de Ordenação: seleção, troca distribuição, inserção, intercalação e cálculo de endereços

Pesquisa de dados: sequencial, binária, hashing, árvore de pesquisa, árvores binárias de pesquisa, árvores AUL (AVL?), árvore patrícia, B-Trees

Objetivos

Manipular estrutura de ordenação e pesquisa

Sistema de avaliação

1ª avaliação – Peso 4

Práticas: 3,0 pts

Teórica: 7,0 pts

2ª avaliação – Peso 6

Práticas: 3,0 pts

Teórica: 7,0 pts

Projeto de Algorítimos

Ziviani, Nívio

3ª Ed. São Paulo

Contextualização

Apresentaremos e disutiremos estratégias para efetuarmos a pesquisa de um elemento específico em um conjunto de dados.

Esta é uma operação muito importante, uma vez que é encontrada em diversas aplicações.

Apresentaremos os métodos de pesquisa sequencial e binária sobre a estrutura de dados vetor.

Pesquisa sequencial

É a forma mais simples de se realizar pesquisas. Consiste em percorrer todo o vetor, elemento por elemento, verificando se o item desejado está presente no vetor.

21

14

36

5

76

95

78

7

35

48

56

71

Perguntas:

1- Como verificar se o elemento 48 está no vetor?

2- Quantas comparações são necessárias para encontrar o elemento 48?

void main(){

        int vet[12]= {21,14,36,5,76,95,78,7,35,48,56,71}

        int i, bachou = 0, num = 48;

        

        for (i = 0; i < 12 && bachou ==0; i++) {

                if (vet[i] == num)

                        bachou = 1;

                if (bachou == 1) {

                        printf (“O elemento %d esta no vetor”, num)

                        printf (“Foram realizadas %d comparações”, i)

                }

}

Exercício:

1- Reescreva o exercício anterior utilizando funções, sendo:

        1.1- Ler Vetor → carregar os elementos do vetor

        1.2- Informar Numeros → Solicitar ao usuário um número para ser pesquisado no vetor

        1.3- Buscar Elementos → Percorrer o vetor em busca do número solicitado pelo usuário

        1.4- Exibir Resultado → Exibe o relatório da pesquisa

2- Transcreva o exercício anterior para Java (em casa)

void LeVetor (int vet[12]){

        int i;

        for (i = 0; i < 12; i++){

                printf (“Informe um número”);

                scanf (“%d”, &vet[i]);

        }

}

int InformaNumero (){

        int num;

        printf (“Qual numero deseja buscar?”);

        scanf (“%d”, &num);

        return num;

}

int BuscaElemento (int vet[], int num){

        int i;

        for (i = 0; i < 12; i++){

                if (vet[i] == num)

                return i;

        }

return -1

}

ExibeResultado (int res, int num){

        if (res < 0 )

                printf (“O elemento %d não foi encontrado”, num);

        else

                printf (“O elemento %d foi encontrado com %d consultas”, num, res);

}

void main (){

int vet [12], num, bRet;

        LeVetor(vet[] );

        num = InformaNumero();

        bRet = BuscaEleemento (vet[], num);

        ExibeResultado(bRet, num);

}

Analise de complexidade:

A análise de complexidade se dará em função dos dados de entrada e será validado em torno de três situações

        Melhor caso: Corresponde ao menor tempo de execução sobre todas as possíveis entradas

        Pior caso: Corresponde ao maior tempo de execução sobre todas as entradas de tamanho N

        Caso médio: Corresponde à média dos tempos de execução de todas as entradas de tamanho N

→ No caso médio ou caso esperado, a analise é realizada com base em uma distribuição de probabilidades sobre o conjunto de entradas de tamanho N e o custo médio é obtido com base nessa distribuição.

Por essa razão, a analise do caso médio é geralmente mais dificil de se obter que as analises de melhor e pior casos.

Seja F uma função de complexidade tal que F(n) é o numero de registros consultados no arquivo, ou seja, o numero de vezes que a chave de consulta é comparada com a chave de cada registro, os casos a considerar são: