A maior rede de estudos do Brasil

Grátis
146 pág.
Programando com PASCAL - Jaime Evaristo

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

sucessivamente 8, 7, 5, 2 e 1 e realizando as seguintes atribuições:
1. Aux = {, , , , 8}
v = {5, 2, 7, 1, -1}
2. Aux = { , , , 7, 8}
v = {5, 2, -1, 1, -1}
3. Aux = { , , 5, 7, 8}
v = {-1, 2, -1, 1, -1}
4. Aux = { , 2, 5, 7, 8}
v = {-1, -1, -1, 1, -1}
5. Aux = {1, 2, 5, 7, 8}
v = {-1, -1, -1, -1, -1},
Para finalizar, basta armazenar nas componentes de v as componentes de Aux, o que pode ser feito 
através de uma atribuição "global" v := Aux.
{Procedimento que retorna o maior valor de uma relacao e a posicao deste maior valor}
procedure MaiorElemento (var v : TVetor; t : integer; var Maior : integer; var p : integer);
var i : integer;
begin
Maior := v[1];
p := 1;
for i := 1 to t do
if v[i] > Maior
then
begin
Maior := v[i];
p := i;
end;
end;
procedure SelectSort(var v : TVetor; t : integer);
var i, j, k : integer;
Aux : TVetor;
begin
j := t;
for i := 1 to t do
begin
MaiorElementoPos(v, t, Aux[j], k);
v[k] := -1;
j := j - 1;
end;
v := Aux;
end;
Observe a importância da utilização da segunda versão do procedimento MaiorElemento discutido no 
exemplo 2 da seção 6.5. Como o parâmetro Maior é passado por referência, o procedimento já armazena no 
vetor Aux os maiores elementos de v, nas suas posições definitivas.
9.2.2 O BubbleSort
O algoritmo BubbleSort consiste em se percorrer o vetor a ser ordenado várias vezes, comparando-se 
cada elemento com o seguinte, permutando suas posições se eles não estiverem na ordem pretendida. Assim, 
cada vez que o vetor é percorrido, o maior elemento (ou o menor, se a ordenação for feita em ordem 
decrescente) ainda não ordenado, é colocado na sua posição de ordenação definitiva. Naturalmente, o vetor 
será percorrido até que não haja mais trocas a se fazer, quando então ele estará ordenado. Por exemplo, se o 
vetor a ser ordenado em ordem crescente fosse v = {5, 1, 9, 3, 7, 2}, teríamos as seguintes configurações para 
v, de acordo com a ordem de percurso:
Percurso v
0 {5, 1, 9, 3, 7, 2}
1 {1, 5, 9, 3, 7, 2}
{1, 5, 3, 9, 7, 2}
{1, 5, 3, 7, 9, 2}
{1, 5, 3, 7, 2, 9}
2 {1, 3, 5, 7, 2, 9}
{1, 3, 5, 2, 7, 9}
3 {1, 3, 2, 5, 7, 9}
4 {1, 2, 3, 5, 7, 9}
procedure BubbleSort(var v : TVetor; t : integer);
var Tr : boolean;
 i, j : integer;
{Procedimento para permutar os conteudos de duas variaveis}
procedure Troca(var x, y : integer);
begin
x := x + y;
y := x - y;
x := x - y;
end;
begin
Tr := true;
while Tr do
begin
Tr := false;
t := t - 1;
for i := 1 to t do
if v[i] > v[i+1]
then
begin
Troca(v[i], v[i+1]);
Tr := true;
end;
end;
end;
Observe que a variável Tr verifica se houve alguma troca para que outro percurso seja realizado. 
Observe também que o comando t := t – 1 se justifica pelo fato de que no percurso de ordem i, i – 1 
elementos já estão em suas posições definitivas.
9.3 Exercícios propostos
1. A maioria das pessoas acha que são azaradas quando procuram uma ficha numa pilha, sempre tendo 
receio que a ficha procurada seja uma das últimas da pilha. Uma pessoa que acredite ser assim azarada pode 
pesquisar a tal ficha pesquisando, sucessivamente, a parte superior e a parte inferior da pilha. Assim, verifica 
a primeira ficha, em seguida, a última, em seguida, a segunda ficha, em seguida, a penúltima e assim 
sucessivamente. Escreva um procedimento que implemente este método de pesquisa.
2. Uma versão melhorada do SelectSort para um vetor que possui i componentes consiste em se comparar 
a maior dentre as i - 1 primeiras componentes com a última componente, permutando-se suas posições se 
aquela maior componente for menor do que esta última componente. Desta forma, coloca-se o maior 
elemento na posição desejada. Este raciocínio é repetido no vetor das i - 1 primeiras componentes e assim 
sucessivamente. Escreva um procedimento que implemente esta versão do SelectSort.
3. O algoritmo InsertSort para ordenação de um vetor Vet consiste em se tomar um vetor auxiliar Aux, 
contendo uma única componente Vet[1] e, em seguida, inserem-se as demais componentes de Vet, uma a 
uma, em Aux, de modo que Aux se mantenha ordenado, como solicitado no exercício 10 da seção 6.9. 
Escreva um procedimento que implemente o InsertSort.
4. Escreva um procedimento que ordene um arquivo, cujos registros têm os campos char Cpf[12] e char 
Nome[40], em relação ao campo Cpf.
Observação
Para receber as respostas dos exercícios propostos, encaminhe mensagem para jaime@ccen.ufal.br, 
assunto RESPOSTAS EXERCÍCIOS PASCAL, contendo NOME, INSTITUIÇÃO (se for o caso), 
CIDADE/ESTADO e CATEGORIA (docente, estudante ou auto-didata).
Capítulo 10 Tipos de Dados Definidos pelo Usuário e 
Conjuntos
10.1 O que são tipos de dados definidos pelo usuário
Além dos tipos de dados predefinidos, os sistemas que implementam Pascal permitem que o 
programador defina novos tipos de dados, que podem ser usados para facilitar a legibilidade e a manutenção 
do programa. Infelizmente, a aplicação destes tipos é limitada em função de que variáveis de tipos definidos 
pelo usuário, com algumas exceções, não podem ser "lidas" nem "escritas". Isto significa, por exemplo, que 
o armazenamento de valores em variáveis deste tipo só podem ser realizadas através da utilização de 
comandos de atribuição.
10.2 O tipo discreto
Um tipo discreto (ou tipo enumerado) é um conjunto de identificadores declarado com a seguinte 
sintaxe:
type Identificador = (Ident1, Ident2,...,IdentN);
Por exemplo, um programa que manipule datas e que pretendesse associar nomes aos dias da semana e 
aos meses poderia ter definições dos seguintes tipos:
type TDia = (dom, seg, ter, qua, qui, sex, sab);
 TMes = (jan, fev, mar, abr, mai, jun, jul, ago, set, out, nov, dez);
