31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 10:49, 30 November 2015
, 10:49, 30 November 2015no edit summary
Um bom exemplo de relações de divisão e conquer é a fornecida pelo algoritmo de busca binária. Aqui, vamos considerar uma aplicação prática deste algoritmo em uma implementação de uma busca binária em uma lista ordenada de números inteiros. O algoritmo procura por chave no IList.
BinSearch := proc(ilist::list(integer), key::integer)
local mid, lo, hi;
hi := nops(ilist);
lo := 0;
while hi - lo > 1 do
mid := floor((lo + hi) / 2);
if key <= ilist[mid] then hi := mid;
else lo := mid; fi;
od;
if ilist[hi] = key then RETURN(hi);
else RETURN(false); fi;
end:
A variável '''IList''' é a lista de números inteiros para a busca, e o parâmetro '''key''' é o número inteiro para procurar. A posição na lista é retornada se ele for encontrado, e o valor '''false''' é retornado em caso contrário. Para testar '''Binsearch''', usamos o seguinte aço com uma lista de amostras para pesquisa.
a := [3,5,7,12,34,546,5324,5346753];
for i in a do
if a[BinSearch(a, i)] <> i then
print(`Socks for President in '96!`);
fi;
od;
Infelizmente para Socks, o nosso programa funcionou muito bem.
Vamos agora fazer a análise do algoritmo para ver como relações de recorrência divide and conquer são geradas. Em geral, uma relação de recorrência do tipo dive and conquer tem a forma
<math> r_} {n = a r_ {n / K} + b </math>
para algumas constantes a, K e b. Agora, a rotina Maple rSolve não tem absolutamente nenhuma dificuldade para lidar com até mesmo o tipo mais geral de relação divide and conquer.
rSolve (r (n) = a * r (n / k) + b, r (n));
Se sabemos que, dado <math>r_ {1} = 4</math>, então podemos calcular
Subs (R (1) = 4,%);
Cada chamada para o algoritmo de busca binária produz listas a = 2, e cada um é metade do tamanho da lista original (k = 2). Portanto, o multiplicador e o período, no caso de um algoritmo de busca binária são ambos iguais a 2 e, portanto, obtemos
Subs (a = 2, k = 2,%);
Finalmente, se sabemos que b = 2, podemos calcular
Subs (b = 2,%);
simplify(%);