algoritmos e programação

Prévia do material em texto

s
é
r
ie
 liv
ro
s
 d
id
á
tic
o
s
 in
fo
r
m
á
tic
a
 u
fr
g
s
23
s é r i e l i v r o s d i d á t i c o s i n f o r m á t i c a u f r g s
volume 3 Linguagens Formais e Autômatos, 6.ed., 
de Paulo Blauth Menezes
volume 4 Projeto de Banco de Dados, 6.ed., 
de Carlos Alberto Heuser 
volume 5 Teoria da Computação: Máquinas Universais 
e Computabilidade, 3.ed, de Tiarajú Asmuz Diverio 
e Paulo Blauth Menezes
volume 6 Arquitetura de Computadores Pessoais, 
2.ed., de Raul Fernando Weber
volume 7 Concepção de Circuitos Integrados, 2.ed., 
de Ricardo Augusto da Luz Reis e cols.
volume 8 Fundamentos de Arquitetura de Computadores, 
4.ed., de Raul Fernando Weber
volume 10 Tabelas: Organização e Pesquisa, 
de Clesio Saraiva dos Santos e Paulo Alberto de Azeredo 
volume 11 Sistemas Operacionais, 4.ed., 
de Rômulo Silva de Oliveira, Alexandre da Silva Carissimi 
e Simão Sirineo Toscani 
volume 12 Teoria das Categorias para Ciência 
da Computação, 2.ed., de Paulo Blauth Menezes 
e Edward Hermann Haeusler
volume 13 Complexidade de Algoritmos, 3.ed., 
de Laira Vieira Toscani e Paulo A. S. Veloso 
volume 16 Matemática Discreta para Computação 
e Informática, 4.ed., de Paulo Blauth Menezes
volume 18 Estruturas de Dados, de Nina Edelweiss 
e Renata Galante
volume 19 Aprendendo Matemática Discreta com 
Exercícios, de Paulo Blauth Menezes, Laira Vieira Toscani 
e Javier García López
volume 20 Redes de Computadores, 
de Alexandre da Silva Carissimi, Juergen Rochol 
e Lisandro Zambenedetti Granville
volume 21 Introdução à Abstração de Dados, 
de Daltro José Nunes
volume 22 Comunicação de Dados, de Juergen Rochol
COMPUTAÇÃO
www.grupoa.com.br
A Bookman é um dos selos editoriais do Grupo A Educação, empresa que 
oferece soluções em conteúdo, tecnologia e serviços para a educação 
acadêmica e profissional.
algoritmos
e programação 
com exemplos em Pascal e C
nina edelweiss
maria aparecida castro livi
Material didático para professores
Visite www.grupoa.com.br
nina edelweiss
maria aparecida castro livi
 l i v r o s d i s p o n í v e i s
algoritm
os e program
ação
com
 exem
plos em
 P
ascal e C
23
edelw
eiss
livi
23
algoritmos
e programação 
com exemplos em Pascal e C
Aprender programação não é uma tarefa simples. 
Requer um entendimento perfeito do problema, a análise 
de como solucioná-lo e a escolha da forma de implementação 
da solução. algoritmos e programação apresenta 
o processo de construção de algoritmos e de programas, 
enfatizando as etapas de abstração, organização, análise 
e crítica na busca de soluções eficientes. Os elementos 
de um programa são introduzidos pouco a pouco ao longo 
do texto, inicialmente apresentados em pseudolinguagem e, 
em seguida, exemplificados nas linguagens de programação 
Pascal e C. Este é um livro-texto para disciplinas iniciais 
de programação de duração de um semestre. Pode ser 
utilizado sobretudo em cursos de bacharelado e licenciatura 
em ciência da computação, análise de sistemas e engenharia 
da computação. 
E22a Edelweiss, Nina.
 Algoritmos e programação com exemplos em Pascal e C 
 [recurso eletrônico] / Nina Edelweiss, Maria Aparecida Castro 
 Livi. – Dados eletrônicos. – Porto Alegre : Bookman, 2014.
 Editado também como livro impresso em 2014.
 ISBN 978-85-8260-190-7
 1. Informática. 2. Algoritmos – Programação. I. Livi, 
 Maria Aparecida Castro. II. Título. 
