A maior rede de estudos do Brasil

Grátis
Estruturas_de_Dados_e_Algoritmos_em_C.erivanildo- Blog - conhecimentovaleouro.blogspot.com by @viniciusf666

Pré-visualização | Página 50 de 50

6.5 apresenta a função que determina, a partir de um 
índice inicial de pesquisa, o índice do elemento do agregado com o melhor valor que não 
excede o valor pretendido. Começa-se por procurar o primeiro valor que serve. Caso ele 
não exista, a função devolve o índice î1 como sinal de pesquisa falhada. Caso contrário 
procura-se até ao último elemento do agregado um elemento com um valor melhor, ou 
seja, um elemento com um valor que seja ainda maior do que o já encontrado e que não 
exceda o valor procurado. Se pretendermos pesquisar todo o agregado, basta invocar a 
função a partir do primeiro elemento do agregado. 
 
 
Figura 6.5 - Função que determina o elemento do agregado com o melhor valor que serve. 
int ProcurarMelhor (int seq[], unsigned int nelem,\ 
 unsigned int inicio, int valor) 
{ 
 int indmelhor; unsigned int indactual; 
 
 indmelhor = ProcurarPrimeiro (seq, nelem, inicio, valor); 
 if (indmelhor == -1 ) return -1; 
 for (indactual = indmelhor+1; indactual < nelem; indactual++) 
 if (seq[indactual] > seq[indmelhor] && seq[indactual] <= valor) 
 indmelhor = indactual; 
 return indmelhor; 
} 
int ProcurarPrimeiro (int seq[], unsigned int nelem,\ 
 unsigned int inicio, int valor) 
{ 
 unsigned int indactual; 
 
 for (indactual = inicio; indactual < nelem; indactual++) 
 if (seq[indactual] <= valor) return indactual; 
 return -1; 
} 
PROGRAMAÇÃO ESTRUTURAS DE DADOS E ALGORITMOS EM C 6 
6.1.1.6 Procurar o pior que serve 
A terceira estratégia de optimização consiste em procurar no agregado, o valor menos 
próximo do valor pretendido, ou seja, o pior valor. Este algoritmo designa-se por o pior 
que serve ( worst fit ). Por vezes, uma estratégia pela negativa é melhor do que pela positiva. 
Imagine-se por exemplo, que se pretende aproveitar uma sobra de 100 cm de uma calha de 
alumínio e que temos a necessidade de cortar secções de 80 cm, 50 cm e 40 cm. Uma 
estratégia o melhor que serve escolherá o valor 80 cm, desperdiçando 20 cm, enquanto que 
uma estratégia o pior que serve escolherá sucessivamente os valores 40 cm e 50 cm, 
desperdiçando apenas 10 cm. 
 
A Figura 6.6 apresenta a função que determina, a partir de um índice inicial de pesquisa, o 
índice do elemento do agregado com o pior valor que não excede o valor pretendido. 
Começa-se por procurar o primeiro valor que serve. Caso ele não exista, a função devolve 
o índice î1 como sinal de pesquisa falhada. Caso contrário procura-se até ao último 
elemento do agregado um elemento com um valor pior, ou seja, um elemento com um 
valor que seja ainda menor do que o já encontrado. Se pretendermos pesquisar todo o 
agregado, basta invocar a função a partir do primeiro elemento do agregado. 
 
 
Figura 6.6 - Função que determina o elemento do agregado com o pior valor que serve. 
6.1.1.7 Exemplificação dos algoritmos de pesquisa sequencial 
A Figura 6.7 apresenta a aplicação destes algoritmos num agregado com vinte elementos 
úteis. Se pesquisarmos o agregado a começar no elemento de índice 7, temos que, o maior 
valor é o elemento com índice 19, cujo valor é 250, e o menor valor é o elemento com 
índice 11, cujo valor é 1. Se procurarmos um elemento no agregado com valor 55, a 
começar no elemento de índice 7, encontramos o elemento com índice 16. Mas, se 
procurarmos um elemento com valor 40, não conseguimos encontrar nenhum valor, pelo 
que, a função devolve o índice î1. 
 
O primeiro elemento com valor que não excede 40, a começar no elemento de índice 7, é o 
elemento com índice 7, cujo valor é 32. Nas mesmas circunstâncias, o elemento com o 
melhor valor é o elemento com índice 15, cujo valor é 39, e o elemento com o pior valor é 
o elemento com índice 11, cujo valor é 1. No entanto, se começarmos a pesquisa no 
elemento de índice 17 do agregado, não encontraremos nenhum valor que não exceda 40, 
pelo que, as funções, o primeiro que serve, o melhor que serve e o pior que serve devolvem 
o índice î1. 
 
