Algoritmo Estruturado

Algoritmo Estruturado

(Parte 2 de 2)

Pesquisa Binária

O método de pesquisa seqüencial é fácil de escrever e é razoavelmente eficientes para seqüências com poucos elementos. Entretanto, para seqüências de tamanho considerável, que ocorrem na maioria das aplicações existentes, a utilização do método torna-se inviável. Uma estratégia interessante e eficiente é utilizada no método de pesquisa binária.

Descrição Geral do Método:

  • Definir intervalo inicial (i, f) de busca

  • Determinar a posição média do intervalo(m = (i+f) DIV 2)

  • Comparar o elemento da posição média (v[m]) com o elemento E:

  • Caso sejam iguais então terminou as pesquisa

  • Caso contrário definir o novo intervalo de busca

  • Aplicar sucessivamente o passo anterior até encontrar E ou não existir mais o intervalo de busca

São aspectos fundamentais do método:

  • vetor de entrada tem que estar ordenado

  • intervalo de busca inicial é (i,f) = (1,n)

  • intervalo de busca, considerado a cada iteração, é definido do seguinte modo:

(i,m-1), se (E < v[m])

(m+1,f), se (E > v[m])

tendo a metade do tamanho do intervalo original

  • O teste de repetição é (i <= f) e Não Achou

Dados :

vetor de n elementos (n conhecido)

elemento a ser pesquisado no vetor

Resultado

Se o elemento existe, mostra-se a sua posição ou o total de ocorrências deste no vetor.

Se o elemento não existe, mostra-se uma mensagem de falha

ALGORÍTMOS DE ORDENAÇÃO

Os problemas de ordenação são comuns tanto em aplicações comerciais quanto científicas. Entretanto, raro são os problemas que se resumem à pura ordenação de seqüências de elementos. Normalmente, os problemas de ordenação são inseridos em problemas de pesquisa, intercalação e atualização. Isto torna ainda mais importante o projeto e a construção de algoritmos eficientes e confiáveis para tratar o problema.

O nosso objetivo é analisar os seguintes tipos de ordenação :

a. Selection Sort

b. Bubble Sort

c. Insertion Sort

a. Selection Sort

Este método é um dos mais simples e intuitivos dentre os métodos existentes. Sua estratégia básica é selecionar o menor elemento da seqüência considerada e colocá-lo no início da seqüência. Assim, dada uma seqüência de tamanho n, várias iterações são efetuadas, sendo que a cada vez que esta estratégia é aplicada, uma nova seqüência é gerada pela eliminação do menor elemento da seqüência original.

Procedure SelectionSort ( var vet : vetor; n : integer);

{ordenado crescente}

var

i, j, pmin : integer;

begin

for i 1 to (n-1) do

begin

pmin  i;

for j (i+1) to n do

if vet[j] < vet[pmin]

then pmin  j;

trocar (vet[i], vet[pmin] ) ;

end;

end;

b. Bubble Sort

A estratégia utilizada pelo BubbleSort consiste de comparações e trocas entre elementos consecutivos da seqüência, a fim de "empurrar" o maior elemento para a última posição. Assim, várias iterações são efetuadas e, para cada seqüência considerada, a aplicação da estratégia gera uma nova seqüência pela eliminação do maior elemento da seqüência original.

Além disto, uma variável de controle (lógica) é utilizada para registrar a ocorrência ou não de troca entre elementos da seqüência. Quando nenhuma troca é efetuada, tem-se que a seqüência considerada já estava ordenada. Esta particularidade determina, em alguns casos, um número menor de comparações que o método SelectionSort.

Procedure BubbleSort ( var vet : vetor ; n integer) ;

{ordem crescente}

var

i, limite : integer;

trocou : boolean;

begin

limite  n;

repeat

trocou  false;

for i 1 to (limite - 1) do

begin

if vet[i] > vet [i+1] then

begin

trocar(vet[i], vet[i+1]);

trocou  true;

end;

end;

limite  limite - 1

until not trocou

end;

c. Insertion Sort

Este método baseia-se no seguinte processo de inserção controlada:

  • Com o primeiro elemento da seqüência forma-se uma seqüência de tamanho 1, ordenada.

  • Cada elemento restante da seqüência original é inserido na seqüência, de modo que esta permaneça ordenada. Isto é feito através de uma pesquisa na seqüência ordenada que determina a posição que o novo elemento deverá ser inserido.

  • Quando um elemento é inserido a frente de outro, estes deverão ser deslocados de uma posição.

RECURSIVIDADE

Recursão é um método geral para resolver problemas reduzindo-os a problemas mais simples do mesmo tipo. A estrutura geral de uma solução recursiva de um problema é assim :

Resolva de forma recursiva um problema.

  • Se o problema é trivial, faça o obvio (resolva-o)

  • Simplifique o problema

  • Resolva de forma recursiva (um problema mais simples)

  • Combine (na medida do possível) a solução do(os) problemas mais simples em uma solução do problema original

Um subprograma recursivo chama a si próprio constantemente, cada vez em uma situação mais simples, até chegar ao caso trivial, quando pára. Devemos lembrar que recursividade deve ser utilizada na solução de problemas que tenham a natureza recursiva.

Exemplos :

  1. Somatório de inteiros - Se n =1; Somatório = 1. Caso contrário Somatório = n + Somatório(n-1)

  2. Fatorial - Se n=0 ou n=1 ; Fatorial = 1. Caso contrário Fatorial = n*Fatorial(n-1)

  3. MDC - Se b divide a, então o MDC é b. Caso contrário, MDC(a,b) = MDC(b,a mod b)

  4. N-ésimo termo da série de Finonacci . 1 e 2 = 1 e n-ésimo = (n-1)+(n-2)

  5. Torre de hanoi

Bibliografia

INTRODUÇÃO AO DESENVOLVIMENTO DE ALGORITMOS

WILSON SILVA PINTO

ALGORITMOS

JOSE AUGUSTO MANZANO - JAYR FIGUEIREDO OLIVEIRA

ALGORITMOS E ESTRUTURAS DE DADOS

NIKLAUS WIRTH

ALGORITMOS E ESTRUTURAS DE DADOS

ANGELO DE MOURA GUIMARAES - NEWTON A C LAGES

ALGORITMOS ESTRUTURADOS

H FARREL - C G BECKER - E C FARIA e MATOS, H F

PROJETO DE ALGORITMOS

NIVIO ZIVIANI

(Parte 2 de 2)

Comentários