CDU 004.421
 as autoras
Nina Edelweiss é engenheira eletricista e doutora em Ciência da Computação pela Uni-
versidade Federal do Rio Grande do Sul. Durante muitos anos, lecionou em cursos de Enge-
nharia e de Ciência da Computação na UFRGS, na UFSC e na PUCRS. Foi, ainda, orientadora 
do Programa de Pós-Graduação em Ciência da Computação da UFRGS. É coautora de três 
livros, tendo publicado diversos artigos em periódicos e em anais de congressos nacionais 
e internacionais. Participou de diversos projetos de pesquisa financiados por agências de 
fomento como CNPq e FAPERGS, desenvolvendo pesquisas nas áreas de bancos de dados e 
desenvolvimento de software.
Maria Aparecida Castro Livi é licenciada e bacharel em Letras, e mestre em Ciência da 
Computação pela Universidade Federal do Rio Grande do Sul. Desenvolveu sua carreira pro-
fissional na UFRGS, onde foi programadora e analista de sistema, antes de ingressar na 
carreira docente. Ministrou por vários anos a disciplina de Algoritmos e Programação para 
alunos dos cursos de Engenharia da Computação e Ciência da Computação. Sua área de 
interesse prioritário é o ensino de Linguagens de Programação, tanto de forma presencial 
quanto a distância.
Catalogação na publicação: Ana Paula M. Magnus – CRB 10/2052
Edelweiss_Iniciais_eletronica.indd iiEdelweiss_Iniciais_eletronica.indd ii 14/05/14 16:5114/05/14 16:51
180 Algoritmos e Programação com Exemplos em Pascal e C
exercício 6.8 Classificação por seleção. Esse é um método de classificação bastante sim-
ples, embora não muito eficiente. Para colocar os dados em ordem crescente, percorre-se 
o vetor buscando o elemento com o menor valor. Esse é trocado com aquele que está na 
primeira posição do vetor. O método é, então, repetido para o segmento do vetor que inicia 
na segunda posição, e assim sucessivamente. A Figura 6.6 mostra esquematicamente como é 
feita a classificação por seleção.
Algoritmo ClassSeleção
{CLASSIFICA UM VETOR PELO MÉTODO DE SELEÇÃO, EM ORDEM CRESCENTE}
 Constantes: MIN = 1
 MAX = 10 {LIMITES DO VETOR}
 Entradas:
 vet (arranjo [MIN..MAX] de inteiro) {VETOR A SER ORDENADO}
 Saídas: {VETOR CLASSIFICADO EM ORDEM CRESCENTE}
 Variáveis auxiliares:
 i, j (inteiro) {ÍNDICES DE UMA PASSADA}
 menor (inteiro) {MENOR VALOR DA PASSADA}
 aux (inteiro) {AUXILIAR PARA FAZER A TROCA}
início
 para i de MIN incr 1 até MAX faça
 ler (vet[i]) {PREENCHE VET POR LEITURA}
 para i de MIN incr 1 até MAX-1 faça
 início
 menor ← i
 para j de i+1 incr 1 até MAX faça
 se vet[j] < vet[menor]
 então menor ← j
 se menor ≠ i
 então início {VAI FAZER A TROCA}
 aux ← vet[i]
 vet[i] ← vet[menor]
 vet[menor] ← aux
 fim
 fim
 para i de MIN incr 1 até MAX faça
 escrever (vet[i]) {MOSTRA VET ORDENADO}