int ProcurarPior (int seq[], unsigned int nelem,\ 
 unsigned int inicio, int valor) 
{ 
 int indpior; unsigned int indactual; 
 
 indpior = ProcurarPrimeiro (seq, nelem, inicio, valor); 
 if (indpior == -1 ) return -1; 
 for (indactual = indpior+1; indactual < nelem; indactual++) 
 if (seq[indactual] < seq[indpior]) indpior = indactual; 
 return indpior; 
} 
7 CAPÍTULO 6 : PESQUISA E ORDENAÇÃO 
20 3 330 25 22 24 15 32 42 2 5 1 8 7 6 39 55 145 209 250
Posição
Inicial de
Pesquisa
Maior
Valor
Menor
Valor
Valor
55
Primeiro
Valor<=40
Melhor
Valor<=40
Pior
Valor<=40
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 
Figura 6.7 - Resultados da utilização dos algoritmos de pesquisa sequencial. 
6.1.2 Pesquisa Binária 
Uma forma de acelerar a pesquisa consiste em utilizar uma estratégia de partição sucessiva 
do agregado ao meio para diminuir o número de elementos a analisar. Mas, este método de 
pesquisa só funciona se os elementos estiverem ordenados. A Figura 6.8 apresenta a função 
de pesquisa binária, na sua versão iterativa, que calcula o índice do elemento com o valor 
procurado. Como não temos a certeza que o valor procurado existe de facto no agregado, a 
função devolve o índice î1 como sinal de pesquisa falhada. Com o objectivo de tornar a 
função o mais versátil possível, a função tem duas variáveis de entrada que indicam os 
índices dos elementos onde deve começar e acabar a pesquisa. 
 
 
Figura 6.8 - Função de pesquisa binária que procura um valor no agregado (versão iterativa). 
Vamos mostrar na Figura 6.9, o funcionamento deste algoritmo, para o caso de um 
agregado com vinte elementos ordenado por ordem crescente. Pretendemos procurar o 
valor 34. Vamos invocar a função para todos os elementos úteis do agregado, ou seja, do 
elemento de índice 0 até ao elemento nelemî1, que neste caso é o elemento de índice 19. 
Calcula-se o elemento médio do agregado, através da divisão inteira da soma das posições 
mínima e máxima, e que neste caso é o elemento de índice 9. Como o valor procurado, que 
é 34, é menor do que valor armazenado no elemento médio, neste caso 44, então isso 
significa que ele se encontra na primeira metade do agregado, pelo que, a posição máxima 
passa para o elemento à esquerda da posição média, ou seja, a nova posição máxima é 
agora o elemento de índice 8. Se pelo contrário, o valor procurado fosse maior do que 44 
então isso significava que ele se encontrava na segunda metade do agregado, pelo que, a 
nova posição mínima passaria para o elemento à direita da posição média, ou seja, a nova 
int ProcuraBinariaIterativa (int seq[], unsigned int inicio,\ 
 unsigned int fim, int valor) 
{ 
 unsigned int minimo = inicio, maximo = fim, medio; 
 
 while (minimo <= maximo) 
 { 
 medio = (minimo + maximo) / 2; /* cálculo da posição média */
 
 if (seq[medio] == valor) return medio; /* pesquisa com sucesso */
 
 /* actualização dos limites do intervalo de pesquisa */
 if (seq[medio] > valor) maximo = medio - 1; 
 else minimo = medio + 1; 
 
 return -1; /* pesquisa falhada */
} 
PROGRAMAÇÃO ESTRUTURAS DE DADOS E ALGORITMOS EM C 8 
posição mínima seria o elemento de índice 10. Agora que estamos a analisar a primeira 
metade do agregado, calcula-se a nova posição média, que é o elemento de índice 4. Como 
o valor procurado é maior do que valor armazenado no elemento médio, que é 26, então 
isso significa que ele se encontra na segunda metade do intervalo em análise, pelo que, a 
posição mínima passa para o elemento à direita da posição média, ou seja, para o elemento 
de índice 5. Agora, a nova posição média passa a ser o elemento de índice 6. Como o valor 
procurado ainda é maior do que valor