A partir daí pode-se declarar variáveis destes tipos, as quais só podem receber atribuições daqueles 
identificadores. Por exemplo, poderíamos efetuar declarações do tipo:
var Dia : TDia;
 Mes : meses;
e atribuições como
Dia := dom; 
Mes := fev, etc.
Vale observar que um tipo discreto é um tipo ordenado com ordenação definida pela própria colocação 
dos identificadores na definição do tipo. Sendo ordenado, uma variável de um tipo discreto pode ser 
argumento das funções Succ e Pred definidas na seção 2.10 e podem ser operandos de operadores 
relacionais. No exemplo anterior, temos Succ(seg) = ter, Pred(jul) = jun, seg < ter, nov > abr, etc.. É claro 
que nem todo valor da variável pode ser argumento daquelas funções: sab não pode ser argumento de Succ 
nem jan pode ser argumento de Pred.
Um tipo discreto também pode ser usado como limites de um comando for ou do conjunto de índices de 
um vetor. Por exemplo, poderíamos, ainda com o exemplo anterior, ter uma declaração do tipo
var Faturamento : array[dom..sab] of real;
e um comando do tipo
for Mes := mar to ago do; 
10.3 O tipo faixa 
Outro tipo de dado que pode ser definido pelo usuário é chamado tipo faixa, cuja definição é feita 
através da seguinte sintaxe:
type Identificador = vi..vf;.
onde vi e vf são constantes de um tipo de dado ordenado, chamado tipo básico, com vi < vf. Como um tipo 
discreto é um tipo ordenado, ele pode ser tipo básico de um tipo faixa. Assim, com o exemplo anterior, 
poderíamos ter os seguintes tipos:
type TDiasUteis = seg..sex
 TInverno = jun..ago;
Neste caso, se declarássemos uma variável DiaDeTrabalho do tipo TDiasUteis, poderíamos atribuir-lhe 
qualquer um dos valores seg, ter, qua, qui, sex ou sab.
Se o tipo básico é integer ou char, uma variável de um tipo faixa pode ser "lida" através do comando 
readln e "escrita" através do comando write. Na hipótese de se pretender que a execução de um comando 
readln com a entrada de um