fim
exercício 6.9 Método da Bolha. Trata-se de um método de classificação de vetores bem 
mais eficiente do que o método de classificação por seleção antes apresentado. Consiste em 
percorrer o vetor comparando cada dois elementos adjacentes e trocando-os de posição caso 
estejam em ordem contrária à desejada. É feito um controle, a cada varredura do vetor, para 
saber se houve alguma troca de valores e, se houve, nova varredura é executada. O ponto 
onde a última troca aconteceu é fixado como o limite da próxima varredura, reduzindo pro-
gressivamente o número de elementos do conjunto considerado na varredura. Se nenhuma 
Edelweiss_06.indd 180Edelweiss_06.indd 180 12/03/14 09:0212/03/14 09:02
Capítulo 6 Variáveis Estruturadas: Arranjos Unidimensionais 181
troca acontece durante uma varredura, então o conjunto já está ordenado e o processo é 
interrompido. Essa estratégia recebe o nome de “Método da Bolha” (bubble sort) ou “orde-
nação por flutuação”, pois os valores maiores (no caso de ordenação em ordem crescente) 
vão “subindo” para o final do vetor a cada varredura, até atingirem sua posição definitiva no 
conjunto de dados.
A Figura 6.7 simula o funcionamento desse método para um vetor de cinco elementos intei-
ros. São representados os valores contidos no vetor nas três primeiras varreduras. Na quarta 
varredura, não será necessário troca – isso indica que o vetor está ordenado. Observar que, ao 
final da primeira varredura, o maior valor (30) estará na posição final e que os valores meno-
res terão descido uma posição, aproximando-se de sua posição correta. Nasegunda varredura 
não é feita a comparação com o último valor, pois ele já está correto. Assim, a cada varredura 
diminui o tamanho do segmento de vetor a ser analisado.
O algoritmo apresentado a seguir classifica o vetor em ordem crescente. Se a ordena-
ção desejada for a decrescente, basta alterar a comparação de vet[i] > vet[i+1] para 
vet[i] < vet[i+1].
Algoritmo ClassBolha
{CLASSIFICA UM VETOR PELO MÉTODO DA BOLHA}
 Constante MAX = 5 {NÚMERO DE ELEMENTOS DO VETOR}
 Entradas:
 vet (arranjo [1..MAX] de inteiro) {VETOR A SER CLASSIFICADO}
 Saídas: {vet CLASSIFICADO}
 Variáveis auxiliares:
 i (inteiro) {ÍNDICE QUE PERCORRE O VETOR}
1 2 3 4 5
28 26 30 24 25
24 26 30 28 25
1 2 3 4 5
1 2 3 4 5
24 25 30 28 26
24 25 26 28 30
1 2 3 4 5
1 2 3 4 5
24 26 30 28 25
24 25 30 28 26
1 2 3 4 5
1 2 3 4 5
24 25 26 28 30
24 25 26 28 30
1 2 3 4 5
i=1
j=2 a 5 
i=2
j=3 a 5 
i=4
j=5 a 5 
i=3
j=4 a 5 
1ª iteração 2ª iteração
4ª iteração3ª iteração
figura 6.6 Classificação por seleção.
Edelweiss_06.indd 181Edelweiss_06.indd 181 12/03/14 09:0212/03/14 09:02
182 Algoritmos e Programação com Exemplos em Pascal e C
 k (inteiro) {AO TERMINAR A VARREDURA, ARMAZENA A POSIÇÃO
 ONDE OCORREU A ÚLTIMA TROCA}
 m (inteiro) {LIMITE SUPERIOR DA VARREDURA –
 RECUA UMA OU MAIS POSIÇÕES A CADA ITERAÇÃO}
 aux (inteiro) {VARIÁVEL AUXILIAR UTILIZADA PARA A TROCA}
 trocou (lógico) {VERDADEIRA SE OCORREU ALGUMA TROCA}
