Livro Texto: ALGORITMOS - Teoria e Prática
Capítulo 2 - Conceitos Básicos
Redator: André Santanchè
Nota: |
Questão 2.1-3 |
Considere o problema de pesquisa:
Entrada: Uma seqüência de n números A = <a1,
a2, ..., an> e um valor
v.
Saída: Um índice i tal que v = A[i] ou o
valor especial NIL, se v não aparecer em A.
Escreva um pseudocódigo para pesquisa linear, que faça
a varredura da seqüência, procurando por v {a}. Usando um loop invariante, prove que seu
algoritmo é correto. Certifique-se de que seu loop invariante satisfaz
às três propriedades necessárias {b}.
Resolução |
{a} Pseudocódigo
int busca_linear(int ve[], int n, int v)
{
for (int i = 0; i < n; i++)
{
if (ve[i] == v) return i;
}
return NULL;
}
Questão 2.2-2 |
Considere a ordenação de n números armazenados no
arranjo A, localizando primeiro o menor elemento de A e permutando
esse elemento com o elemento contido em A[1]. Em seguida, encontre o
segundo menor elemento de A e o troque pelo elemento A[2]. Continue
dessa maneira para os primeiros n-1 elementos de A. Escreva o
pseudocódigo para esse algoritmo, conhecido como ordenação
por seleção {a}.
Que loop invariante esse algoritmo mantém? {b}
Por que ele só precisa ser executado para os n-1 elementos, e
não para todos os n elementos? {c}
Forneça os tempos de execução do melhor caso e do pior
caso da ordenação por seleção em notação
{d}.
Resolução |
{a}
Pseudocódigo
for i = 1 to length[A] - 1
menor = i
for j = i+1 to length[A]
if A[menor] > A[j]
menor = j
tmp = A[i]
A[i] = A[menor]
A[menor] = tmp
{c} Porque trata-se de um algoritmo baseado na comparação de um elemento chave com seus vizinhos de modo que se possa selecionar o menor elemento do subconjunto em questão e se realizar uma troca. Quando resta apenas um último elemento a ser ordenado, já não há mais outros elementos com os quais comparar, além disto, este último elemento já ocupa a sua posição correta na ordenação de maior elemento.
{d} (n2)
tanto no melhor quanto no pior caso.
Questão 2.3-7 |
Descreva um algoritmo de tempo (n lg n) que, dado um conjunto S de n
inteiros e outro inteiro x, determine se existem ou não dois elementos
em S cuja soma seja exatamente x.
Resolução |
soma_igual(S, x, existem)
merge_sort(S)
existem = false
esquerda = 1
direita = length[S]
while esquerda < direita and S[esquerda]+S[direita] <>
x
if S[esquerda]+S[direita] > x
direita = direita - 1
else
esquerda = esquerda + 1
if esquerda < direita
existem = true
Explicação:
O princípio de funcionamento deste algoritmo pode ser entendido
da seguinte maneira: