apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.917 seguidores
Pré-visualização50 páginas
6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 23 23 27 19 21 ? ? ? ? ? . . . ? ? ? ?
Isto e´, o 27 foi copiado da posic¸a\u2dco 7 para a posic¸a\u2dco 8 e o 23 foi copiado da posic¸a\u2dco
6 para a posic¸a\u2dco 7. Na figura acima destacamos os elementos que foram movidos de
lugar. Observando que o 23 ficou repetido na posic¸a\u2dco 6, o que na pra´tica resultou na
posic¸a\u2dco 6 livre. Agora basta inserir o 18 a´\u131:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 18 23 27 19 21 ? ? ? ? ? . . . ? ? ? ?
Esta etapa constitui o nu´cleo do algoritmo mostrado na figura 10.25. O lac¸o
externo apenas garante que esta operac¸a\u2dco sera´ executada para todos os elementos das
posic¸o\u2dces de 1 ate´ N .
O lac¸o interno foi implementado de tal forma que, ao mesmo tempo em que se
localiza o lugar certo do elemento da vez, ja´ se abre espac¸o no vetor. O lac¸o e´
controlado por dois testes, um deles para garantir que o algoritmo na\u2dco extrapole o
in´\u131cio do vetor, o outro que compara dois elementos e troca de posic¸a\u2dco sempre que for
detectado que o elemento esta´ na posic¸a\u2dco incorreta.
procedure insercao (var v: vetor ; n: integer) ;
var i , j : integer ;
aux: real ;
begin
for i := 1 to n do
begin
aux = v[ i ] ;
(\u2217 abre espaco no vetor enquanto localiza a posicao certa \u2217)
j:= i \u2212 1;
while ( j >= 1) and (v[ j ] > aux) do
begin
v[ j+1] = v[ j ] ;
j:= j \u2212 1;
end;
v[ j+1] = aux;
end;
end;
Figura 10.25: Me´todo de ordenac¸a\u2dco por inserc¸a\u2dco.
152 CAPI´TULO 10. ESTRUTURAS DE DADOS
Analisar quantas comparac¸o\u2dces sa\u2dco feitas e´ bem mais complicado neste algoritmo,
pois isto depende da configurac¸a\u2dco do vetor de entrada. Neste nosso exemplo, vimos
que cada etapa teve um comportamento diferente das outras. Em uma vez o elemento
ja´ estava em seu lugar. Em duas outras vezes tivemos que percorrer todo o subvetor
inicial, pois os elementos deveriam ser o primeiro, em cada etapa.
Aparentemente, no pior caso poss´\u131vel, que e´ quando o vetor esta´ na ordem inversa
da ordenac¸a\u2dco, havera´ o maior nu´mero de comparac¸o\u2dces, que e´ quadra´tico. Mas, na
pra´tica, este algoritmo aparenta ser mais ra´pido que o me´todo da selec¸a\u2dco na maior
parte dos casos, pois algumas vezes o elemento muda pouco de posic¸a\u2dco.4
10.1.5 Outros algoritmos com vetores
Nesta sec¸a\u2dco vamos apresentar alguns problemas interessantes que podem ser resolvidos
usando-se a estrutura de vetores.
Permutac¸o\u2dces
Vamos apresentar um problema matema´tico conhecido como permutac¸a\u2dco, propor uma
representac¸a\u2dco computacional em termos de vetores, e, em seguida, estudar alguns
problemas interessantes do ponto de vista de computac¸a\u2dco.5
Os matema´ticos definem uma permutac¸a\u2dco de algum conjunto como uma func¸a\u2dco
bijetora de um conjunto nele mesmo. Em outras palavras, e´ uma maneira de reor-
denar os elementos do conjunto. Por exemplo, podemos definir uma permutac¸a\u2dco do
conjunto {1, 2, 3, 4, 5 } assim: P (1) = 4, P (2) = 1, P (3) = 5, P (4) = 2, P (5) = 3.
Esquematicamente temos: (
1 2 3 4 5
4 1 5 2 3
)
Outra maneira seria: P (1) = 2, P (2) = 5, P (3) = 1, P (4) = 3, P (5) = 2. Esque-
maticamente: (
1 2 3 4 5
2 5 1 3 2
)
De fato, existem n! maneiras de se reordenar os elementos e obter uma permutac¸a\u2dco
va´lida. Se n = 5 enta\u2dco existem 120 permutac¸o\u2dces.
Modelando permutac¸o\u2dces
O primeiro problema interessante do ponto de vista algoritmico e´ como representar
4O site http://cg.scs.carleton.ca/~morin/misc/sortalg permite visualizar o comporta-
mento dos principais algoritmos de ordenac¸a\u2dco atrave´s de animac¸o\u2dces. Os dois algoritmos aqui ex-
plicados esta\u2dco la´, entre outros.
5Esta sec¸a\u2dco foi inspirada em uma preparato´ria para a maratona de programac¸a\u2dco da ACM da
Ural State Universisy (Internal Contest October\u20192000 Junior Session) encontrada na seguinte URL:
http://acm.timus.ru/problem.aspx?space=1&num=1024.
10.1. VETORES 153
uma permutac¸a\u2dco. Para isto pode-se usar um vetor de n posic¸o\u2dces inteiras, onde cada
posic¸a\u2dco e´ um valor (sem repetic¸a\u2dco) entre 1 e n. Em todos os algoritmos desta sec¸a\u2dco
consideraremos que:
const min i = 1; max i = 5;
Assim os dois vetores que representam as permutac¸o\u2dces acima sa\u2dco, respectivamente:
1 2 3 4 5
4 1 5 2 3
1 2 3 4 5
2 5 1 3 2
Testando permutac¸o\u2dces va´lidas
Uma vez resolvido o problema da representac¸a\u2dco, podemos estudar o pro´ximo de-
safio, que e´ como testar se um dado vetor (lido do teclado) e´ uma permutac¸a\u2dco va´lida?
O algoritmo tem que testar se, para os \u131´ndices de 1 a n, seus elementos sa\u2dco cons-
titu´\u131dos por todos, e apenas, os elementos entre 1 e n, em qualquer ordem. A func¸a\u2dco
da figura 10.26 apresenta uma poss´\u131vel soluc¸a\u2dco.
function testa permutacao (var v: vetor i ; n: integer) : boolean;
var i , j : integer ;
eh permutacao: boolean;
begin
eh permutacao:= true ;
i := 1;
while eh permutacao and ( i <= n) do
begin
j:= 1; (\u2217 procura se i esta no vetor \u2217)
while (v[ j ] <> i ) and ( j <= n) do
j:= j + 1;
i f v[ j ] <> i then (\u2217 se nao achou nao eh permutacao \u2217)
eh permutacao:= false ;
i := i +1;
end;
testa permutacao:= eh permutacao;
end; (\u2217 testa permutacao \u2217)
Figura 10.26: Verifica se um vetor define uma permutac¸a\u2dco.
Este algoritmo testa para saber se cada \u131´ndice entre i e n esta´ presente no vetor.
Para isto executa no pior caso algo da ordem do quadrado do tamanho do vetor.
No primeiro semestre de 2011 um estudante6 sugeriu que basta usar um vetor
6Cre´ditos para o DESCOBRIR O NOME DO ALUNO
154 CAPI´TULO 10. ESTRUTURAS DE DADOS
auxiliar, inicialmente zerado, e percorrer o vetor candidato a permutac¸a\u2dco apenas uma
vez. Para cada \u131´ndice, tentar inserir seu respectivo conteu´do no vetor auxiliar: se esti-
ver com um zero, inserir, sena\u2dco, na\u2dco e´ permutac¸a\u2dco. Se o vetor auxiliar for totalmente
preenchido enta\u2dco temos um vetor que representa uma permutac¸a\u2dco. Este processo e´
linear e esta´ ilustrado na figura 10.27.
function testa permutacao (var v: vetor i ; n: integer) : boolean;
var i , j : integer ;
aux: vetor ;
eh permutacao: boolean;
begin
zera vetor (aux,n) ;
eh permutacao:= true ;
i := 1;
while eh permutacao and ( i <= n) do
begin
if aux[v[ i ] ] = 0 then
aux[v[ i ]]:= v[ i ]
else
eh permutacao:= false
i := i + 1;
end;
testa permutacao:= eh permutacao;
end; (\u2217 testa permutacao \u2217)
Figura 10.27: Verifica linearmente se um vetor define uma permutac¸a\u2dco.
Outros estudantes sugeriram uma conjectura, na\u2dco provada em sala, de que, se
todos os elementos pertencem ao intervalo 1 \u2264 v[i] \u2264 n e \u2211ni=1 v[i] = n(n+1)2 e ao
mesmo tempo
\u220fn
i=1 v[i] = n!, enta\u2dco o vetor representa uma permutac¸a\u2dco. Tambe´m
na\u2dco encontramos contra-exemplo e o problema ficou em aberto.
Gerando permutac¸o\u2dces va´lidas
O pro´ximo problema e´ gerar aleatoriamente uma permutac¸a\u2dco. Para isto faremos
uso da func¸a\u2dco random da linguagem Pascal.
O primeiro algoritmo gera um vetor de maneira aleato´ria e depois testa se o vetor
produzido pode ser uma permutac¸a\u2dco usando o co´digo da func¸a\u2dco testa permutacao ja´
implementado. A tentativa e´ reaproveitar co´digo a qualquer custo. Este racioc´\u131nio
esta´ implementado no co´digo da figura 10.28.
Este algoritmo e´ absurdamente lento quando n cresce. Isto ocorre pois os vetores
sa\u2dco gerados e depois testados para ver se sa\u2dco va´lidos, mas, conforme esperado, e´
muito prova´vel que nu´meros repetidos sejam gerados em um vetor com grande nu´mero
de elementos. Um dos autores deste material teve pacie\u2c6ncia de esperar o co´digo
terminar apenas ate´ valores de n pro´ximos de 14. Para valores maiores o co´digo ficou
infernalmente demorado, levando va´rias horas de processamento.
Numa tentativa de melhorar o desempenho, o que implica em abrir ma\u2dco da como-
10.1. VETORES 155
procedure gerar permutacao1 (var v: vetor i ; var n: integer) ;
var i : integer ;
begin
read (n) ;
randomize