início
 para i de 1 incr 1 até MAX faça
 ler (vet[i]) {PREENCHIMENTO DO VETOR POR LEITURA}
 trocou ← verdadeiro {INICIALIZA trocou EM VERDADEIRO}
 m ← (MAX – 1) {INICIALIZA m NA PENÚLTIMA POSIÇÃO DO VETOR}
 k ← 1 {INICIALIZA k NO PRIMEIRO ELEMENTO DO VETOR}
 enquanto trocou {REPETE ENQUANTO HOUVER ALGUMA TROCA}
 início
 trocou ← falso {INDICA QUE NESTA VARREDURA AINDA NÃO HOUVE TROCA}
 para i de 1 incr 1 até m faça
 se vet[i] > vet [i + 1] {COMPARA VALORES ADJACENTES}
 então início
 aux ← vet[i] {TROCA DOIS ELEMENTOS DE POSIÇÃO}
 vet[i] ← vet [i + 1]
 vet[i + 1] ← aux
28 26 30 24 25
1ª iteração
26 28 30 24 25
26 28 30 24 25
26 28 24 30 25
26 28 24 25 30
26 28 24 25 30
26 28 24 25 30
26 24 28 25 30
26 24 25 28 30
26 24 25 28 30
2ª iteração
3ª iteração
24 26 25 28 30
24 25 26 28 30
figura 6.7 Classificação por meio do Método da Bolha.
Edelweiss_06.indd 182Edelweiss_06.indd 182 12/03/14 09:0212/03/14 09:02
Capítulo 6 Variáveis Estruturadas: Arranjos Unidimensionais 183
 k ← i {k POSIÇÃO EM QUE OCORREU A TROCA}
 trocou ← verdadeiro; {INDICA QUE NESTA VARREDURA HOUVE
 TROCA}
 fim
 m ← k {m INDICA ATÉ ONDE SERÁ FEITA A PRÓXIMA VARREDURA}
 fim {ENQUANTO}
 escrever ('Vetor classificado');
 para i de 1 incr 1 até MAX faça
 escrever (vet[i]) {MOSTRA VETOR CLASSIFICADO}
fim
6.5 em Pascal
6.5.1 declaração de um vetor
Um tipo de dado vetor (arranjo de uma dimensão) é declarado em Pascal da seguinte forma:
array [<limite inferior>..<limite superior>] of <tipo>
Os limites superior e inferior, índices do primeiro e do último elemento do vetor, devem ser do 
tipo inteiro, caractere ou do tipo enumeração (que será apresentado no Capítulo 8). O 
tipo declarado no final será o tipo de todos os elementos do vetor.
Exemplo de declarações de vetores:
var
 nota: array [1..10] of real;
 nr_letras: array ['a'..'j'] of integer;
 caract: array [-4..7] of char;
Nesses exemplos, o vetor nota tem 10 elementos reais, com índices iniciando em 1 e crescen-
do até 10; o vetor nr_letras tem elementos inteiros, com índices do tipo caractere, tendo 
o primeiro elemento o índice “a” e o último o índice “j”; e o vetor caract, de elementos do 
tipo caractere, tem 12 elementos, tendo o primeiro o índice -4 e o último, 7. A Figura 6.8 
ilustra estes três vetores, simulando alguns valores contidos em seus elementos.
Quando os índices forem do tipo inteiro, recomenda-se que a declaração dos limites do 
vetor seja feita usando constantes previamente definidas. As duas declarações a seguir são 
equivalentes à declaração do vetor nota:
const LIMSUP = 10;
 LIMINF = 1;
