Livro
Livro com dois capítulos (cada capítulo com 1 sub-capítulos)
2. Capítulo 2
2.1. Sub-Capítulo 2
5.8.1.1.1 - Algoritmo de Busca Linear
Este algoritmo faz uma busca no vetor procurando todas as ocorrências do elemento desejado, portanto este algoritmo permite elementos duplicados no vetor. O algoritmo mostra a posição onde o elementos foi encontrado dentro do vetor. Á variável C é um contador, para verificar se foi encontrada alguma ocorrência.
5.8.1.1.1.1 - Estrutura do Algoritmo
writeln('Entre com o elemento a ser encontrado no vetor !');
readln(e);
i := 1;
while (i <= n) do
begin
if(mat[i] = e) then
begin
writeln('Elemento ',e,' encontrado na posicao ',i);
c := c + 1;
end;
i :=i +1;
end;
5.8.1.1.1.2 - Programa Completo
(** Programa para testar o algoritmo de Busca Linear **
** Para n ocorrencias de um elemeto desejado ***
** Autor: Ricardo W. Saad **
** Data : 10/03/97 **
** Para um vetor de 30 elementos **)
program Busc_lin;
var
mat:array[1..30] OF INTEGER;
n:integer;
i:integer;
e:integer;
c:integer;
begin
n :=0;
i :=0;
c :=0;
e :=0;
writeln('Entre com a quantidade de elementos do vetor no maximo 30');
readln(n);
while (i <= n) do
begin
mat[i] := 0;
i := i + 1;
end;
writeln('Entre com os elementos do vetor');
for i:= 1 to n do
readln(mat[i]);
writeln('Elementos lidos ');
writeln;
for i:= 1 to n do
write(mat[i],' ');
writeln;
writeln('Entre com o elemento a ser encontrado no vetor !');
readln(e);
i := 1;
while (i <= n) do
begin
if(mat[i] = e) then
begin
writeln('Elemento ',e,' encontrado na posicao ',i);
c := c + 1;
end;
i :=i +1;
end;
if(c=0) then
begin
writeln('Elemento ',e,'nao encontrado');
end
else
begin
writeln('Elemento ',e,' econtrado ',c,' vezes');
end;
end.
5.8.1.1.1.3 - Teste de Mesa
mat
44 |
55 |
12 |
42 |
94 |
18 |
06 |
67 |
1 2 3 4 5 6 7 8
E |
I |
N |
C |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5.8.1.1.2 - Algoritmo de Busca Binária
O algoritmo de Busca Binária requer que os elementos do vetor estejam ordenados de forma crescente e não permite a existencia de elementos duplicados no vetor. Este algoritmo trabalha com posições fornecidas pelo usuário, na tentativa de localizar o elemento desejado , o algoritmo verifica se o elemento procurado é menor ou maiior que o elemento que se encontra na posição sugerida pelo usuário , desprezando os elementos do vetor que se encontrem abaixo ou acima da posição sugerida.
5.8.1.1.2.1 - Estrutura do Algoritmo
writeln('Entre com o elemento a ser encontrado no vetor !');
readln(e);
i := 1;
r := n;
found := 1;
while (i <= n) and (found = 1) do
begin
writeln;
writeln('Entre com uma posicao entre ',i,' e ',r);
readln(pos);
if (pos < i ) or (pos > r) then
found := 1
else
begin
if(mat[pos] = e) or (i = r) then
begin
writeln;
writeln('Elemento ',e,' encontrado na posicao ',pos);
found:=0;
end
else
begin
if mat[pos] < e then
i :=pos + 1
else
r := pos - 1
end
end;
end;
end
5.8.1.1.2.2 - Programa Completo
(** Programa para testar o algoritmo de Busca Binaria **
** Para 1 ocorrencias de um elemeto desejado ***
** Requer que o vetor esteja ordenado e sem elementos duplicados **
** Autor: Ricardo W. Saad **
** Data : 10/03/97 **
** Para um vetor de 30 elementos **)
program Busc_bin;
uses Crt;
var
mat:array[1..30] OF INTEGER;
n:integer;
i:integer;
e:integer;
c:integer;
j:integer;
temp:integer;
r:integer;
found:integer;
pos:integer;
begin
n :=0;
i :=0;
c :=0;
e :=0;
clrscr;
writeln('Entre com a quantidade de elementos do vetor no maximo 30');
readln(n);
while (i <= n) do
begin
mat[i] := 0;
i := i + 1;
end;
writeln('Entre com os elementos do vetor');
for i:= 1 to n do
begin
readln(mat[i]);
for j:= 1 to i do
begin
if (mat[i] = mat[j]) and (i <> j) then
begin
writeln;
writeln('Elemento duplicado ! Digite outro valor');
i := i - 1;
end;
end;
end;
(** Ordenacao do vetor **)
for i := 1 to n do
begin
for j:= n downto i do
begin
if(mat[i] > mat[j]) then
begin
temp := mat[i];
mat[i] := mat[j];
mat[j] := temp;
end;
end;
end;
writeln('Elementos lidos e ordenados');
writeln;
for i:= 1 to n do
write(mat[i],' ');
writeln;
writeln('Entre com o elemento a ser encontrado no vetor !');
readln(e);
i := 1;
r := n;
found := 1;
while (i <= n) and (found = 1) do
begin
writeln;
writeln('Entre com uma posicao entre ',i,' e ',r);
readln(pos);
if (pos < i ) or (pos > r) then
found := 1
else
begin
if(mat[pos] = e) or (i = r) then
begin
writeln;
writeln('Elemento ',e,' encontrado na posicao ',pos);
found:=0;
end
else
begin
if mat[pos] < e then
i :=pos + 1
else
r := pos - 1
end
end;
end;
end.