ex1g

Universidade Federal de Minas Gerais
Departamento de Ciência da Computação
Algoritmos e Estruturas de Dados II

1ª Lista de Exercícios - GABARITO



Esta lista deverá ser entregue para os professores durante a aula do dia 13 de setembro de 2011. Não serão recebidas listas por e-mail.
Todos os programas devem ser feitos em C.

1. São dados 2n números distintos distribuídos em dois vetores com n elementos A e B ordenados de maneira tal que:
A[1] > A[2] > A[3] > ... > A[n] e B[1] > B[2] > B[3] > ... > B[n]
Apresente um algoritmo linear para encontrar o n-ésimo maior número dentre estes 2n elementos.
Para encontrar o maior elemento, basta comparar o elemento A[1] com B[1], o maior será o maior elemento do conjunto. Para encontrar o segundo maior elemento, basta comparar o elemento A[1] com B[1]. Se o
A[1] for o maior, basta compara o A[2] com o B[1], senão serão comparados os elementos A[1] com B[2].
Neste caso, serão necessárias 2 comparações. Para encontrar o n-ésimo maior elemento, basta realizar n comparações. 2. Considere o problema de encontrar a posição de inserção de um novo elemento em um conjunto ordenado:
A[1] > A[2] > A[3] > ... > A[n]
a) Apresente a situação e/ou entrada de dados em que ocorre o melhor caso e o pior caso.
b) Apresente um algoritmo para resolver o problema acima.
a) Resolução através de busca binária. Existem n+1 lugares possíveis para inserir este novo elemento.
Melhor caso: elemento será inserido após o elemento que está na posição n/2.
Pior caso: elemento será inserido na posição 1 ou n+1. Para inserir um novo elemento serão necessárias, no pior caso log(n + 1) comparações.
3. Considere a função abaixo: int X(int a)
{
if (a<=0) then return 0; else return (a + X(a-1));
}
a) O que essa função faz?
b) Calcule a sua ordem de complexidade. Mostre como você chegou a esse resultado.
c) Escreva uma função não-recursiva que resolve o mesmo problema. Qual é a ordem de complexidade da sua função? Explique.
d) Qual implementação é mais