var nota: array [LIMINF..LIMSUP] of real;
Nesse caso, todas as referências ao primeiro e último elemento do vetor ao longo do progra-
ma serão feitas utilizando as constantes declaradas. Dessa forma, o tamanho do vetor poderá 
Edelweiss_06.indd 183Edelweiss_06.indd 183 12/03/14 09:0212/03/14 09:02
Capítulo 15 Recursividade 427
A Figura 15.3 ilustra as chamadas recursivas realizadas para calcular o quinto termo dessa 
série.
exercício 15.3 Classificação de vetor pelo método Quicksort. No Capítulo 6 (Seção 
6.3.3), foi ressaltado que a classificação de um vetor é uma operação muito usual em apli-
cações e que há vários métodos disponíveis para realizá-la. Aqui, é apresentado um dos mé-
todos mais eficientes para classificar um vetor, denominado Quicksort ou ordenação rápida. 
Embora possa ser implementado somente por meio de comandos iterativos, a utilização de 
chamadas recursivas é recomendável, uma vez que a eficiência do método garante que o 
número de chamadas nunca seja elevado.
O método inicia buscando a posição correta do primeiro elemento do vetor (aqui chamado de 
pivô) e trocando-o para essa posição. Além de posicionar o pivô em seu lugar correto, todos 
os elementos antes dele serão menores do que ele e todos os posteriores, maiores do que ele. 
Isso é feito da seguinte maneira: o pivô é comparado com o segundo elemento, depois com 
o terceiro, etc., até que seja encontrado um (aqui nomeado de índice i) que seja maior do 
que ele. Em seguida, o pivô é comparado com o último elemento do vetor, depois com o pe-
núltimo, etc., até que seja encontrado um que seja menor do que ele (índice j). Os elementos 
de índices i e j são então permutados. Feita a troca, novamente o pivô é comparado com os 
elementos que seguem o elemento que estava em i, até que seja encontrado outro maior do 
que ele, depois com os elementos abaixo do j, até que seja encontrado outro menor do que 
ele, e nova permuta é feita. Esse processo é repetido até que i seja maior do que j, o que de-
fine o valor de j como a posição correta do pivô, que é então trocado com o elemento dessa 
posição. Uma vez posicionado o pivô, o vetor original está particionado em dois – no subvetor 
inferior, todos os elementos são menores do que o pivô e, no superior, todos são maiores. 
O mesmo método de ordenação é então repetido para cada um desses subvetores por meio 
de chamadas recursivas, passando, como parâmetros, os índices que limitam os subvetores.
Exemplificando, suponha um vetor de 9 elementos, numerados de 1 a 9, preenchido com os 
seguintes valores:
70 27 21 90 81 24 30 80 88
FIB (5)
FIB (3) + FIB (2)
FIB (2) + FIB (1)
FIB (2) + FIB (1)
FIB (4) + FIB (3)
figura 15.3 Chamadas recursivas para cálculo do quinto termo da série de Fibonacci.
Edelweiss_15.indd 427Edelweiss_15.indd 427 12/03/14 09:0012/03/14 09:00
428 Algoritmos e Programação com Exemplos em Pascal e C
A Figura 15.4 mostra resumidamente a sequência de valores no vetor durante a execução do 
método. Os índices i e j são utilizados para percorrer o vetor, o primeiro crescendo e o se-
gundo diminuindo. O pivô é o primeiro elemento, com valor 70. Quando i=4 e j=30, é feita a 
primeira permuta de valores, entre 90 e 30. A permuta seguinte acontece quando i=5 e j=6, 
sendo trocados de posição os valores 81 e 24. Quando i=6 e j=5, significa que foi encontra-
da a posição do pivô (posição 5), que é então permutado com o elemento dessa posição. Na 
figura, pode ser observado que agora todos os valores à esquerda de 70 são menores do que 
esse valor e todos os à direita dele são superiores a 70. Duas chamadas recursivas solicitam a 
ordenação do subvetor inferior, fornecendo os índices 1e 4 como seus limites, e do subvetor 
superior, com índices limites 6 e 9. Na figura podem ser observados os valores decorrentes das 
permutas durantes as chamadas recursivas.
O procedimento a seguir implementa a classificação pelo método Quicksort. O procedimento 
utiliza o vetor V, do tipo TipoVetorInteiros, com valores inteiros, e um outro procedi-
mento, chamado troca, que permuta os conteúdos (valores inteiros) entre duas posições de 
memória recebidas como parâmetros.
Procedimento Quick
{CLASSIFICA O VETOR V EM ORDEM CRESCENTE, PELO MÉTODO QUICKSORT}
 Parâmetros de entrada:
 ref V (TipoVetorInteiros) {VETOR OU SUBVETOR A SER CLASSIFICADO}
 li, ls (inteiro) {LIMITES INFERIOR E SUPERIOR DOS ÍNDICES}
 Variáveis locais:
 i, j (inteiro) {ÍNDICES UTILIZADOS PARA PERCORRER O VETOR}
 pivô (inteiro) {VALOR CONTIDO NO PRIMEIRO ELEMENTO CONSIDERADO}
 sinal (lógico) {INDICA FINAL DE UMA VARREDURA}
