Algoritmos de pesquisa
1
Algoritmos de pesquisa
1. Escreva um programa que permita efectuar a pesquisa sequencial nos dados que se
encontram no ficheiro “dados2.txt”. Use para chave o campo Num.
2. Escreva uma função recursiva para a pesquisa binária e use-a para fazer pesquisa de dados
no ficheiro “dados2.txt”. Use para chave o campo Num.
3. Construa os seguintes subprogramas:
- LerVector (para inserir o tamanho de um vector de inteiros e depois construi-lo),
- OrdenarDecrescente (ordena decrescentemente um vector), e
- PesquisarElemento (determina o índice/posição de um elemento x num vector V -- se
existirem vários valores iguais a x, devolve o de menor índice/posição).
Usando estes três subprogramas, implementar um programa em C que:
a) leia/construa o vector V;
b) determine a quantidade de valores de V iguais ao menor valor de V;
c) mostre o resultado obtido.
4. Os números de Fibonacci são os inteiros positivos dados pelas seguintes expressões:
Fib(0) = 1; Fib(1) = 1; Fib(a) = Fib(j-1) + Fib(j-2), j ≥ 2
Usando estes números pode ser implementado um método de pesquisa: a pesquisa de
Fibonacci. Dado um vector X com N elementos ordenados pela chave, este algoritmo permite
pesquisar o vector pelo elemento com chave k. O elemento na posição X[0] é ignorado.
Assume-se que N + 1 = Fib(j+1) (é um número de Fibonacci). Algoritmo:
P1: [Inicialização] Fazer i = Fib(j); p = Fib(j-1) e q = Fib(j-2). (neste algoritmo p e q
serão sempre números de Fibonacci consecutivos).
P2: [Comparação] Se k < ki ir para P3. Se k > ki ir para P4. Se k = ki termina com
sucesso (devolve i).
P3: [Diminuir i] Se q = 0 o algoritmo termina sem sucesso (devolve -1). Senão fazer
i = i − q, aux = p, p = q e q = aux − q. Voltar a P2.
P4: [Aumentar i] Se p = 1 o algoritmo termina sem sucesso (devolve -1). Senão fazer
i = i + q, p = p − q e q = q − p. Voltar a P2.
Implemente este método de pesquisa e teste-o com um dos ficheiros disponíveis.
5. Implemente uma agenda electrónica para manter os contactos dos seus amigos. Ofereça
serviços de ordenação dos registos por nome, por data de nascimento, por operador de
serviço telefónico (indicativo da região para números da rede fixa) e por endereço de e-mail
(nome de utilizador ou designação do domínio). Permita que o utilizador pesquise a agenda
por nome do contacto e por número de telefone.
Programação e Algoritmos / Programação II / Algoritmos e Estruturas de Dados
Algoritmos de pesquisa
2
6. Considere o seguinte algoritmo correspondente a um método de ordenação (para um vetor V
de tamanho N):
Para i desde 0 até N-1 fazer
Para j desde (i+1) até N-1 fazer
Se (V[i] > V[j]) então
temp ← V[i];
V[i] ← V[j]
V[j] ← temp
a) Simule as duas primerias iterações do algoritmo para o seguinte exemplo:
V
9
7
2
8
10
3
V
1ª iteração
V
2ª iteração
b) Construa uma função em C que traduza este algoritmo.
7. Considere-se uma estrutura do seguinte tipo:
typedef struct {
int
num;
char nome[80];
float nota;
} ALUNO;
Tendo em consideração todas as funções estudadas nas aulas, construir um programa que:
➔ leia um vector de estruturas daquele tipo (utilize os dados do ficheiro “dados5.txt”);
➔ peça uma chave a pesquisar (valor inteiro associado ao campo num);
➔ verifique se existe algum elemento do vector com esta chave e se existe escrever os
dados que lhe estão associados;
➔ Determinar e mostrar o número de alunos com nota superior ou igual à nota obtida
pelo aluno cujo valor do campo num é igual à chave dada;
➔ Determinar a média obtida pelos alunos com notas superiores ou igual à nota obtida
pelo aluno cujo valor do campo num é igual à chave dada.
Método de resolução:
Considerando definida a estrutura ALUNO, implementar as seguintes funções:
a) Determinar o número de alunos com nota superior ou igual a um valor k.
b) Determinar a soma das notas obtidas pelos alunos com nota superior ao valor k.
Programação e Algoritmos / Programação II / Algoritmos e Estruturas de Dados