início
24 27 21 30 70 81 90 80 88
Quick (V, 1, 4) Quick (V, 6, 9) 
24 27 21 30 81 90 80 88
24 21 27 30 81 80 90 88
21 24 27 30 80 81 90 88
21 27 30 80 88 90
i
70 27 21 90 81 24 30 80 88
70 27 21 30 81 24 90 80 88
70 27 21 30 24 81 90 80 88
j
j
i
i j
ij
figura 15.4 Simulação de valores no Quicksort.
Edelweiss_15.indd 428Edelweiss_15.indd 428 12/03/14 09:0012/03/14 09:00
Capítulo 15 Recursividade 429
 sinal ← falso {INICIALIZAÇÃO}
 se li < ls
 então início
 i ← li {POSICIONA I E J NO INÍCIO E NO FINAL}
 j ← ls + 1
 pivô ← v[li]
 repita
 i ← i + 1
 {AVANÇA I ENQUANTO O ELEMENTO FOR INFERIOR AO PIVÔ
 E NÃO CHEGAR AO FINAL DO SEGMENTO ANALISADO}
 enquanto (v[i]<pivô) e (i<ls)
 faça i ← i + 1
 j ← j – 1
 {RECUA J ENQUANTO O ELEMENTO FOR SUPERIOR AO PIVÔ
 E NÃO CHEGAR AO INÍCIO DO SEGMENTO ANALISADO}
 enquanto (v[j]>pivô) e (j>li)
 faça j ← j – 1
 se i < j {PERMUTA DOIS ELEMENTOS}
 então executar troca(v[i], v[j])
 senão sinal ← verdadeiro {INDICA QUE TERMINOU}
 até sinal
 executar troca(v[j], v[li]) {POSICIONA PIVÔ EM SUA POSIÇÃO}
 executar Quick(v, li, j-1)
 executar Quick(v, j+1, ls)
 fim
fim {Quick}
exercício 15.4 Pesquisa binária recursiva. No Exercício de Fixação 6.7 (no Capítulo 6), 
foi visto o método de pesquisa conhecido como pesquisa binária. Relembrando, esse méto-
do realiza a busca de um valor sobre um vetor já ordenado, comparando o valor buscado 
com o elemento que está na posição central do vetor. Se o valor não for encontrado nessa 
posição, a pesquisa segue buscando o valor na metade superior (caso o valor buscado seja 
superior ao valor que está no meio) ou na metade inferior (caso seja inferior ao valor do 
meio). Claramente, esse método pode ser implementado por meio de recursividade, pois a 
pesquisa na metade superior ou inferior é feita novamente da mesma maneira, alterando 
somente o tamanho do vetor analisado, ou seja, fazendo a chamada recursiva para a metade 
superior ou para a inferior.
A função a seguir realiza a pesquisa binária utilizando chamadas recursivas. Além do nome 
do vetor e do valor a ser pesquisado, são passados como parâmetros os índices que limitam o 
espaço do vetor a ser pesquisado. A função devolve o índice do elemento em que foi encon-
trado o valor buscado ou, no caso de não encontrá-lo, o valor -1 (supondo que esse índice 
não seja utilizado no vetor original).
Edelweiss_15.indd 429Edelweiss_15.indd 429 12/03/14 09:0012/03/14 09:00
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.