Exercícios para
Fundamentos da Programação
Utilizando Múltiplos Paradigmas
Pedro Adão, Fausto Almeida, Ana Cardoso-Cachopo, Pedro Amaro de Matos (editores)
Departamento de Engenharia Informática
Instituto Superior Técnico
Universidade Técnica de Lisboa
2
3
Preâmbulo
O objectivo desta publicação é disponibilizar um conjunto de exercícios que permitam aos alunos da disciplina de Fundamentos de Programação da Licenciatura em Engenharia Informática
e de Computadores do Instituto Superior Técnico consolidarem os conhecimentos adquiridos
ao longo do semestre.
Os exercícios estão divididos de acordo com os capítulos do livro adoptado na disciplina:
“Fundamentos da Programação Utilizando Múltiplos Paradigmas”, de João Pavão Martins e
Maria dos Remédios Cravo, editado pela IST Press em 2011. Sempre que tal foi considerado
relevante, os exercícios foram subdivididos de acordo com o seu tipo.
Chama-se a atenção dos alunos para a indicação do nível de dificuldade de 1 a 4, correspondendo o nível 1 a exercícios muito fáceis e o nível 4 a exercícios francamente difíceis. Esta
informação é apresentada dentro de um quadrado cinzento antes do enunciado do exercício a
que diz respeito.
Alguns destes exercícios correspondem a exercícios propostos nas sebentas (a) Exercícios da
cadeira de Introdução à Programação, Cláudia Antunes, Ana Cardoso Cachopo, João Cachopo,
Francisco Couto, António Leitão, Inês Lynce, César Pimentel e H. Sofia Pinto, editados por
Inês Lynce, 2002, e (b) Exercícios para Programação em Scheme: Introdução à Programação
Utilizando Múltiplos Paradigmas, Departamento de Engenharia Informática, IST.
4
Conteúdo
1 Noções básicas
1.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Abstracção Procedimental
2.1 Exercícios de revisão . . . . . . . . . .
2.2 Exercícios de programação . . . . . . .
2.2.1 Avaliação de Expressões . . . .
2.2.2 Definição de Procedimentos . .
2.2.3 Recursão . . . . . . . . . . . .
2.2.4 Valores aproximados de funções
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
8
11
11
11
11
13
18
23
3 Processos gerados por procedimentos
25
3.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Estruturação de Procedimentos
4.1 Exercícios de revisão . . . . . . . .
4.2 Exercícios de programação . . . . .
4.2.1 Estrutura de Blocos . . . .
4.2.2 Utilização de Nomes Locais
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
37
37
37
39
5 Abstracção de dados
5.1 Exercícios de revisão . . .
5.2 Exercícios de programação
5.2.1 Caixas e ponteiros
5.2.2 Tipo tempo . . . .
5.2.3 Tipo data . . . . .
5.2.4 Complexos . . . .
5.2.5 Listas . . . . . . .
5.2.6 Árvores Binárias .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
43
44
44
44
45
46
48
55
.
.
.
.
65
65
65
65
71
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Procedimentos de ordem superior
6.1 Exercícios de revisão . . . . . . . . . . . . . . . . . .
6.2 Exercícios de programação . . . . . . . . . . . . . . .
6.2.1 Procedimentos que recebem procedimentos .
6.2.2 Procedimentos que produzem procedimentos .
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
CONTEÚDO
7 O desenvolvimento de programas
77
7.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Capítulo 1
Noções básicas
1.1
Exercícios de revisão
1. O que é um processo computacional? Qual a relação entre um programa e um processo
computacional?
2. O que é um algoritmo? Explique cada uma das suas características: rigor, eficácia e
garantia de terminação.
3. O que é um programa? Qual a sua relação com um algoritmo?
4. O que é a abordagem do topo para a base? Aplique-a à solução de um problema à sua
escolha.
5. Em que consiste a abstracção? Qual a sua vantagem?
6. Explique em que consiste o ciclo “lê-avalia-escreve”.
7. O que são a sintaxe e a semântica de uma linguagem? Como se descrevem?
8. Dê um exemplo de cada um dos seguintes tipos de entidades existentes em Scheme:
(a) Constante.
(b) Procedimento primitivo.
(c) Combinação.
(d) Forma especial.
9. Diga o que é uma combinação, apresentando a sua sintaxe em notação BNF e explicando
informalmente os símbolos não terminais que a compõem.
10. Quais os passos seguidos pelo Scheme na avaliação de uma combinação?
11. O que é um predicado? Dê um exemplo.
12. O que é uma definição recursiva? Quais as partes que a compõem?
13. Considere a operação de nomeação em Scheme.
(a) Qual a sintaxe e a semântica da operação de nomeação?
7
8
CAPÍTULO 1. NOÇÕES BÁSICAS
(b) Explique a razão de esta operação corresponder a uma forma especial.
(c) Qual a necessidade da definição desta operação?
14. O que é um ambiente?
1.2
Exercícios de programação
1. (1) Instale o Scheme no seu computador seguindo as instruções do Manual de Sobrevivência em Scheme.
2. (1) Na janela de interacção do Scheme execute as seguintes acções:
(a) Avalie a constante inteira correspondente ao seu número de aluno.
(b) Avalie a cadeia de caracteres correspondente ao seu nome completo.
(c) Calcule a diferença entre 2007 e o seu ano de nascimento.
(d) Calcule a área de um círculo com diâmetro 10.
(e) Calcule a razão entre a área de um quadrado com 10 de lado e a área de um círculo
com diâmetro 10.
3. (1) Converta as seguintes expressões para a notação do Scheme:
(a) (1 + 5) ∗ 6 − 12/3
(b) 2 + 3 ∗ 4/5
(c) (8 + 7 ∗ 9/3 − 2) ∗ (8/4 − 9 + 3)
4. (2) Traduza as seguintes expressões para notação prefixa e calcule o seu valor utilizando
o interpretador do Scheme. Mostre a árvore de avaliação para cada uma delas utilizando
o modo de avaliação de expressões em Scheme.
(a) (5 + 4 ∗ 3)/(2 + 1)
(b) (5 + 4) ∗ 3/2 − 1
(c) 1 + 2 ∗ 3/4 − 5 ∗ 6/(7 + 8)
5. (1) Suponha que as seguintes expressões são avaliadas pelo Scheme. Na linha imediatamente a seguir a cada uma delas diga o que é escrito pelo interpretador do Scheme (se
a avaliação de alguma das expressões der origem a um erro, explique a razão do erro).
(a) (+ 1 20)
(b) (1 + 20)
6. (1) Considere uma máscara de papel feita a partir um círculo de papel de raio 5. Os
dois olhos são círculos de raio 1 recortados, o nariz é um quarto de círculo de raio 3
recortado e a boca corresponde a meio círculo de raio 3, também recortado. Escreva
uma expressão em Scheme para calcular a área ocupada pela máscara.
(a) Escreva o código em texto corrido usando os valores apropriados.
(b) Escreva o código usando a indentação elegante.
1.2. EXERCÍCIOS DE PROGRAMAÇÃO
9
(c) Escreva o código definindo nomes Raio-Face, Raio-Olhos, Raio-Nariz, Raio-Boca
para os raios dos círculos referidos.
(d) Escreva o código utilizando os nomes Area-Face, Area-Olhos, Area-Nariz, Area-Boca,
com os valores apropriados.
(e) Avalie cada uma das respostas das alíneas anteriores quanto à legibilidade do código.
7. (1) Suponha que as seguintes expressões são avaliadas pela ordem apresentada. Diga
o que é escrito pelo interpretador do Scheme. Se a avaliação de alguma das expressões
der origem a um erro, explique a razão do erro.
(a) (* 4 (+ 1 7.0))
(b) (define a 5)
(c) (+ a b)
(d) (define b (* (+ 5 a) (+ 2 56)))
(e) (+ a b)
(f) a
(g) (define a (+ a 2))
(h) a
(i) +
(j) 7.0
(k) (* 2 (/ 8 4))
(l) (+ 3 #f)
(m) (define a a)
(n) a
8. (1) Diga qual o resultado de avaliar cada uma das seguintes formas.
Se a avaliação de uma forma não produzir resultados escreva -nada-.
Se a avaliação de uma forma produzir um erro, explique a sua razão.
(a) (and (> 3 5) (/ 3 0))
(b) (and (/ 3 0) (> 3 5))
(c) (+ 8 (max 3 2))
(d) (define a 5)
10
CAPÍTULO 1. NOÇÕES BÁSICAS
Capítulo 2
Abstracção Procedimental
2.1
Exercícios de revisão
1. Diga qual a diferença entre uma função matemática e um procedimento em Scheme para
o cálculo dessa função.
2. Explique o que são os parâmetros formais e o que são os parâmetros concretos, referindo,
em particular onde aparecem os parâmetros formais e onde aparecem os parâmetros
concretos e quando e como é que os parâmetros formais são associados com os parâmetros
concretos.
3. Utilizando a notação BNF, apresente a definição de uma expressão lambda. Explique
cada um dos constituintes da sua definição.
4. O que é um procedimento anónimo? Dê um exemplo.
5. Diga o que é abstracção procedimental e qual a sua vantagem.
6. Escreva as regras seguidas pelo Scheme para a avaliação de uma expressão.
7. O que é um ambiente local? Qual o significado de dizer que um nome está ligado num
ambiente?
2.2
2.2.1
Exercícios de programação
Avaliação de Expressões
1. (1) Avalie as seguintes formas. Se alguma das avaliações der origem a um erro, explique
qual a razão do erro.
(a) (3 1)
(b) ((lambda (x) (+ 2 x)) 3)
(c) ((lambda (x) ((lambda (y) (* y 2)) (+ x 3))) 4)
(d) ((lambda (x) (+ x 3)) ((lambda (y) (* y 2)) 4))
12
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
2. (1) Diga qual o resultado de avaliar cada uma das seguintes formas. Considere que
estas são fornecidas ao avaliador do Scheme pela ordem apresentada (e consequentemente
cada forma é dependente das anteriores).
Se a avaliação de uma forma não produzir resultados escreva -nada-. Se a avaliação de
uma forma produzir um erro, explique a sua razão.
(a) (define a 5)
(b) (if (odd?
a) (+ a 2) (* a 3))
(c) (lambda (x) (+ b x))
(d) ((lambda (x)(+ a x)) b)
3. (1) Considere o procedimento
(define (cont n)
(if (< n 0)
0
(+ 2 (cont (- n 3)))))
Com base nas regras de avaliação, desenhe a árvore que representa o funcionamento
deste procedimento com a avaliação de (cont 5).
4. (1) Considere o procedimento
(define (proc n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ 3 (proc (- n 3))))))
Com base nas regras utilizadas pelo interpretador do Scheme para avaliar uma combinação, desenhe a árvore que representa o funcionamento deste procedimento com a
avaliação de (proc 3).
5. (1) Considere a seguinte interacção com o Scheme:
> (define (f x) (+ x 2))
> (define (g x) (* 2 (f x)))
> (define (h x) (f (* 2 x)))
> (g 3)
10
> (h 3)
8
Com base nas regras utilizadas pelo interpretador do Scheme para avaliar uma combinação, desenhe as árvores que representam o funcionamento destes procedimentos com
a avaliação de (g 3) e de (h 3).
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
13
6. (2) Repare que o nosso modelo de avaliação permite a existência de combinações cujos
operadores são expressões compostas. Use esta observação para descrever o comportamento do seguinte procedimento:1
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
7. (2) Considere a seguinte interacção em Scheme:
> (define (f1 x) (* x x))
> (f1 5)
25
> (define f2 f1)
(a) Qual o valor de (f2 5)? Justifique a sua resposta.
(b) Suponha que agora definia o procedimento f2, do seguinte modo:
> (define (f2 x) (+ x 10))
Quais os valores de (f1 5) e de (f2 5)? Justifique a sua resposta.
8. (2) Considere a seguinte definição:
(define f ((lambda (x) (lambda (y) x)) 1)).
Diga quais os resultados da avaliação sequencial das seguintes expressões. Se alguma
das expressões produzir um erro, explique a razão do erro.
(a) (f 2)
(b) (define g (f 3))
(c) (g 4)
(d) (define h f)
(e) (h 6)
2.2.2
Definição de Procedimentos
1. (1) Escreva um procedimento anónimo que soma dois ao seu argumento.
2. (1) Escreva um procedimento anónimo para representar a função de um argumento
(x) cujo valor é calculado por (x − 32) ∗ 5/9.
3. (1) Escreva um procedimento anónimo para representar a função de dois argumentos
(x e y) cujo valor é calculado por (x + 3 ∗ y) ∗ (x − y).
4. (1) Escreva o procedimento dobro que devolve o dobro do seu argumento.
1
Exercício 1.4 de Abelson H., Sussman G. J., e Sussman J., Structure and Interpretation of Computer
Programs, 2a Edição, p. 21, 1996.
14
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
5. (1) Escreva o procedimento metade que recebe um número inteiro positivo e devolve
um número racional que corresponde a metade do seu argumento.
6. (1) Escreva um procedimento horas->dias que recebe um inteiro correspondente a
um certo número de horas e que devolve um número real que traduz o número de dias
correspondentes ao seu argumento.
> (horas->dias 48)
2.0
> (horas->dias 10)
0.4166666666666667
7. (2) Escreva o procedimento digitos->numero que recebe como argumentos três dígitos
e produz o número inteiro de três algarismos constituído pelos seus argumentos e pela
ordem em que aparecem.
> (digitos->numero 3 2 8)
328
8. (1) Escreva um procedimento area-circulo que calcula a área de um círculo cujo raio
é r. Note-se que esta área é dada pela fórmula πr2 .
9. (2) Utilizando o procedimento area-circulo do exercício anterior, escreva um procedimento area-coroa que calcula a área de uma coroa circular de raio interior r1 e raio
exterior r2 .
10. (1) Defina o procedimento media que recebe dois argumentos que devem ser números
e devolve o número real que corresponde à média dos seus argumentos.
11. (1) Escreva um procedimento sinal, que receba um inteiro e devolva 1, −1 ou 0, caso
o número seja, respectivamente, maior, menor ou igual a zero.
12. (1) Escreva o procedimento intermedio que recebe três números e devolve o número
com o valor intermédio.
13. (3) Escreva um procedimento quant->qual, que recebe um real, representando uma
nota quantitativa de um aluno (entre 0 e 20), e a transforma numa constante do tipo
cadeia de caracteres que corresponde a uma nota qualitativa, de acordo com a tabela
Nota
quantitativa
18 a 20
14 a 17
10 a 13
5a9
0a4
Nota
qualitativa
Muito Bom
Bom
Suficiente
Mediocre
Mau
A nota recebida deverá ser convertida para um número inteiro, antes da conversão para
a nota qualitativa.
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
15
14. (1) Escreva um procedimento que recebe as notas de um aluno de uma disciplina C1
(nota do projecto, média dos trabalhos das práticas, nota do teste, e nota do exame
final) e calcula a sua nota final de acordo com as seguintes regras:
(a) A nota na disciplina será calculada por uma média ponderada da classificação
obtida nas provas realizadas, com os seguintes pesos: projecto – 25%; trabalhos de
casa e aulas práticas – 10%; teste – 20%; exame final – 45%.
(b) Para obter aprovação na disciplina, a nota do exame terá de ser superior a 7,5
valores, a nota do projecto terá de ser superior a 9,5 valores e a média ponderada
da disciplina terá de ser superior a 9,5 valores.
O seu procedimento deve devolver a nota final da disciplina (um inteiro) no caso de o
aluno ter sido aprovado ou zero no caso do aluno ter sido reprovado.
15. (1) Utilizando os procedimentos desenvolvidos nos exercícios 13 e 14, escreva um procedimento em Scheme que recebe as notas de um aluno da disciplina C1 (nota do projecto,
média dos trabalhos das práticas, nota do teste, e nota do exame final) e calcula a sua
nota qualitativa final.
16. (3) O procedimento primitivo round, quando a parte decimal do número a arredondar
é 0.5, arredonda por excesso ou por defeito (em termos de valor absoluto), consoante a
parte inteira seja ímpar ou par. Por exemplo,
> (round 5.5)
6.0
> (round 6.5)
6.0
Escreva um procedimento arredonda que arredonda sempre por excesso (em termos de
valor absoluto), quando a parte decimal do número é 0.5. Por exemplo,
> (arredonda 5.5)
6.0
> (arredonda 6.5)
7.0
> (arredonda -6.5)
-7.0
17. (2) Escreva um procedimento cinco? que tem o valor verdadeiro se o seu argumento
for 5 e falso no caso contrário. Não utilize o if, nem o cond, nem #t nem #f.
18. (2) Escreva um procedimento (entre? val x y) que devolve verdadeiro, no caso de
val se encontrar entre x e y (x < val < y) e falso no caso contrário.
19. (2) Escreva o procedimento bissexto? para verificar se um ano é bissexto. Um ano
é bissexto se for divisível por 4 e não for divisível por 100, a não ser que seja também
divisível por 400. Por exemplo, 1984 é bissexto, 1100 não é, e 2000 é bissexto.
16
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
> (bissexto? 2000)
#t
> (bissexto? 1900)
#f
20. (2) Escreva o procedimento data-valida? para verificar se uma data é válida. O seu
procedimento deve receber 3 inteiros, em que o primeiro representa o ano, o segundo, o
mês, e o terceiro, o dia, e verificar se a data correspondente existe no calendário. Por
exemplo, 1998 2 29 e 1945 4 31 não são datas válidas (porque 1998 não é bissexto e Abril
só tem 30 dias, respectivamente) mas 2000 2 29 é uma data válida.
> (data-valida? 31 1 2000)
#t
> (data-valida? 29 2 1900)
#f
> (data-valida? 31 4 2000)
#f
21. (2) Se a, b e c representam as dimensões dos lados de um triângulo, escreva um procedimento triangulo? que devolve verdadeiro se os valores de a, b e c puderem corresponder
a lados de um triângulo e falso no caso contrário. Note que a, b e c podem representar as
dimensões dos lados de um triângulo se: (a) nenhum dos valores a, b e c for negativo ou
nulo; (b) a soma de quaisquer destes valores for maior do que o terceiro (num triângulo,
qualquer lado é menor do que a soma dos outros dois).
22. (2) Escreva o procedimento classifica que recebe três números correspondentes aos
comprimentos dos lados de um triângulo e decide se o triângulo é equilátero, isósceles
ou escaleno.
23. (2) Escreva um procedimento triangulo-rect?, que recebe três números inteiros positivos e determina se estes correspondem aos comprimentos dos lados de um triângulo
rectângulo.
O seu procedimento deverá satisfazer as seguintes condições:
• O procedimento devolve verdadeiro no caso dos valores recebidos corresponderem
aos comprimentos dos lados de um triângulo rectângulo e falso em caso contrário.
• O funcionamento do procedimento é independente da ordem pela qual os valores
lhe são fornecidos.
• O procedimento verifica se os valores fornecidos e correspondem a inteiros positivos,
produzindo uma mensagem em caso de não corresponderem.
Note que num triângulo rectângulo, o quadrado de um dos lados é igual à soma dos
quadrados dos outros dois.
24. (2) Escreva o procedimento idade que recebe como argumentos seis números inteiros
correspondentes a duas datas (um dia, mês, ano para cada data), sendo a primeira data
correspondente à data de nascimento de uma pessoa e a segunda correspondente a uma
data posterior, e devolve a idade (número de anos) dessa pessoa na segunda data.
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
17
> (idade 3 3 1990 28 9 2011)
21
> (idade 3 3 1990 3 2 2011)
20
25. (3) Escreva o procedimento anterior? que recebe como argumentos seis números
inteiros correspondentes a duas datas (um dia, mês, ano para cada data) e devolve
verdadeiro se a primeira data for anterior à segunda e falso caso contrário. Não utilize
o if, nem o cond, nem #t nem #f.
> (anterior? 1 12 2010 1 1 2011)
#t
> (anterior? 31 12 2010 1 12 2010)
#f
26. (2) Escreva o procedimento dias-p/-reveillon que recebe como argumentos dois
números inteiros correspondentes a um mês e um ano e que devolve o número de dias
desde o dia 1 do mês dado até ao final desse ano.
27. (3) Escreva um procedimento dias-entre-datas que recebe seis números inteiros como
argumentos correspondentes a duas datas (um dia, mês e ano para cada data), sendo
a primeira data anterior à segunda e o período que decorre entre as datas não superior
a um ano, e devolve o número de dias depois da primeira data até à segunda data
(inclusive).
(dias-entre-datas 1 12 2010 1 1 2011)
31
(dias-entre-datas 1 12 2010 1 12 2011)
365
28. (3) Escreva o procedimento proximo-29/2 que recebe como argumentos três números
inteiros correspondentes a uma data (um dia, mês e ano) e devolve o ano da próxima
ocorrência do dia 29 de Fevereiro depois da data recebida como argumento.
Sugestão: Use o procedimento bissexto? definido na alínea 19.
> (proximo-29/2 29 1 2000)
2000
> (proximo-29/2 29 3 2000)
2004
> (proximo-29/2 29 1 1900)
1904
29. (3) Escreva o procedimento numero-de-29/2s que recebe como argumentos seis números inteiros correspondentes a duas datas (um dia, mês, ano para cada data), sendo
a primeira data anterior à segunda, e devolve o número de ocorrências do dia 29 de
Fevereiro depois da primeira data e até à segunda (inclusive).
Sugestão: Use o procedimento proximo-29/2 definido na alínea 28.
18
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
30. (3) Escreva o procedimento dias que recebe como argumentos seis números inteiros
correspondentes a duas datas (um dia, mês, ano para cada data), sendo a primeira data
anterior à segunda, e devolve o número de dias depois da primeira data e até à segunda
(inclusive).
Sugestão: Use os procedimentos definidos anteriormente.
2.2.3
Recursão
1. Suponha que em Scheme não existiam as operações aritméticas +, -, *, /, quotient e
remainder nem os predicados <, >, =, odd? e even? mas que existem os procedimentos
add1, sub1 e zero? que recebem como argumento um inteiro e devolvem, respectivamente, o seu sucessor, o seu antecessor, e o resultado de verificar se o número é 0.
Neste exercício apenas poderá utilizar estas 3 operações e outras eventualmente definidas
utilizando estas.
(a) (1) Escreva um procedimento soma que recebe dois números inteiros positivos n
e m, e devolve a soma dos dois.
Sugestão: A soma de dois números n e m pode ser vista como n + 1 + · · · + 1,
m vezes.
> (soma 8 2)
10
(b) (1) Escreva um procedimento multiplica que recebe dois números inteiros positivos n e m, e devolve a multiplicação dos dois.
Sugestão: A multiplicação de dois números n e m pode ser vista como n + n +
· · · + n, m vezes.
> (multiplica 8 2)
16
(c) (1) Escreva um procedimento menos que recebe dois números inteiros positivos n
e m, e devolve a diferença dos dois.
Sugestão: Use uma ideia semelhante ao exercício 1a.
> (menos 8 2)
6
> (menos 2 8)
-6
(d) (2) Escreva um procedimento par? que recebe um número inteiro positivo n, e
devolve #t se n for par e #f no caso contrário.
> (par? 8)
#t
> (par? 5)
#f
(e) (2) Suponha definido um procedimento menor? que recebe dois números inteiros
positivos n e m, e devolve #t se o n for menor do que m e #f no caso contrário.
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
19
Escreva um procedimento quociente que recebe dois números inteiros positivos n
e m, e devolve o quociente da divisão de n por m. No caso de m ser 0 deverá dar um
erro.
Relembre que o quociente da divisão de dois números inteiros positivos n e m é o
maior inteiro r tal que r.m ≤ n.
Sugestão: Utilize o procedimento menos definido anteriormente.
> (quociente 8 2)
4
> (quociente 10 3)
3
2. (1) Escreva um procedimento somatorio que recebe um número inteiro positivo n, e
devolve a soma de todos os números até n.
> (somatorio 3)
6
> (somatorio 6)
21
3. (1) Escreva um procedimento soma-quadrados que recebe um número inteiro positivo
n, e devolve a soma do quadrado de todos os números até n.
> (soma-quadrados 3)
14
> (soma-quadrados 5)
55
4. (1) Escreva um procedimento factorial que recebe um número inteiro positivo n, e
devolve o factorial desse número.
> (factorial 0)
1
> (factorial 5)
120
5. (1) Escreva um procedimento potencia que recebe dois números inteiros positivos b e
n, e devolve a potência n de b, i.e., bn . Neste exercício não pode usar o procedimento
expt.
> (potencia 3 2)
9
> (potencia 2 4)
16
6. (2) Um número d é divisor de n se o resto da divisão de n por d for 0. Escreva um
procedimento numero-divisores que recebe um número inteiro positivo n, e devolve o
número de divisores de n. No caso de n ser 0 deverá devolver 0.
20
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
> (numero-divisores 20)
6
> (numero-divisores 13)
2
7. (2) Suponha definido um procedimento primo? que recebe um número inteiro positivo
n, e devolve #t se o número for primo e #f no caso contrário.
Escreva um procedimento numero-primos-menores que recebe um número inteiro positivo n, e devolve o número de primos menores ou iguais a n.
> (numero-primos-menores 9)
4
> (numero-primos-menores 23)
9
8. (2) Suponha definido um procedimento primo? que recebe um número inteiro positivo
n, e devolve #t se o número for primo e #f no caso contrário.
Escreva um procedimento numero-divisores-primos que recebe um número inteiro
positivo n, e devolve o número de divisores primos de n. No caso de n ser 0 deverá
devolver 0.
> (numero-divisores-primos 1)
0
> (numero-divisores-primos 20)
2
> (numero-divisores-primos 30)
3
9. (2) Escreva um procedimento soma-divisores que recebe um número inteiro positivo
n, e devolve a soma de todos os divisores de n. No caso de n ser 0 deverá devolver 0.
> (soma-divisores 20)
42
> (soma-divisores 13)
14
10. (3) O logaritmo inteiro de um número n na base b é o maior número inteiro e tal que
be ≤ n. Escreva um procedimento logaritmo que recebe dois números inteiros positivos
n e b, e devolve o logaritmo inteiro de n na base b. No caso de n ou b serem 0 deverá
devolver 0.
> (logaritmo 8 2)
3
> (logaritmo 7 2)
2
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
21
11. (3) A raiz inteira de índice e de um número n é o maior número inteiro r tal que
re ≤ n. Escreva um procedimento raiz que recebe dois números inteiros positivos n e
e, e devolve a raiz inteira de n de índice e. No caso de e ser 0 deverá devolver 0.
> (raiz 8 3)
2
> (raiz 15 2)
3
12. (4) Suponha definido um procedimento kesimo-factor-primo que recebe dois números
inteiros positivos n e k, e devolve o seu k-ésimo factor primo de n.
Escreva um procedimento kesimo-expoente que recebe dois números inteiros positivos
n e k, e devolve o expoente do k-ésimo factor primo de n. No caso de n ter menos de k
factores primos ou k ser 0, deverá devolver 0.
> (kesimo-expoente 72 1)
3
> (kesimo-expoente 72 2)
2
Nos exercícios que se seguem poderá ser útil a utilização dos seguintes procedimentos
sobre números inteiros:
• (remainder n m) devolve o resto da divisão de n por m.
• (quotient n m) devolve o quociente da divisão de n por m.
13. (3) Escreva um procedimento numero-digitos que recebe um número inteiro positivo
n, e devolve o número de dígitos de n.
> (numero-digitos 9)
1
> (numero-digitos 1012)
4
14. (3) Escreva um procedimento soma-digitos que recebe um número inteiro positivo n,
e devolve a soma de todos os dígitos de n.
> (soma-digitos 9)
9
> (soma-digitos 1012)
4
15. (3) Escreva um procedimento soma-digitos-pares que recebe um número inteiro
positivo n, e devolve a soma de todos os dígitos pares de n.
> (soma-digitos-pares 9)
0
> (soma-digitos-pares 1412)
6
22
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
16. (4) Escreva um procedimento digitos-impares que recebe um número inteiro positivo
n, e devolve o número composto apenas pelos dígitos ímpares de n ou 0, se n não tiver
dígitos ímpares.
> (digitos-impares 94558)
955
> (digitos-impares 2468)
0
17. (4) Escreva um procedimento muda-digito que recebe três números inteiros positivos
n, k e d, e devolve o inteiro que resulta de substituir o dígito na posição k de n por d.
> (muda-digito 12345 2 8)
12385
> (muda-digito 12345 7 8)
80012345
18. (4) O espelho de um número inteiro positivo é o resultado de inverter a ordem de todos
os seus algarismos. Escreva um procedimento espelho que recebe um número inteiro
positivo n, e devolve o seu espelho.
> (espelho 391)
139
> (espelho 45679)
97654
19. (4) Um número binário bn bn−1 . . . b1 b0 pode ser transformado num número decimal
P
usando a seguinte formula ni=0 bi 2i . Escreva um procedimento binario-decimal que
recebe um número b escrito em binário e devolve a sua representação decimal.
> (binario-decimal 1001)
9
> (binario-decimal 10000)
16
20. (4) Um número decimal d pode ser transformado num número binário bn bn−1 . . . b1 b0
através da seguinte recorrência: seja q0 = d e qi = quociente(qi−1 , 2) para i > 0, e
bi = resto(qi , 2). Escreva um procedimento decimal-binario que recebe um número d
escrito em base 10 e devolve a sua representação binária.
> (decimal-binario 33)
100001
> (decimal-binario 156)
10011100
2.2. EXERCÍCIOS DE PROGRAMAÇÃO
2.2.4
23
Valores aproximados de funções
1. (2) Sabe-se que a seguinte fórmula permite calcular uma aproximação da função seno
até um determinado número de termos:
x2
x2
x2
(1 −
(1 −
(· · · ))))
2·3
4·5
6·7
Defina um procedimento seno que corresponde ao método de cálculo anterior. O seu
procedimento deverá receber o número para o qual se pretende calcular o seno e o número
de factores a considerar.
seno(x) = x(1 −
2. (2) A função arctg pode ser aproximada através da fórmula
arctg(z) =
∞
X
(−1)n z 2n+1
n=0
2n + 1
=z−
z3 z5 z7
+
−
+ ...
3
5
7
Defina um procedimento que calcule o arctg de acordo com a fórmula acima. O seu
procedimento deverá receber o número z para o qual se quer calcular o arctg bem como
o número de termos da expressão a calcular.
3. (3) Suponha que o procedimento sqrt não estava definido em Scheme como um procedimento primitivo.
A raiz quadrada de um número, x, pode ser calculada usando um método de aproxima√
ções sucessivas, chamado método de Newton, em que um valor aproximado para x, y,
y+ x
é sucessivamente melhorado utilizando a fórmula 2 y .
√
Por exemplo, para calcular 3, poderíamos efectuar os seguintes cálculos:
Passo
1
2
3
4
5
6
Aproximação
3
2
1.75
1.732142857
1.73205081
1.732050808
Nova aproximação
2
1.75
1.732142857
1.73205081
1.732050808
1.732050808
√
Considerando que uma primeira aproximação grosseira para x pode ser x, escreva um
procedimento para calcular a raiz quadrada de um número.
4. (3) A constante e é um dos números mais importantes em Matemática, a par com
os elementos neutros da adição (0) e da multiplicação (1), com a constante π e com a
unidade imaginária i.
O valor de e corresponde ao número real que é a soma da seguinte série infinita
∞
X
1
1
1
1
1
e=
= + + + + ...
n!
0! 1! 2! 3!
n=0
Escreva um procedimento para calcular uma aproximação do número e, utilizando a
série apresentada. A condição de paragem deve ser determinada por si e devidamente
justificada.
24
CAPÍTULO 2. ABSTRACÇÃO PROCEDIMENTAL
Capítulo 3
Processos gerados por procedimentos
3.1
Exercícios de revisão
1. Explique os seguintes conceitos: procedimento e processo gerado por um procedimento.
2. Quais são as características de um processo recursivo?
3. Quais são as características de um processo iterativo linear?
4. Será que um procedimento recursivo pode gerar um processo iterativo? Justifique a sua
resposta e dê um exemplo.
5. Considere a afirmação “os procedimentos que geram processos iterativos são sempre melhores que os procedimentos que geram processos recursivos”. Comente-a relativamente
aos seguintes aspectos: (a) memória ocupada; (b) tempo gasto; (c) facilidade de escrita
e leitura do programa.
6. Qual o interesse de estudar a ordem de crescimento de um processo? Compare as ordens de crescimento (temporal e espacial) entre processos recursivos lineares e iterativos
lineares.
7. Diga o que significa a frase “A ordem de crescimento do recurso R(n) é Θ(n)”.
8. Usando a definição da função Θ que define a ordem de crescimento de um processo,
explique o que significa um processo ter ordem de crescimento polinomial.
3.2
Exercícios de programação
1. (1) Considere o seguinte procedimento
(define (misterio x)
(cond ((= x 0) (newline))
(else (display (remainder x 10))
(misterio (quotient x 10)))))
Qual a função calculada pelo procedimento misterio?
Sugestão: Siga o processo gerado por este procedimento para alguns inteiros. Depois
admire o poder dos procedimentos recursivos.
26
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
2. (1) Considere a definição do seguinte procedimento em Scheme que recebe inteiros
superiores ou iguais a zero:
(define (misterio?-aux b c)
(cond ((zero? b) #t)
((zero? c) #f)
(else (misterio?-aux (sub1 (sub1 b))
(sub1 (sub1 c))))))
(define (misterio? a)
(misterio?-aux a (sub1 a)))
(a) Explique qual a função matemática calculada pelo procedimento misterio?.
(b) O processo gerado pelo procedimento misterio?-aux é iterativo ou recursivo? Justifique a sua resposta.
3. (1) Considere o seguinte procedimento:
(define (misterio-aux n ac)
(if (< n 10)
(+ n (* ac 10))
(misterio-aux (quotient n 10)
(+ (remainder n 10) (* ac 10)))))
(define (misterio n)
(misterio-aux n 0))
(a) Entre os procedimentos apresentados, misterio e misterio-aux, existe algum que
seja um procedimento recursivo? Justifique a sua resposta.
(b) Mostre a evolução do processo gerado pela avaliação de (misterio 149).
(c) O procedimento misterio gera um processo recursivo ou iterativo? Justifique a
sua resposta.
4. (2) Considere o seguinte procedimento
(define (misterio x n)
(if (= n 0)
0
(+ (* x n) (misterio x (- n 1)))))
(a) Mostre a evolução do processo gerado pela avaliação de (misterio 2 3).
(b) O procedimento apresentado é um procedimento recursivo? Justifique.
(c) O procedimento apresentado gera um processo recursivo ou iterativo? Justifique.
(d) Se o processo gerado era iterativo, transforme o procedimento de forma que gere um
processo recursivo. Se o processo gerado era recursivo, transforme o procedimento,
de forma a que gere um processo iterativo.
3.2. EXERCÍCIOS DE PROGRAMAÇÃO
27
5. (2) Suponha que as operações de multiplicação e potência não existiam em Scheme e
que pretende calcular o quadrado de um número natural. O quadrado de um número
natural pode ser calculado como sendo a soma de todos os números ímpares inferiores
ao dobro do número. Com efeito:
n
1
2
3
4
5
6
...
1 + . . . + (2n − 1)
1=
1+3 =
1+3+5 =
1+3+5+7 =
1+3+5+7+9 =
1+3+5+7+9+11 =
...
n2
1
4
9
16
25
36
...
Note que o dobro de um número também não pode ser calculado recorrendo à operação
de multiplicação.
Escreva dois procedimentos que calculam o quadrado de um número natural utilizando
o método descrito.
(a) Um procedimento que dá origem a um processo recursivo linear.
(b) Um procedimento que dá origem a um processo iterativo linear.
6. (2) Defina um procedimento recursivo que recebe três argumentos a, b e n e que devolve
o valor de somar n vezes a a b, i.e., b + a + a + · · · + a, n vezes.
(a) Gerando um processo recursivo.
(b) Gerando um processo iterativo.
7. Suponha que em Scheme não existiam as operações aritméticas +, -, quotient, * e /
nem os predicados <, > e = mas que existem os procedimentos add1, sub1 e zero? que
recebem como argumento um inteiro e devolvem, respectivamente, o seu sucessor, o seu
antecessor, e o resultado de verificar se o número é 0.
Neste exercício apenas poderá utilizar estas 3 operações e outras eventualmente definidas
utilizando estas.
(a) (1) (Secção 2.2.3, Ex 1a) Escreva um procedimento soma, que gere um processo
iterativo, e que recebe dois números inteiros positivos n e m, e devolve a soma dos
dois.
Sugestão: A soma de dois números n e m pode ser vista como n + 1 + · · · + 1,
m vezes.
> (soma 8 2)
10
(b) (1) (Secção 2.2.3, Ex 1b) Escreva um procedimento multiplica, que gere um
processo iterativo, e que recebe dois números inteiros positivos n e m, e devolve a
multiplicação dos dois.
Sugestão: A multiplicação de dois números n e m pode ser vista como n + n +
· · · + n, m vezes.
28
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
> (multiplica 8 2)
16
(c) (1) (Secção 2.2.3, Ex 1c) Escreva um procedimento menos, que gere um processo
iterativo, e que recebe dois números inteiros positivos n e m, e devolve a diferença
dos dois.
Sugestão: Use uma ideia semelhante ao exercício 7a.
> (menos 8 2)
6
> (menos 2 8)
-6
(d) (2) (Secção 2.2.3, Ex 1d) Escreva um procedimento par?, que gere um processo
iterativo, e que recebe um número inteiro positivo n, e devolve verdadeiro se n for
par e falso no caso contrário.
> (par? 8)
#t
> (par? 5)
#f
(e) (1) Escreva um procedimento igual?, e que gere um processo iterativo, que recebe
dois números inteiros positivos n e m, e devolve verdadeiro se o n for igual a m e
falso no caso contrário.
> (igual? 8 2)
#f
> (igual? 8 8)
#t
> (igual? 2 8)
#f
(f) (1) Escreva um procedimento menor?, e que gere um processo iterativo, que recebe
dois números inteiros positivos n e m, e devolve verdadeiro se o n for menor do que
m e falso no caso contrário.
> (menor? 8 2)
#f
> (menor? 8 8)
#f
> (menor? 2 8)
#t
(g) (2) (Secção 2.2.3, Ex 1e) Escreva um procedimento quociente, que gere um processo iterativo, e que recebe dois números inteiros positivos n e m, e devolve o
quociente da divisão de n por m. No caso de m ser 0 deverá devolver 0.
Relembre que o quociente da divisão de dois números inteiros positivos n e m é o
maior inteiro r tal que r.m ≤ n.
Sugestão: Utilize os procedimentos menos e menor? definidos anteriormente.
3.2. EXERCÍCIOS DE PROGRAMAÇÃO
29
> (quociente 8 2)
4
> (quociente 10 3)
3
(h) (2) Escreva um procedimento resto, que gere um processo iterativo, e que recebe
dois números inteiros positivos n e m, e devolve o resto da divisão de n por m. No
caso de m ser 0 deverá devolver n.
> (resto 8 2)
0
> (resto 10 3)
1
(i) (2) Escreva um procedimento simetrico, que gere um processo iterativo, e que
recebe um número inteiro n, e devolve o simetrico de n.
> (simetrico 8)
-8
> (simetrico -3)
3
8. (1) (Secção 2.2.3, Ex 3) Escreva um procedimento soma-quadrados, que gere um processo iterativo, e que recebe um número inteiro positivo n, e devolve a soma do quadrado
de todos os números até n.
> (soma-quadrados 3)
14
> (soma-quadrados 5)
55
9. (1) (Secção 2.2.3, Ex 5) Escreva um procedimento potencia, que gere um processo
iterativo, e que recebe dois números inteiros positivos b e n, e devolve a potência n de b,
i.e., bn .
> (potencia 3 2)
9
> (potencia 2 4)
16
10. (2) Um número n é quadrado perfeito se existir um m tal que m2 = n. Escreva um
procedimento quadrado-perfeito?, que gere um processo iterativo, e que recebe um
número n, e devolve verdadeiro se n for um quadrado perfeito e falso no caso contrário.
> (quadrado-perfeito? 4)
#t
> (quadrado-perfeito? 8)
#f
30
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
11. (2) Um número n diz-se primo se os seus únicos divisores são o 1 e o próprio n. O
número 1 não é primo. Um modo, pouco eficiente, de determinar se um dado inteiro é
primo corresponde a dividi-lo sucessivamente por todos os inteiros menores que ele.
Escreva um procedimento primo?, que gere um processo iterativo, e que recebe um
número inteiro positivo n, e usando o método acima devolve verdadeiro se o número for
primo e falso no caso contrário.
> (primo? 53)
#t
> (primo? 21)
#f
12. (3) Um número é livre de quadrados se não for divisível por nenhum quadrado perfeito
para além de 1. Escreva um procedimento livre-quadrados?, que gere um processo
iterativo, e que recebe um número n, e devolve verdadeiro se n for livre de quadrados e
falso no caso contrário.
> (livre-quadrados? 4)
#f
> (livre-quadrados? 50)
#f
> (livre-quadrados? 70)
#t
13. (3) Um número n diz-se poderoso se para cada primo p, se p é divisor de n então p2
também é divisor de n. Escreva um procedimento poderoso?, que gere um processo
iterativo, e que recebe um número inteiro positivo n, e devolve verdadeiro se o número
for poderoso e falso no caso contrário.
> (poderoso?
#t
> (poderoso?
#t
> (poderoso?
#f
> (poderoso?
#f
100)
36)
75)
2)
14. (2) (Secção 2.2.3, Ex 6) Um número d é divisor de n se o resto da divisão de n por d
for 0. Escreva um procedimento numero-divisores, que gere um processo iterativo, e
que recebe um número inteiro positivo n, e devolve o número de divisores de n. No caso
de n ser 0 deverá devolver 0.
> (numero-divisores 20)
6
> (numero-divisores 13)
2
3.2. EXERCÍCIOS DE PROGRAMAÇÃO
31
15. (2) (Secção 2.2.3, Ex 9) Escreva um procedimento soma-divisores, que gere um processo iterativo, e que recebe um número inteiro positivo n, e devolve a soma de todos os
divisores de n. No caso de n ser 0 deverá devolver 0.
> (soma-divisores 20)
42
> (soma-divisores 13)
14
16. (3) (Secção 2.2.3, Ex 11) A raiz inteira de índice e de um número n é o maior número
inteiro r tal que re ≤ n. Escreva um procedimento raiz, que gere um processo iterativo,
e que recebe dois números inteiros positivos n e e, e devolve a raiz inteira de n de índice
e. No caso de e ser 0 deverá devolver 0.
> (raiz 8 3)
2
> (raiz 15 2)
3
17. (3) Um número n diz-se triangular se n = 1 + 2 + · · · + (m − 1) + m para algum m.
Escreva um procedimento triangular?, que gere um processo iterativo, e que recebe um
número inteiro positivo n, e devolve verdadeiro se o número for triangular e falso no caso
contrário. No caso de n ser 0 deverá devolver falso.
> (triangular? 6)
#t
> (triangular? 8)
#f
18. (3) Dois números n e m dizem-se primos entre si se não têm nenhum divisor em comum
à excepção do 1. Escreva um procedimento primos-entre-si?, que gere um processo
iterativo, e que recebe dois números inteiros positivos n e m, e devolve verdadeiro se os
números forem primos entre si e falso no caso contrário. No caso de n ou m serem 0
deverá devolver falso.
> (primos-entre-si? 4 10)
#f
> (primos-entre-si? 21 10)
#t
19. (3) Um número n diz-se um divisor fraco de m se todos os factores primos de n
também são factores primos de m. Escreva um procedimento divisor-fraco?, que
gere um processo iterativo, e que recebe dois números inteiros positivos n e m, e devolve
verdadeiro se n for um divisor fraco de m e falso no caso contrário. No caso de n ou m
serem 0 deverá devolver falso.
32
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
> (divisor-fraco? 4 10)
#t
> (divisor-fraco? 10 4)
#f
> (divisor-fraco? 6 10)
#f
20. (4) O máximo divisor comum de dois números n e m é o maior inteiro x tal que x é
divisor de n e m. Escreva um procedimento mdc, que gere um processo iterativo, e que
recebe dois números inteiros positivos n e m, e devolve o máximo divisor comum dos dois
números. No caso de n e m serem ambos 0 deverá devolver 0. Se apenas um deles for 0
deverá devolver o outro.
> (mdc 3 0)
3
> (mdc 12 20)
4
> (mdc 10 20)
10
21. (4) O mínimo múltiplo comum de dois números n e m é o menor inteiro x tal que x
é divisível por n e m. Escreva um procedimento mmc, que gere um processo iterativo, e
que recebe dois números inteiros positivos n e m, e devolve o mínimo múltiplo comum
dos dois números. No caso de n ou m serem 0 deverá devolver 0.
> (mmc 4 6)
12
> (mmc 12 5)
60
22. (3) Um número n é o n-ésimo primo se for primo e existirem n − 1 números primos
menores que ele. Escreva um procedimento nesimo-primo, que gere um processo iterativo, e que recebe um número inteiro positivo n, e devolve o n-ésimo número primo. No
caso de n ser 0 deverá devolver 0.
> (nesimo-primo 1)
2
> (nesimo-primo 10)
29
23. (3) Um número p é primo de Mersenne se p é primo e 2p − 1 também é primo. Um
número n é o n-ésimo primo de Mersenne se existirem n−1 primos de Mersenne menores
que n. Os primeiros 10 primos de Mersenne são 2, 3, 5, 7, 13, 17, 19, 31, 61, 89.
Escreva um procedimento nesimo-primo-mersenne, que gere um processo iterativo, e
que recebe um número n, e devolve o n-ésimo primo de Mersenne.
3.2. EXERCÍCIOS DE PROGRAMAÇÃO
33
> (nesimo-primo-mersenne 3)
5
> (nesimo-primo-mersenne 9)
61
24. (3) Um número d é o k-ésimo divisor de n se for divisor de n e existirem k−1 divisores de
n menores que d. Escreva um procedimento k-divisor, que gere um processo iterativo,
e que recebe dois números inteiros positivos n e k, e devolve o k-ésimo divisor de n. No
caso de n ser 0, ou k ser 0, ou n ter menos de k divisores deverá devolver 0.
> (kesimo-divisor 20 3)
4
> (kesimo-divisor 20 6)
20
> (kesimo-divisor 20 7)
0
25. (3) Um número p é o k-ésimo factor primo de n se p é primo e existem k − 1 factores
primos de n menores que p. Escreva um procedimento kesimo-factor-primo, que gere
um processo iterativo, e que recebe dois números inteiros positivos n e k, e devolve o
seu k-ésimo factor primo de n. No caso de n ter menos de k factores primos ou k ser 0,
deverá devolver 0.
> (kesimo-factor-primo 3 1)
3
> (kesimo-factor-primo 3 2)
0
> (kesimo-factor-primo 60 3)
5
26. (4) (Secção 2.2.3, Ex 12) Escreva um procedimento kesimo-expoente, que gere um
processo iterativo, e que recebe dois números inteiros positivos n e k, e devolve o expoente
do k-ésimo factor primo de n. No caso de n ter menos de k factores primos ou k ser 0,
deverá devolver 0.
> (kesimo-expoente 72 1)
3
> (kesimo-expoente 72 2)
2
Nos exercícios que se seguem poderá ser útil a utilização dos seguintes procedimentos
sobre números inteiros:
• (remainder n m) devolve o resto da divisão de n por m.
• (quotient n m) devolve o quociente da divisão de n por m.
27. (3) (Secção 2.2.3, Ex 13) Escreva um procedimento numero-digitos, que gere um
processo iterativo, e que recebe um número inteiro positivo n, e devolve o número de
dígitos de n.
34
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
> (numero-digitos 9)
1
> (numero-digitos 1012)
4
28. (3) (Secção 2.2.3, Ex 14) Escreva um procedimento soma-digitos, que gere um processo iterativo, e que recebe um número inteiro positivo n, e devolve a soma de todos os
dígitos de n.
> (soma-digitos 9)
9
> (soma-digitos 1012)
4
29. (3) Escreva um procedimento existe-digito?, que gere um processo iterativo, e que
recebe um número inteiro positivo n e um dígito d, e devolve verdadeiro se o dígito d
ocorrer em n e falso no caso contrário.
> (existe-digito? 234 3)
#t
> (existe-digito? 538 7)
#f
30. (4) (Secção 2.2.3, Ex 16) Escreva um procedimento digitos-impares, que gere um
processo iterativo, e que recebe um número inteiro positivo n, e devolve o número composto apenas pelos dígitos ímpares de n.
> (digitos-impares 94558)
955
> (digitos-impares 2468)
0
31. (3) O dígito de posição k de um número n é o dígito na k-ésima posição de n a partir do
dígito das unidades. Escreva um procedimento posicao, que gere um processo iterativo,
e que recebe dois números inteiros positivos n e k, e devolve o dígito na posicao k de n.
No caso de n ter menos de k dígitos ou k ser 0, deverá devolver 0.
> (posicao 12345 2)
4
> (posicao 12345 7)
0
32. (3) Um número é capicua se se lê igualmente da esquerda para a direita e vice-versa.
Escreva um procedimento capicua?, que gere um processo iterativo, e que recebe um
número inteiro positivo n, e devolve verdadeiro se o número for uma capicua e falso no
caso contrário.
Sugestão: Use o procedimento posicao definido na alínea 31
3.2. EXERCÍCIOS DE PROGRAMAÇÃO
35
> (capicua? 12321)
#t
> (capicua? 1221)
#t
> (capicua? 123210)
#f
33. (4) (Secção 2.2.3, Ex 17) Escreva um procedimento muda-digito, que gere um processo
iterativo, e que recebe três números inteiros positivos n, k e d, e devolve o inteiro que
resulta de substituir o dígito na posição k de n por d.
> (muda-digito 12345 2 8)
12385
> (muda-digito 12345 7 8)
80012345
34. (4) (Secção 2.2.3, Ex 18) O espelho de um número inteiro positivo é o resultado de
inverter a ordem de todos os seus algarismos. Escreva um procedimento espelho, que
gere um processo iterativo, e que recebe um número inteiro positivo n, e devolve o seu
espelho.
> (espelho 391)
139
> (espelho 45679)
97654
35. (1) Usando o procedimento espelho definido acima, reescreva de novo o procedimento
capicua? definido na alínea 32.
36. (4) (Secção 2.2.3, Ex 20) Um número decimal d pode ser transformado num número binário bn bn−1 . . . b1 b0 através da seguinte recorrência: seja q0 = d e qi = quociente(qi−1 , 2)
para i > 0, e bi = resto(qi , 2). Escreva um procedimento decimal-binario, que gere
um processo iterativo, e que recebe um número d escrito em base 10 e devolve a sua
representação binária.
> (decimal-binario 33)
100001
> (decimal-binario 156)
10011100
36
CAPÍTULO 3. PROCESSOS GERADOS POR PROCEDIMENTOS
Capítulo 4
Estruturação de Procedimentos
4.1
Exercícios de revisão
1. Diga o que entende por linguagem estruturada em blocos. Descreva a regra associada a
esta estrutura, e diga qual a sua importância.
2. O que entende pelo domínio de um nome?
4.2
Exercícios de programação
4.2.1
Estrutura de Blocos
1. (1) Considere as seguintes alternativas para definir um procedimento que calcula a
função factorial.
Alternativa 1:
(define (factorial n)
(if (>= n 0)
(fact-aux n)
(error "factorial: argumento negativo")))
(define (fact-aux n)
(if (= n 0)
1
(* n (fact-aux (- n 1)))))
Alternativa 2:
(define (factorial n)
(define (fact-aux n)
(if (= n 0)
1
(* n (fact-aux (- n 1)))))
(if (>= n 0)
(fact-aux n)
(error "factorial: argumento negativo")))
38
CAPÍTULO 4. ESTRUTURAÇÃO DE PROCEDIMENTOS
(a) Compare estas duas alternativas quanto à garantia de que o factorial não é calculado
com valores indevidos.
Sugestão: Será que se pode avaliar directamente (fact-aux -1)?
(b) Como se chama a estrutura definida pela alternativa 2? Qual a sua vantagem?
2. (1) Considere o seguinte procedimento que calcula m!
n! (m > n), recorrendo à estrutura
de blocos. Identifique as variáveis locais e não locais para cada um dos procedimentos.
(define (quociente-de-factoriais m n)
(define (iter m res)
(if (= m n)
res
(iter (- m 1) (* m res))))
(iter m 1))
3. (1) (Secção 2.2.3, Ex 2) Recorrendo à estrutura de blocos, escreva um procedimento
somatorio que recebe um número inteiro positivo n, e devolve a soma de todos os
números até n. O seu procedimento deve gerar um processo iterativo.
> (somatorio 3)
6
> (somatorio 6)
21
4. (1) (Secção 2.2.3, Ex 4) Recorrendo à estrutura de blocos, escreva um procedimento
factorial que recebe um número inteiro positivo n, e devolve o factorial desse número.
O seu procedimento deve gerar um processo iterativo.
> (factorial 0)
1
> (factorial 5)
120
5. (2) (Secção 2.2.3, Ex 7) Recorrendo à estrutura de blocos, escreva um procedimento
numero-primos-menores que recebe um número inteiro positivo n, e devolve o número
de primos menores ou iguais a n. O seu procedimento deve gerar um processo iterativo.
Sugestão: Utilize o procedimento primo? definido na alínea 11 da Secção 3.2.
> (numero-primos-menores 9)
4
> (numero-primos-menores 23)
9
6. (2) (Secção 2.2.3, Ex 8) Recorrendo à estrutura de blocos, escreva um procedimento
numero-divisores-primos que recebe um número inteiro positivo n, e devolve o número
de divisores primos de n. No caso de n ser 0 deverá devolver 0. O seu procedimento
deve gerar um processo iterativo.
Sugestão: Utilize o procedimento primo? definido na alínea 11 da Secção 3.2.
4.2. EXERCÍCIOS DE PROGRAMAÇÃO
39
> (numero-divisores-primos 1)
0
> (numero-divisores-primos 20)
2
> (numero-divisores-primos 30)
3
7. (3) (Secção 2.2.3, Ex 10) O logaritmo inteiro de um número n na base b é o maior
número inteiro e tal que be ≤ n. Recorrendo à estrutura de blocos, escreva um procedimento logaritmo que recebe dois números inteiros positivos n e b, e devolve o logaritmo
inteiro de n na base b. No caso de n ou b serem 0 deverá devolver 0. O seu procedimento
deve gerar um processo iterativo.
> (logaritmo 8 2)
3
> (logaritmo 7 2)
2
8. (3) (Secção 2.2.3, Ex 15) Recorrendo à estrutura de blocos, escreva um procedimento
soma-digitos-pares que recebe um número inteiro positivo n, e devolve a soma de
todos os dígitos pares de n. O seu procedimento deve gerar um processo iterativo.
> (soma-digitos-pares 9)
0
> (soma-digitos-pares 1412)
6
9. (4) (Secção 2.2.3, Ex 19) Um número binário bn bn−1 . . . b1 b0 pode ser transformado
P
num número decimal usando a seguinte formula ni=0 bi 2i . Recorrendo à estrutura de
blocos, escreva um procedimento binario-decimal que recebe um número b escrito
em binário e devolve a sua representação decimal. O seu procedimento deve gerar um
processo iterativo.
> (binario-decimal 1001)
9
> (binario-decimal 10000)
16
4.2.2
Utilização de Nomes Locais
1. Em relação às seguintes expressões utilizando o “let”, avalie o valor da expressão e
transforme-a numa expressão equivalente utilizando o “lambda”.
(a) (1)
(let ((x 5)
(y 3))
(* x y))
40
CAPÍTULO 4. ESTRUTURAÇÃO DE PROCEDIMENTOS
(b) (1)
(let ((x 4)
(y 3))
(let ((z (* x y)))
(+ z x)))
(c) (2)
(let ((x 5))
(let ((x 3)
(y (* x 2)))
(+ x y)))
(d) (2)
(let ((x 5)
(y 12))
(+ x (let ((x (+ x y)))
(+ x 3))))
2. (2) Suponha que a tem o valor 5 no ambiente global. Diga qual o resultado de avaliar
a seguinte expressão:
(let ((a 3)
(b (* a 4)))
(+ a b))
3. (2) Considere as seguintes expressões. São equivalentes? Justifique.
(let ((x 8))
(let ((x 5)
(y (+ x 4)))
(+ x y)))
(let* ((x 8)
(x 5)
(y (+ x 4)))
(+ x y))
4. Para cada uma das seguintes combinações envolvendo uma expressão “lambda”, calcule
o seu valor e transforme-a numa expressão equivalente utilizando o “let”.
(a) (1)
((lambda (x y)
(+ (* 3 x)
y))
2
3)
(b) (1)
((lambda (x)
((lambda (y)
((lambda (z) (* y z))
(+ x y)))
2))
5)
4.2. EXERCÍCIOS DE PROGRAMAÇÃO
41
(c) (1)
((lambda (x)
((lambda (y) (+ (* 2 y) x))
(+ x 3)))
5)
(d) (2)
((lambda (x y)
((lambda (x) (+ (* 2 x)
y))
(+ x y)))
6
2)
(e) (2)
((lambda (x y)
(+ x y ((lambda (z) (* 2 z))
(+ y 1))))
5
2)
5. Para cada uma das seguintes séries, escreva um programa em Scheme que calcula o valor
aproximado da série. O seu programa deve apresentar uma estrutura de blocos e deve
evitar cálculos repetidos. Pode utilizar os procedimentos potencia e factorial sem os
definir.
(a) (2)
∞
X 1
1 1 1
1
1+ + + +
+ ... =
2 4 8 16
2n
n=0
(b) (2)
∞
1−
X
1 1 1 1
1
+ − + + ... =
(−1)n+1 = ln(2)
2 3 4 5
n
n=1
(c) (2)
∞
X
xn
n=1
n!
= ex
(d) (2)
∞
1−
X
x2 x4
x2n−2
+
− ... =
(−1)n+1
= cos(x)
2!
4!
(2n − 2)!
n=1
42
CAPÍTULO 4. ESTRUTURAÇÃO DE PROCEDIMENTOS
Capítulo 5
Abstracção de dados
5.1
Exercícios de revisão
1. Diga o que é um tipo abstracto de informação.
2. Diga qual é a diferença entre tipos de informação elementares e tipos de informação
estruturados.
3. Explique em que consiste a abstracção de dados, usando os termos barreiras de abstracção, encapsulação da informação e anonimato da representação.
4. Explique quais são as vantagens da abstracção de dados.
5. Compare a abstracção de dados com a abstracção procedimental.
6. Justifique a seguinte afirmação “a abstracção de dados aumenta o poder expressivo da
nossa linguagem de programação”.
7. Quais são os quatro passos a seguir na definição de um tipo abstracto de informação?
Explique em que consiste cada um deles.
8. Diga o que são operações básicas de um tipo abstracto de informação e quais os grupos
em que estas são divididas.
9. Explique o que são as barreiras de abstracção criadas por um tipo de informação e quais
os inconvenientes de não as respeitar.
10. Apresente a metodologia dos tipos abstractos de informação e explique porque é que
esta metodologia garante a abstracão de dados.
11. Diga o que é o anonimato da representação e qual a sua importância.
12. Na criação de um tipo abstracto de informação, há dois tipos de representação a considerar. Diga quais são e descreva cada um deles.
13. Diga o que é uma árvore binária e quais são as suas operações básicas, classificando-as
de acordo com os vários grupos de operações.
43
44
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
5.2
Exercícios de programação
5.2.1
Caixas e ponteiros
1. (1) Considere a seguinte estrutura de pares usando a notação de caixas e ponteiros(correspondente à variável Estr):
Para cada uma das seguintes expressões escreva o seu valor (o qual pode ser um número
inteiro, uma estrutura de pares ou pode originar um erro). No caso de a expressão
originar um erro explique a razão do erro.
(a) (car Estr)
(b) (car (car (cdr Estr)))
(c) (cdr (cdr (cdr Estr)))
2. (1) Represente as seguintes estruturas, usando a notação de caixas e ponteiros:
(a) (1 . 2)
(b) (1 . ("bom dia". 3))
(c) (1 . (2 . (3 . 4)))
(d) ((1 . 2) . ((3 . (4 . 5)) . (7 . 8)))
5.2.2
Tipo tempo
Suponha que desejava criar o tipo tempo em Scheme. Suponha que o tempo é caracterizado
por um certo número de horas (um inteiro não negativo), minutos (um inteiro entre 0 e 59) e
segundos (um inteiro entre 0 e 59).
1. (2) Especifique as operações básicas para o tipo tempo.
2. (1) Escolha uma representação interna para o tipo tempo usando pares.
3. (2) Escreva em Scheme as operações básicas, de acordo com a representação escolhida.
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
45
4. (1) Supondo que a representação externa para os elementos do tipo tempo é h : mm : ss
(em que h é um inteiro positivo que representa as horas, mm são dois dígitos que
identificam os minutos e ss são dois dígitos que identificam os segundos) escreva o
transformador de saída escreve-tempo para o tipo tempo. Por exemplo,
> (escreve-tempo (faz-tempo 9 2 34))
9:02:34
5. (1) Escreva o procedimento diferenca-segundos que calcula o número de segundos
entre dois instantes de tempo. Este procedimento apenas deve produzir um valor se o
segundo tempo for maior do que o primeiro, gerando uma mensagem de erro se essa
condição não se verificar.
> (diferenca-segundos (faz-tempo 10 2 34) (faz-tempo 11 2 34))
3600
6. (1) Escreva o procedimento diferenca-tempo que calcula a diferença entre dois instantes de tempo devolvendo o valor em termos de horas, minutos e segundos. Este
procedimento apenas deve produzir um valor se o segundo tempo for maior do que o
primeiro, gerando uma mensagem de erro se essa condição não se verificar.
> (escreve-tempo (diferenca-tempo (faz-tempo 10 2 34) (faz-tempo 11 4 39)))
1:02:05
7. (2) Escreva o procedimento soma-tempos que calcula o tempo resultante da soma entre
dois instantes de tempo.
> (escreve-tempo (soma-tempos (faz-tempo 1 45 30) (faz-tempo 2 20 40)))
4:06:10
8. (2) Suponha agora que pretende representar os elementos do tipo tempo através de
inteiros positivos com a forma hmmss, em que h é um inteiro não negativo que representa
o número de horas, mm e ss são dois inteiros entre 0 e 59 cada um e que representam,
respectivamente, os minutos e os segundos do tempo.
Escreva em Scheme as operações básicas, de acordo com esta nova representação.
9. (1) Seria possível utilizar as operações definidas nos exercícios anteriores, 4–7, usando
esta nova representação? Justifique.
5.2.3
Tipo data
Suponha que desejava criar o tipo data em Scheme. Suponha que uma data é caracterizada
por um dia (um inteiro entre 1 e 31), um mês (um inteiro entre 1 e 12) e um ano. Para cada
data, deve ser respeitado o limite de dias de cada mês, incluindo o caso de Fevereiro nos anos
bissextos.
1. (1) Especifique as operações básicas para o tipo data.
46
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
2. (2) Escolha uma representação interna para o tipo data usando pares.
3. (1) Escreva em Scheme as operações básicas, de acordo com a representação escolhida.
4. (1) Supondo que a representação externa para um elemento do tipo data é d/m/a (em
que d representa o dia, m o mês e a o ano) escreva o transformador de saída para o tipo
data. Por exemplo,
> (escreve-data (faz-data 5 9 2011))
5/9/2011
5. (2) Tendo em conta as operações básicas do tipo data, defina um procedimento anterior?
que recebe como argumentos duas datas e tem o valor verdadeiro se a primeira data for
anterior à segunda e falso em caso contrário.
> (anterior? (faz-data 2 1 2003) (faz-data 2 1 2005))
#t
6. (2) Tendo em conta as operações básicas do tipo data, defina um procedimento idade
que recebe como argumentos a data de nascimento de uma pessoa e outra data posterior
e devolve a idade da pessoa na segunda data.
> (idade (faz-data 2 1 2003) (faz-data 2 1 2005))
2
> (idade (faz-data 2 1 2003) (faz-data 2 3 2006))
3
5.2.4
Complexos
Suponha que desejava criar o tipo número complexo em Scheme. Um número complexo é
um número que é constituído por uma parte real e por uma parte imaginária. Um número
complexo pode ser escrito sob a forma a + bi, em que a e b são números reais e i representa
a unidade imaginária. Esta tem a propriedade i2 = −1. Os reais a e b são chamados,
respectivamente, a parte real e a parte imaginária de a + bi. Os números complexos podem ser
representados geometricamente no plano complexo (representação rectangular ou cartesiana),
representando-se a parte real, a, no eixo horizontal e a parte imaginária, b, no eixo vertical.
1. Defina as operações básicas para o tipo número complexo.
2. Escolha uma representação para números complexos baseada em pares.
3. Com base na representação escolhida, implemente as operações básicas para números
complexos.
4. Com base na representação escolhida, escreva o transformador de saída para números
complexos.
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
47
5. Um número complexo diz-se um imaginário puro se a sua parte real for zero. Usando os
resultados das alíneas anteriores, e a abstracção adequada, escreva um procedimento que
recebe um número complexo e que decide se este é um imaginário puro. Por exemplo:
> (im-puro? (cmp 2 3))
#f
> (im-puro? (cmp 0 3))
#t
6. Considere as seguintes operações definidas sobre números complexos:
(a + bi) + (c + di) = (a + c) + (b + d)i
(a + bi)(c + di) = (ac − bd) + (ad + bc)i
Usando os resultados das alíneas anteriores, e a abstracção adequada, escreva procedimentos que somam e multiplicam números complexos. Por exemplo:
> (escreve-cmp (cmp+ (cmp 2 3)(cmp 4 5)))
6+8i
> (escreve-cmp (cmp* (cmp 2 3)(cmp 4 5)))
-7+22i
7. Considere a seguinte representação alternativa para números complexos: <[a + bi] =
(cons "complexo"(cons a b)).
(a) Escreva as operações básicas e o transformador de saída com base nesta representação.
(b) Quais as alterações a fazer nas operações imaginário puro e soma e multiplica complexos como consequência da alteração da representação. Justifique a sua resposta.
8. Suponha que por questões de segurança a representação de números complexos deveria
ser encriptada. Supondo que existem funções de codificação (code que recebe um número
real devolve a sua imagem encriptada) e de descodificação (decode, que recebe uma
imagem encriptada e devolve o real correspondente) e de teste de imagem encriptada
(code?), defina uma representação correspondente aos números complexos encriptados
e com base nessa representação volte a escrever as operações básicas para números
complexos.
9. Uma representação alternativa para o número complexo a + bi, conhecida por representação polar ou trignométrica (Figura
√ 5.1), utiliza a distância do número complexo à
origem do referencial, o módulo ρ = a2 + b2 , e o ângulo θ que a linha que liga a origem
do referencial ao ponto que representa o número complexo faz com a parte positiva do
48
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
y
b
ρ
θ
a
x
Figura 5.1: Representação polar de números complexos.
eixo 0~x. Para o complexo a + bi, o valor de θ


arctg( ab )







b

 arctg( a ) + π







 arctg( ab ) − π
θ=

π


 2







− π2







indef inido
é dado por:
se a > 0
se a < 0 e b ≥ 0
se a < 0 e b < 0
se a = 0 e b > 0
se a = 0 e b < 0
se a = 0 e b = 0
Com base nesta representação, podemos escrever:
a + bi = ρ(cos(θ) + sen(θ)i)
Escolha uma representação para números complexos em notação polar e escreva as operações básicas para complexos com base nessa representação.
10. Escreva as operações rect->polar e polar->rect que transformas as representações
rectangular em polar e vice-versa.
5.2.5
Listas
1. (1) Escreva um procedimento ultimo que recebe uma lista não vazia, e devolve o
último elemento da lista.
> (ultimo ’(4 5 6))
6
> (ultimo ’(1))
1
2. (1) Escreva um procedimento produto-lista que recebe uma lista de números inteiros, e devolve o produto de todos os elementos da lista. Considere que o produto dos
elementos de uma lista vazia tem o valor 1.Exemplo,
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
49
> (produto-lista ’(4 5 6))
120
> (produto-lista ’())
1
3. (1) Escreva um procedimento conta-pares que recebe uma lista de números inteiros,
e devolve o número de elementos pares na lista.
> (conta-pares ’(4 5 6))
2
> (conta-pares ’(3 5 7))
0
4. (1) Escreva um procedimento conta-menores que recebe uma lista de números inteiros
lst e um número inteiro n, e devolve o número de elementos da lista lst menores que
n.
> (conta-menores ’(4 5 6) 4)
0
> (conta-menores ’(3 5 7) 6)
2
5. (1) Escreva um procedimento numero-ocorrencias que recebe uma lista de números
inteiros e um número inteiro n, e devolve o número de vezes que não ocorre na lista.
> (numero-ocorrencias ’(4 5 6) 5)
1
> (numero-ocorrencias ’(3 5 7) 2)
0
6. (2) Escreva um procedimento todos-pares? que recebe uma lista de números inteiros,
e devolve verdadeiro se a lista for constituída exclusivamente por números pares e falso
no caso contrário.
> (todos-pares? ’(4 5 6))
#f
> (todos-pares? ’(4 4 6))
#t
7. (2) Escreva um procedimento ocorre-lista? que recebe uma lista de números inteiros
e um número inteiro n, e devolve verdadeiro se o número n ocorrer na lista e falso no
caso contrário.
> (ocorre-lista? ’(3 2 4) 3)
#t
> (ocorre-lista? ’(3 2 4) 1)
#f
50
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
8. (3) Escreva um procedimento maximo-lista que recebe uma lista não vazia de números
inteiros, e devolve o maior elemento da lista.
> (maximo-lista ’(4 5 6))
6
> (maximo-lista ’(7 3 6))
7
9. (2) Escreva um procedimento quadrados-lista que recebe uma lista de números inteiros e devolve a lista que resulta de elevar todos os números da lista original ao quadrado.
> (quadrados-lista ’(3 2 4))
(9 4 16)
10. (2) Escreva um procedimento substitui que recebe uma lista de números inteiros lst,
um número inteiro v (velho) e um número inteiro n (novo), e devolve a lista que resulta
de substituir em lst todas as ocorrências de v por n.
> (substitui ’(4 3 2 4) 4 5)
(5 3 2 5)
11. (2) Escreva um procedimento insere-no-fim que recebe uma lista lst e um número
n, e devolve a lista que resulta de inserir o elemento n no final da lista lst.
> (insere-no-fim 3 ’(3 2 4))
(3 2 4 3)
> (insere-no-fim 3 ’())
(3)
12. (2) Escreva um procedimento remove-ultimo que recebe uma lista não vazia, e devolve
a lista que resulta de remover o último elemento da lista.
> (remove-ultimo ’(3 2 4))
(3 2)
> (remove-ultimo ’(4))
()
13. (2) Escreva um procedimento junta que recebe duas listas, e devolve a lista que resulta
de juntar a segunda lista no final da primeira.
> (junta
(3 2 4 1
> (junta
(4 5 3)
> (junta
(1 2 3)
’(3 2 4) ’(1 2 3))
2 3)
’() ’(4 5 3))
’(1 2 3) ’())
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
51
14. (2) Escreva um procedimento inverte que recebe uma lista, e devolve a lista que
resulta de inverter a lista original.
Sugestão: Utilize o procedimento insere-no-fim definido no exercício 11 ou os procedimentos ultimo e remove-ultimo definidos nos exercícios 1 e 12.
> (inverte ’(3 2 4))
(4 2 3)
15. (3) Escreva um procedimento alisa que recebe uma lista, cujos elementos podem ser
listas, e devolve a lista com todos os elementos atómicos da lista original.
Sugestão: Utilize o procedimento junta definido no exercício 13.
> (alisa ’((((3))) 4 5 (8 (9))))
(3 4 5 8 9)
16. (3) Escreva um procedimento sublistas que recebe uma lista, e conta o número total
de sublistas que esta contém.
> (sublistas ’(1 2 3))
0
> (sublistas ’((1) 2 (3)))
2
> (sublistas ’(((((1))))))
4
17. (2) Escreva um procedimento selecciona-pares que recebe uma lista de números
inteiros, e devolve a lista com todos os números pares da lista original.
> (selecciona-pares ’(4 3 2 4))
(4 2 4)
> (selecciona-pares ’(7 3 5))
()
18. (2) Escreva um procedimento selecciona-menores que recebe uma lista de números
inteiros e um número inteiro n, e devolve a lista com todos os números da lista original
menores que n.
> (selecciona-menores ’(4 3 2 4) 4)
(3 2)
> (selecciona-menores ’(7 3 5) 1)
()
19. (2) Escreva um procedimento selecciona-primos que recebe uma lista de números
inteiros, e devolve a lista com todos os números primos da lista original.
> (selecciona-primos ’(4 3 2 4))
(3 2)
> (selecciona-primos ’(4 6 8 9))
()
52
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
20. (2) Escreva um procedimento remove-elemento que recebe uma lista de números inteiros e um número inteiro n, e devolve a lista que resulta de remover todas as ocorrências
de n da lista original.
> (remove-elemento ’(4 3 2 4) 4)
(3 2)
> (remove-elemento ’(7 3 5) 1)
(7 3 5)
21. (2) Escreva um procedimento altera-posicao que recebe uma lista, um número inteiro
positivo p e um número inteiro n, e devolve a lista que resulta de alterar o elemento na
posição p da lista para n. Caso a lista tenha menos de p posições deverá devolver a lista
original.
> (altera-posicao ’(4 3 2 2 1 4) 4 10)
(4 3 2 10 1 4)
> (altera-posicao ’(4 3 2 2 1 4) 100 8)
(4 3 2 2 1 4)
22. (2) Escreva um procedimento posicoes-lista que recebe uma lista de números inteiros e um número inteiro n, e devolve a lista de todas as posições em que n ocorre na
lista.
> (posicoes-lista ’(4 3 2 2 1 4) 4)
(1 6)
> (posicoes-lista ’(4 3 2 2 1 4) 6)
()
23. (2) Escreva um procedimento posicoes-dos-pares que recebe uma lista de números
inteiros, e devolve a lista de todas as posições da lista em que ocorrem números pares.
> (posicoes-dos-pares ’(4 3 2 2 1 4))
(1 3 4 6)
> (posicoes-dos-pares ’(5 3 5 3 1))
()
24. (2) Escreva um procedimento ordenada? que recebe uma lista de números inteiros, e
devolve verdadeiro se a lista estiver ordenada de forma crescente e falso no caso contrário.
> (ordenada? ’(3 2 1 2 3))
#f
> (ordenada? ’(3 5 7 8))
#t
25. (3) Escreva um procedimento intercala que recebe duas listas, e devolve a lista que
resulta de intercalar os elementos das duas listas. Se as listas não forem do mesmo
tamanho, o que restar da lista maior deverá ser adicionado no fim.
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
53
> (intercala ’(3 2 4) ’(1 2 3))
(3 1 2 2 4 3)
> (intercala ’(2 3) ’(4 5 8 6))
(2 4 3 5 8 6)
26. (2) Escreva um procedimento insere-ordenado que recebe uma lista ordenada de
números inteiros e um número inteiro n, e devolve a lista que resulta de inserir o número
n na posição certa na lista de modo a que o resultado continue uma lista ordenada.
> (insere-ordenado ’(3 5 7 8) 7)
(3 5 7 7 8)
> (insere-ordenado ’(3 5 7 8) 1)
(1 3 5 7 8)
> (insere-ordenado ’(3 5 7 8) 15)
(3 5 7 8 15)
27. (3) Escreva um procedimento parte que recebe uma lista de números inteiros lst e
um número inteiro n, e devolve uma lista contendo na primeira posição a lista com os
elementos de lst menores que n, e na segunda posição a lista com os elementos de lst
maiores ou iguais a n. A ordem pela qual os elementos aparecem nas listas devolvidas é
irrelevante.
> (parte ’(6 1 2 9 7) 3)
((1 2) (6 9 7))
> (parte ’(6 1 2 3 9 7) 3)
((1 2) (6 3 9 7))
> (parte ’(9 12 5) 4)
(() (9 12 5))
28. (2) Escreva um procedimento capicua? que recebe uma lista de números inteiros, e
devolve verdadeiro se a lista for uma capicua e falso no caso contrário.
Sugestão: Utilize os procedimentos ultimo e remove-ultimo definidos nos exercícios 1
e 12.
> (capicua? ’(3 2 1 2 3))
#t
> (capicua? ’(3 2 2 3))
#t
> (capicua? ’(3 2 1 3 2 3))
#f
29. (3) Escreva um procedimento capicua que recebe uma lista de números inteiros, e
devolve a lista que se obtém construindo uma capicua com a lista original.
Sugestão: Utilize o procedimento insere-no-fim do exercício 11.
> (capicua ’(3 4 7 1))
(3 4 7 1 1 7 4 3)
> (capicua ’(1 2))
(1 2 2 1)
54
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
30. (3) Escreva um procedimento remove-duplicados que recebe uma lista de números
inteiros lst, e fica apenas com uma cópia de cada elemento de lst. A ordem pela qual
os elementos aparecem na lista devolvida é irrelevante.
Sugestão: Utilize o procedimento remove-elemento do exercício 20.
> (remove-duplicados ’(4 3 2 2 1 4))
(4 3 2 1)
> (remove-duplicados ’(4 3 2 2 1 4 2))
(4 3 2 1)
> (remove-duplicados ’(7 5 3 4 6 2))
(7 5 3 4 6 2)
31. (3) Escreva um procedimento elementos-repetidos que recebe uma lista de números
inteiros, e devolve a lista com uma cópia de cada elemento que aparece repetido na lista.
A ordem pela qual os elementos aparecem na lista devolvida é irrelevante.
Sugestão: Utilize os procedimentos ocorre-lista? e remove-elemento dos exercícios 7 e 20.
> (elementos-repetidos ’(3 4 4 4 3 6 7))
(3 4)
> (elementos-repetidos ’(3 4 6 7))
()
32. (3) Escreva um procedimento conta-elementos que recebe uma lista de números inteiros, e devolve uma lista de pares em que cada par contém como primeiro elemento
um elemento da lista e como segundo elemento o número de vezes que este aparece na
lista. A ordem pela qual os pares aparecem na lista devolvida é irrelevante.
Respeite as barreiras de abstracção, mas lembre-se que está a lidar com dois tipos estruturados, a lista e o par.
Sugestão: Utilize os procedimentos ocorre-lista? e remove-elemento dos exercícios 7 e 20.
> (conta-elementos ’(3 4 5 5 3 3 9 3 3 12 3 12))
((3 . 6) (4 . 1) (5 . 2) (9 . 1) (12 . 2))
33. (2) Escreva um procedimento lista-inteiros que recebe um inteiro positivo n, e
devolva uma lista com todos os inteiros entre 0 e n (a ordem pela qual os números
aparecem na lista não é relevante).
> (lista-inteiros 7)
(0 1 2 3 4 5 6 7)
(a) O seu procedimento é um procedimento recursivo? Porquê?
(b) O seu procedimento gera um processo iterativo ou recursivo? Porquê?
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
55
(c) Se o seu procedimento gera um processo iterativo, escreva um que gere um processo
recursivo. Se gera um processo recursivo, escreva um que gere um processo iterativo.
34. (4) O Crivo de Eratóstenes é um algoritmo para calcular números primos que, segundo
a tradição, foi criado pelo matemático grego Eratóstenes (c. 285-194 a.C.), o terceiro
bibliotecário-chefe da Biblioteca de Alexandria. O algoritmo calcula os números primos
inferiores a n. Para isso, começa-se por criar uma lista com todos os inteiros positivos de
√
2 a n e seleccionar o número 2. Enquanto o número seleccionado for menor que n: (a)
removem-se da lista todos os múltiplos desse número; (b) passa-se ao número seguinte
√
na lista. No final do algoritmo, quando o número seleccionado for superior a n, a lista
apenas contém números primos.
Escreva um procedimento que recebe um inteiro positivo n e calcula a lista de números
primos inferiores a n de acordo com o Crivo de Eratóstenes.
Sugestão: Defina um procedimento remove-multiplos que dado uma lista lst e um
número inteiro n, remove da lista todos os múltiplos de n.
> (lista-primos 20)
(2 3 5 7 11 13 17 19)
> (lista-primos 100)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
5.2.6
Árvores Binárias
Definições e Notação
Nesta secção deve considerar os seguintes procedimentos sobre árvores binárias:
• (nova-arv) cria uma árvore vazia.
• (cria-arv r arve arvd) cria uma árvore binária com raiz r, árvore esquerda arve e
árvore direita arvd.
• (raiz arv) dada uma árvore binária arv devolve a sua raiz.
• (arv-esq arv) dada uma árvore binária arv devolve a sua árvore esquerda.
• (arv-dir arv) dada uma árvore binária arv devolve a sua árvore direita.
• (arvore-vazia? arv) devolve verdadeiro se a árvore binária arv é vazia e falso no
caso contrário.
• (arvore? arg) devolve verdadeiro se arg for uma árvore binária e falso no caso contrário.
• (arvores=? arv1 arv2) devolve verdadeiro se as árvores binárias arv1 e arv2 forem
iguais e falso no caso contrário.
Um nó de uma árvore a é a raiz de uma das sub-árvores de a. As raízes das sub-árvores
esquerda e direita de um nó r dizem-se os filhos de r. Neste caso r diz-se o pai dos dois nós.
Dois nós dizem-se irmãos se tiverem o mesmo pai. Uma folha de uma árvore é um nó sem
filhos.
A profundidade de um nó é o comprimento do caminho desde a raiz até ele. A profundidade
de uma árvore é o comprimento do caminho desde a raiz até ao nó mais profundo. O nó d
diz-se descendente de a se existir um caminho na árvore de a para d e a profundidade de a é
menor que a profundidade de d. Um nó a diz-se ascendente de d se d for descendente de a.
56
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
O tamanho de um nó é o número de seus descendentes, incluindo o próprio. O tamanho
de uma árvore é o tamanho da sua raiz.
Suponha definidas as seguintes árvores binárias
(define a1 (cria-arv 3
(cria-arv 2
(cria-arv
(cria-arv
(cria-arv 5
(cria-arv
(cria-arv
5 (nova-arv) (nova-arv))
7 (nova-arv) (nova-arv)))
1 (nova-arv) (nova-arv))
6 (nova-arv) (nova-arv)))))
(define a2 (cria-arv 10
(cria-arv 12
(nova-arv)
(nova-arv))
(cria-arv 1
(cria-arv 8 (nova-arv) (nova-arv))
(cria-arv 2 (nova-arv) (nova-arv)))))
(define a3 (cria-arv 5
(nova-arv)
(cria-arv 10
(cria-arv 8 (nova-arv) (nova-arv))
(cria-arv 10 (nova-arv) (nova-arv)))))
cujas representações gráficas são dadas por
10
3
2
5
12
5
7 1
6
5
1
8
10
2
8
10
Exercícios
1. (1) Escreva um procedimento folha? que recebe uma árvore binária, e devolve verdadeiro se a árvore for uma folha e falso no caso contrário.
> (folha? (arv-esq a1))
#f
> (folha? (arv-esq a2))
#t
2. (1) Escreva um procedimento tamanho que recebe uma árvore binária, e devolve o
número de nós da árvore.
> (tamanho a1)
7
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
57
3. (1) Escreva um procedimento soma-arvore que recebe uma árvore binária contendo
números inteiros, e devolve a soma de todos os nós da árvore.
> (soma-arvore a1)
29
4. (1) Escreva um procedimento procura? que recebe uma árvore binária contendo números inteiros arv e um número inteiro n, e devolve verdadeiro se n ocorre num dos nós
da árvore e falso no caso contrário.
> (procura? a1 8)
#f
> (procura? a2 8)
#t
5. (1) Escreva um procedimento todos-pares? que recebe uma árvore binária contendo
números inteiros, e devolve verdadeiro se a árvore for constituída exclusivamente por
números pares e falso no caso contrário.
> (todos-pares? a3)
#f
> (todos-pares? (arv-dir a3))
#t
6. (1) Escreva um procedimento conta-pares-arvore que recebe uma árvore binária
contendo números inteiros, e conta quantos números pares ocorrem na árvore.
> (conta-pares-arvore a1)
2
7. (1) Escreva um procedimento numero-folhas que recebe uma árvore binária, e devolve
o número de folhas da árvore.
> (numero-folhas a1)
4
> (numero-folhas a2)
3
> (numero-folhas a3)
2
8. (1) Escreva um procedimento profundidade que recebe uma árvore binária, e devolve
a profundidade da árvore.
> (profundidade a2)
3
9. (2) Escreva um procedimento pai? que recebe uma árvore binária contendo números
inteiros e dois números inteiros p e f, e devolve verdadeiro se p for pai de f na árvore e
falso no caso contrário.
58
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
> (pai? a1 3 7)
#f
> (pai? a1 3 9)
#f
> (pai? a1 5 1)
#t
10. (2) Escreva um procedimento filho? que recebe uma árvore binária contendo números
inteiros e dois números inteiros f e p, e devolve verdadeiro se f for filho de p na árvore
e falso no caso contrário.
> (filho?
#f
> (filho?
#f
> (filho?
#t
> (filho?
#t
a1 6 3)
a1 9 3)
a1 5 2)
a1 5 3)
11. (2) Escreva um procedimento irmaos? que recebe uma árvore binária contendo números inteiros e dois números inteiros n e m, e devolve verdadeiro se os números forem
irmãos na árvore e falso no caso contrário.
> (irmaos? a1 2 7)
#f
> (irmaos? a1 2 5)
#t
12. (2) Escreva um procedimento ascendente? que recebe uma árvore binária contendo
números inteiros e dois números inteiros a e d, e devolve verdadeiro se a for ascendente
de d na árvore e falso no caso contrário.
Sugestão: Utilize o procedimento procura? definido no exercício 4.
> (ascendente?
#t
> (ascendente?
#f
> (ascendente?
#t
> (ascendente?
#t
a1 3 6)
a1 3 9)
a1 2 5)
a1 3 5)
13. (2) Escreva um procedimento descendente? que recebe uma árvore binária contendo
números inteiros e dois números inteiros d e a, e devolve verdadeiro se d for descendente
de a na árvore e falso no caso contrário.
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
59
> (descendente? a1 6 5)
#t
> (descendente? a1 7 3)
#t
> (descendente? a1 2 5)
#f
14. (2) Uma árvore binária diz-se própria se todos os seus nós têm dois filhos ou são
folhas. Escreva um procedimento arv-propria? que recebe uma árvore binária, e
devolve verdadeiro se a árvore for própria e falso no caso contrário.
> (arv-propria? a1)
#t
> (arv-propria? a2)
#t
> (arv-propria? a3)
#f
15. (2) Uma árvore binária diz-se perfeita se é própria e todas as suas folhas estão ao
mesmo nível. Escreva um procedimento arv-perfeita? que recebe uma árvore binária,
e devolve verdadeiro se a árvore for perfeita e falso no caso contrário.
Sugestão: Utilize o procedimento profundidade definido no exercício 8.
> (arv-perfeita? a1)
#t
> (arv-perfeita? a2)
#f
> (arv-perfeita? a3)
#f
16. (3) Uma árvore binária diz-se balanceada se for própria e todas as suas folhas diferem
no máximo de um nível. Escreva um procedimento arv-balanceada? que recebe uma
árvore binária, e devolve verdadeiro se a árvore for balanceada e falso no caso contrário.
Sugestão: Utilize o procedimento profundidade definido no exercício 8.
> (arv-balanceada? a1)
#t
> (arv-balanceada? a2)
#t
> (arv-balanceada? a3)
#f
17. (3) Escreva um procedimento maximo que recebe uma árvore binária não vazia contendo
números inteiros, e devolve o maior elemento da árvore.
> (maximo a1)
7
60
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
18. (3) Escreva um procedimento minimo que recebe uma árvore binária não vazia contendo
números inteiros, e devolve o menor elemento da árvore.
> (minimo a2)
1
19. (3) Escreva um procedimento mais-profundo que recebe uma árvore binária não vazia,
e devolve o nó mais profundo da árvore. Caso existam vários à mesma profundidade
deverá devolver o mais à esquerda na árvore.
Sugestão: Utilize o procedimento profundidade definido no exercício 8.
> (mais-profundo a1)
5
> (mais-profundo a2)
8
20. (4) Escreva um procedimento profundidade-minima que recebe uma árvore binária
não vazia contendo números inteiros e um número inteiro n, e devolve a profundidade
mínima a que n ocorre na árvore. Caso o número não ocorra na árvore deverá devolver
falso.
Sugestão: Utilize o procedimento mais-profundo definido no exercício 19.
> (profundidade-minima a1 5)
2
> (profundidade-minima a1 1)
3
> (profundidade-minima a1 9)
#f
21. (2) Escreva um procedimento lista-folhas que recebe uma árvore binária, e devolve
a lista com todas as suas folhas começando da mais à esquerda para a mais à direita.
Sugestão: Utilize o procedimento junta definido no exercício 13.
> (lista-folhas a2)
(12 8 2)
> (lista-folhas a3)
(8 10)
22. (2) Escreva um procedimento espelha que recebe uma árvore binária e devolve uma
nova árvore binária idêntica à recebida, mas em que em cada nível da árvore se trocou
a árvore esquerda com a direita, mantendo-se a raiz.
> (espelha a1)
deve devolver a árvore cuja representação gráfica é
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
61
3
5
6
2
1 7
5
23. (2) Escreva um procedimento substitui que recebe uma árvore binária contendo
números inteiros e dois números inteiros v (velho) e n (novo), e devolve a árvore que
resulta de substituir todas as ocorrências de v por n.
> (substitui a1 5 8)
deve devolver a árvore cuja representação gráfica é
3
2
8
8
7 1
6
24. (2) Escreva um procedimento poda que recebe uma árvore binária, e devolve a árvore
que resulta de remover todas as folhas da árvore.
> (poda a2)
deve devolver a árvore cuja representação gráfica é
10
1
25. (4) Escreva um procedimento promove-irmao que recebe uma árvore binária contendo
números inteiros, e que em cada uma das suas sub-árvores coloca o irmão maior como
raiz da árvore direita.
> (promove-irmao a2)
deve devolver a árvore cuja representação gráfica é
10
1
12
2
8
62
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
26. (4) Escreva um procedimento promove-descendente que recebe uma árvore binária
contendo números inteiros, e que em cada uma das suas sub-árvores coloca o seu maior
elemento na raiz. Nos casos em que há troca da raiz r por m, então r deverá ocupar o
lugar onde m estava.
Sugestão: Defina um procedimento substitui1 que recebe uma árvore arv e dois
números v e n e substitui uma única ocorrência de v por n na árvore arv.
> (promove-descendente a1)
deve devolver a árvore cuja representação gráfica é
7
6
5
2
3 1
5
27. (4) Uma árvore binária contendo números inteiros diz-se de procura se a sua raiz é
maior que todos os elementos da sua sub-árvore esquerda, menor ou igual que todos os
elementos da sua sub-árvore direita, e o mesmo se passa para todas as suas sub-árvores.
Escreva um procedimento arv-procura? que recebe uma árvore binária, e devolve
verdadeiro se a árvore for uma árvore binária de procura e falso no caso contrário.
> (arv-procura? a1)
#f
> (arv-procura? a3)
#t
28. (2) Escreva um procedimento existe-arv-procura? que recebe uma árvore binária
de procura contendo números inteiros e um número inteiro n, e devolve verdadeiro se o
número n ocorre num dos nós da árvore e falso no caso contrário.
Nota: O seu procedimento deve tirar partido do facto de receber uma árvore binária
de procura e não uma árvore binária qualquer.
> (existe-arv-procura? a3 8)
#t
> (existe-arv-procura? a3 9)
#f
29. (3) Escreva um procedimento insere-arvore-procura que recebe uma árvore binária
de procura contendo números inteiros e um número inteiro n, e devolve a árvore binária
de procura que resulta de inserir o número n na árvore.
> (insere-arvore-procura a3 9)
5.2. EXERCÍCIOS DE PROGRAMAÇÃO
63
deve devolver a árvore cuja representação gráfica é
5
10
8
10
9
30. (2) Escreva um procedimento cria-arvore-procura que recebe zero ou mais números
inteiros, e devolve uma árvore binária de procura criada a partir desses argumentos. O
primeiro argumento, caso exista, deverá ser a raiz da árvore.
> (cria-arvore-procura 2 1 5 3)
deve devolver a árvore cuja representação gráfica é
2
1
5
3
64
CAPÍTULO 5. ABSTRACÇÃO DE DADOS
Capítulo 6
Procedimentos de ordem superior
6.1
Exercícios de revisão
1. Diga quando é que em programação se diz que um objecto computacional é um cidadão
de primeira classe.
2. Diga o que é um procedimento de ordem superior e quais são as suas vantagens.
6.2
Exercícios de programação
6.2.1
Procedimentos que recebem procedimentos
1. (1) Escreva um procedimento anónimo que recebe um procedimento e um número e
devolve o resultado de aplicar o procedimento ao triplo do quadrado do número.
2. O procedimento somatorio
(define (somatorio calc-termo lim-inf proximo lim-sup)
(if (> lim-inf lim-sup)
0
(+ (calc-termo lim-inf)
(somatorio calc-termo
(proximo lim-inf)
proximo
lim-sup))))
é apenas o mais simples de um vasto número de abstracções semelhantes que podem
ser capturadas por procedimentos de ordem superior. Por exemplo, podemos usar o
procedimento somatorio para somar os quadrados dos múltiplos de 3 entre 9 e 21:
(somatorio (lambda (x) (expt x 2))
9
(lambda (x) (+ x 3))
21)
66
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
(a) (2) Diga o que fazem as seguintes utilizações desse procedimento:
i. (somatorio (lambda (x) x) 4 add1 500)
ii. (somatorio (lambda (x) (sqrt x)) 5 (lambda (x) (+ x 5)) 500)
iii. (somatorio (lambda (x) (somatorio (lambda (x) x) 1 add1 x)) 1 add1
5)
(b) (2) Mostre como é que o procedimento somatorio poderia ser definido gerando um
processo iterativo (em vez de gerar um processo recursivo, como faz actualmente).
(c) (2) Defina um procedimento piatorio que calcula o produto dos termos de uma
função entre dois limites especificados.
(d) (2) Mostre como definir o factorial em termos da utilização do procedimento
piatorio.
3. A conversão de valores é uma operação comum em programação. Por exemplo, convertemse temperaturas em graus Farenheit para graus Centígrados, horas locais em Lisboa para
horas locais em Nova Iorque, etc.
(a) (2) Escreva um procedimento converte que recebe o procedimento correspondente à função de conversão e o valor a converter e devolve o valor convertido. Por
exemplo, se far-cent for o procedimento correspondente à função de conversão de
graus Farenheit em Centígrados definido como
(define (far-cent f)
(/ (* 5 (- f 32)) 9))
a avaliação de (converte far-cent 32) tem o valor 0.
(b) (2) Escreva um procedimento lis-ny para converter uma hora local em Lisboa
(um número inteiro entre 0 e 23) para a hora local em Nova Iorque (onde são
menos cinco horas do que em Lisboa). Tenha cuidado com a passagem da meia
noite. Utilize o procedimento converte da alínea anterior e o procedimento lis-ny
para mostrar qual a hora em Nova Iorque quando são 3 da manhã em Lisboa.
4. (3) Escreva um procedimento nenhum-p? que recebe um número inteiro positivo n e
um predicado p, e devolve verdadeiro se nenhum inteiro positivo menor que n satisfaz p
e falso no caso contrário.
> (nenhum-p? 87 (lambda (x) (= 0 (remainder x 100)))
#t
> (nenhum-p? 187 (lambda (x) (= 0 (remainder x 100)))
#f
5. (1) Escreva os procedimentos dos exercícios 18 e 19 da secção 2.2.3 (primos-entre-si?
e divisor-fraco?) utilizando o procedimento nenhum-p?.
6. (1) Escreva os procedimentos dos exercícios 10, 11, 12 e 13 da secção 3.2 (quadrado-perfeito?,
primo?, livre-quadrados?, poderoso?) utilizando o procedimento nenhum-p.
6.2. EXERCÍCIOS DE PROGRAMAÇÃO
67
7. (2) Escreva um procedimento conta-p que recebe um número inteiro positivo n e um
predicado p, e devolve o número de inteiros positivos menores ou iguais a n que satisfazem
p.
> (conta-p 87 (lambda (x) (= 0 (remainder x 100)))
0
> (conta-p 487 (lambda (x) (= 0 (remainder x 100)))
4
8. (1) Escreva os procedimentos dos exercícios 6, 7 e 8 da secção 2.2.3 (numero-divisores,
numero-primos-menores e numero-divisores-primos) utilizando o procedimento conta-p.
9. (2) Escreva um procedimento soma-p que recebe um número inteiro positivo n e um
predicado p, e devolve a soma de todos os inteiros positivos menores do que n que
satisfazem p.
> (soma-p 87 (lambda (x) (= 0 (remainder x 100)))
0
> (soma-p 487 (lambda (x) (= 0 (remainder x 100)))
1000
10. (1) Escreva os procedimentos dos exercícios 2 e 9 da secção 2.2.3 (somatorio e soma-divisores)
utilizando o procedimento soma-p.
11. (3) Escreva um procedimento nesimo-p que recebe um número inteiro positivo n e um
predicado p, e devolve o n-ésimo elemento que satisfaz p.
> (nesimo-p 4 (lambda (x) (= 0 (remainder x 100)))
400
> (nesimo-p 4 even?)
8
12. (1) Escreva os procedimentos dos exercícios 22, 23, 24, e 25 da secção 3.2 (nesimo-primo,
nesimo-primo-mersenne, k-divisor, e kesimo-factor-primo) utilizando o procedimento nesimo-p.
13. (3) Escreva um procedimento soma-digitos-p que recebe um número inteiro positivo
n e um predicado p, e devolve a soma de todos os dígitos de n que satisfazem p.
> (soma-digitos-p 97 (lambda (x) (< x 5)))
0
> (soma-digitos-p 1452 (lambda (x) (< x 5)))
7
14. (1) Escreva os procedimentos dos exercícios 14 e 15 da secção 2.2.3 (soma-digitos e
soma-digitos-pares) utilizando o procedimento soma-digitos-p.
68
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
15. (3) Escreva um procedimento existe-digito-p? que recebe um número inteiro positivo n e um predicado p, e devolve verdadeiro se ocorrer um dígito em n que satisfaça p
e falso no caso contrário.
> (existe-digito-p? 234 (lambda (x) (< x 5)))
#t
> (existe-digito-p? 558 (lambda (x) (< x 5)))
#f
16. (1) Escreva o procedimento do exercício 29 da secção 3.2 (existe-digito?) utilizando
o procedimento existe-digito-p?.
17. (4) Escreva um procedimento digitos-p que recebe um número inteiro positivo n e
um predicado p, e devolve o número composto apenas pelos dígitos de n que satisfazem
p. Se nenhum dos dígitos de n satisfizer p deve devolver 0.
> (digitos-p 9558 (lambda (x) (< x 5)))
0
> (digitos-p 2458 (lambda (x) (< x 5)))
24
18. (1) Escreva o procedimento do exercício 16 da secção 2.2.3 (digitos-impares) utilizando o procedimento digitos-p.
19. (2) Escreva um procedimento conta que recebe uma lista e um predicado unário, e
devolve o número de elementos da lista que satisfazem o predicado.
> (conta ’(4 5 6) (lambda(x) (> x 5)))
1
20. (1) Escreva os procedimentos dos exercícios 3, 4, e 5 da secção 5.2.5 (conta-pares,
conta-menores, e numero-ocorrencias) utilizando o procedimento conta.
21. (2) Escreva um procedimento todos? que recebe uma lista e um predicado unário, e
devolve verdadeiro caso todos os elementos da lista satisfaçam o predicado e falso no
caso contrário.
> (todos? ’(4 5 6) (lambda(x) (> x 5)))
#f
> (todos? ’(4 5 6) (lambda(x) (>= x 4)))
#t
22. (1) Escreva o procedimento do exercício 6 da secção 5.2.5 (todos-pares) utilizando o
procedimento todos?.
23. (2) Escreva um procedimento existe? que recebe uma lista e um predicado unário, e
devolve verdadeiro se existir pelo menos um elemento da lista que satisfaça o predicado
e falso no caso contrário.
6.2. EXERCÍCIOS DE PROGRAMAÇÃO
69
> (existe? ’(4 5 6) (lambda(x) (> x 5)))
#t
> (existe? ’(4 5 6) (lambda(x) (>= x 4)))
#t
> (existe? ’(4 5 6) (lambda(x) (< x 4)))
#f
24. (1) Escreva o procedimento do exercício 7 da secção 5.2.5 (ocorre-lista) utilizando
o procedimento existe?.
25. (2) Escreva um procedimento nem-todos? que recebe uma lista e um predicado unário,
e devolve verdadeiro caso exista pelo menos um elemento da lista que não satisfaz o
predicado e falso no caso contrário.
> (nem-todos? ’(2 4 5 6) even?)
#t
> (nem-todos? ’(2 4 6) even?)
#f
26. (2) Escreva um procedimento transforma que recebe uma lista e um procedimento
unário f, e devolve a lista que resulta de aplicar o procedimento a todos os elementos
da lista.
> (transforma ’(4 3 2 4) (lambda(x) (- x 1)))
(3 2 1 3)
> (transforma ’(4 3 2 4) (lambda(x) (>= x 4)))
(#t #f #f #t)
27. (2) Escreva os procedimentos dos exercícios 9 e 10 da secção 5.2.5 (quadrados-lista
e substitui) utilizando o procedimento transforma (este é apresentado na Página 207
do livro).
28. (2) Escreva um procedimento filtra que recebe uma lista l e um predicado p, e
devolve a lista que resulta de ficar com todos os elementos da lista l que satisfazem o
predicado p.
> (filtra ’(4 3 2 1 4) (lambda(x) (< 1 x 4)))
(3 2)
29. (2) Escreva os procedimentos dos exercícios 17, 18, 19, e 20 da secção 5.2.5 (selecciona-pares,
selecciona-menors, selecciona-primos, e remove-elemento) utilizando o procedimento filtra.
30. (2) Escreva um procedimento posicoes-p que recebe uma lista e um predicado, e
devolve a lista de todas as posições em que o elemento da lista satisfaz o predicado.
> (posicoes-p ’(4 3 2 2 1 4) (lambda(x) (< x 3)))
(3 4 5)
> (posicoes-p ’(4 3 2 2 1 4) (lambda(x) (> x 4)))
()
70
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
31. (2) Escreva os procedimentos dos exercícios 22 e 23 da secção 5.2.5 (posicoes-lista
e posicoes-dos-pares) utilizando o procedimento posicoes-p.
32. (2) Escreva um procedimento da-pares que recebe um procedimento, um valor e uma
lista e que devolve uma lista de pares em que cada par contém o elemento da lista seguido
do valor obtido da aplicação do procedimento ao valor e ao elemento da lista respectivo.
> (da-pares (lambda (x y) (+ x y)) 3 ’(2 4 3 5 6))
((2 5) (4 7) (3 6) (5 8) (6 9))
> (da-pares (lambda (x y) (* x y)) 2 ())
()
> (da-pares (lambda (x y) (* x y)) 9 ’(1 3))
((1 9) (3 27))
33. (2) Escreva um procedimento de ordem superior chamado lista-de-a-n-pred que
recebe dois números inteiros (de e ate) e um predicado aplicável a inteiros (pred) e que
devolve a lista de todos os inteiros ente de e ate que satisfazem o predicado pred. Por
exemplo:
> (lista-de-a-n-pred 1 10 even?)
(2 4 6 8 10)
> (lista-de-a-n-pred 1 10 (lambda (x) #t))
(1 2 3 4 5 6 7 8 9 10)
34. (4) Usando o procedimento lista-de-a-n-pred e outros procedimentos de ordem
superior, escreva um procedimento correspondente ao crivo de Eratóstenes.
35. (2) Escreva um procedimento conta-arvore que recebe uma árvore binária e um
predicado p que se aplica a cada um dos nós da árvore, e conta quantos elementos
da árvore satisfazem p.
> (conta-arvore a1 odd?)
5
> (conta-arvore a1 (lambda (x) (> x 5)))
2
36. (2) Escreva os procedimentos dos exercícios 2, 4, e 6 da secção 5.2.6 (tamanho, procura?,
e conta-pares-arvore) utilizando o procedimento conta-arvore.
37. (2) Escreva um procedimento conta-subarvore que recebe uma árvore binária a e um
predicado p que se aplica a árvores, e conta quantas subárvores de a satisfazem p.
> (define (dois-filhos? a)
(and (not (arvore-vazia? a))
(not (arvore-vazia? (arv-esq a)))
(not (arvore-vazia? (arv-dta a)))))
> (conta-subarvore a1 dois-filhos?)
6.2. EXERCÍCIOS DE PROGRAMAÇÃO
71
3
> (conta-subarvore a2 dois-filhos?)
2
> (conta-subarvore a3 dois-filhos?)
1
38. (2) Escreva os procedimentos dos exercícios 7, 9, e 10 da secção 5.2.6 (numero-folhas,
pai?, filho?) utilizando o procedimento conta-subarvore.
39. (2) Escreva um procedimento aplica-f-arvore que recebe uma árvore binária e um
procedimento f que se aplica à raiz de uma árvore, e devolve a árvore que resulta de
aplicar o procedimento a todos os elementos da árvore.
> (aplica-f-arvore a2 (lambda(x) (* x x)))
deve devolver a árvore cuja representação gráfica é
100
144
1
64
4
40. (2) Escreva o procedimento do exercício 23 da secção 5.2.6 (substitui) utilizando o
procedimento transforma.
6.2.2
Procedimentos que produzem procedimentos
1. (1) A composição de duas funções de um argumento, f (x) e g(x), é a função f (g(x)).
Escreva um procedimento fn-composta que recebe como argumentos dois procedimentos
correspondentes a funções de um argumento e que devolve o procedimento correspondente à composição dos seus argumentos.
Por exemplo, com o seu procedimento, seria gerada a seguinte interacção:
> (define (quadrado x) (* x x))
> (define (soma-6 y) (+ 6 y))
> ((fn-composta quadrado soma-6) 3)
81
2. (a) (2) Escreva um procedimento fn-soma que receba como argumentos dois procedimentos correspondentes a funções reais de variável real, f e g, e devolva o
procedimento correspondente à função correspondente à soma de f com g.
Por exemplo, com este procedimento podemos gerar a interacção:
> (define (f1 x) (+ x 3))
> (define (f2 y) (* y 10))
> ((fn-soma f1 f2) 12)
135
72
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
(b) (2) Podemos pensar numa generalização do procedimento do exercício anterior,
fornecendo a operação a realizar entre as funções f e g. Por exemplo, se a operação
for a adição, o procedimento corresponde ao anterior, devolvendo f (x) + g(x); no
entanto, se a operação for a potência, o procedimento devolve f (x)g(x) .
Escreva um procedimento aplica-op que recebe como argumentos uma operação
(aplicável a dois argumentos) e duas funções reais de variável real e que devolve o
procedimento que corresponde a aplicar a operação fornecida às duas funções.
Por exemplo,
> (define (f1
> (define (f2
> ((aplica-op
135
> ((aplica-op
1800
x) (+ x 3))
y) (* y 10))
+ f1 f2) 12)
* f1 f2) 12)
3. (2) Defina um procedimento funcao-i que recebe procedimentos para calcular as funções reais de variável real f , g e h e devolve um procedimento que se comporta como a
seguinte função matemática:
i(x) = 2f (x)2 + 3g(x)3 − h(x2 )
4. (2) Escreva um procedimento nega que recebe como argumento um predicado de dois
argumentos e que devolve o procedimento correspondente à negação do seu argumento.
> ((nega >) 2 3)
#t
> ((nega >) 2 2)
#t
> ((nega <=) 4 5)
#f
5. (2) Escreva o procedimento conjuncao que recebe dois predicados de um argumento
cada, e devolve um novo predicado de um argumento que verifica se esse argumento
satisfaz ambos os predicados recebidos originalmente.
> (define
> (par>5?
#f
> (par>5?
#t
> (par>5?
#f
par>5? (conjuncao even? (lambda (x) (> x 5))))
4)
8)
9)
6. (a) (2) Escreva um procedimento faz-arredonda que recebe um inteiro n, e devolve
um procedimento que recebe um argumento real e o arredonda para n casas decimais.
6.2. EXERCÍCIOS DE PROGRAMAÇÃO
73
(b) (2) Utilize o procedimento faz-arredonda para definir o procedimento arredonda-3,
que recebe um real e o arredonda para 3 casas decimais.
> (arredonda-3 1.23456)
1.235
7. (2) Escreva um procedimento que recebe um número e devolve um procedimento que
recebe outro número e o multiplica pelo primeiro.
> (define mult5 (cria-multiplicador 5))
> (mult5 2)
10
8. (2) Considere as seguintes definições para um procedimento que devolve a primeira
derivada de uma função:
(define (derivada f)
(lambda (x)
(/ (- (f (+ x dx)) (f x))
dx)))
(define dx 0.00001)
Com base na definição anterior escreva um procedimento que recebe um procedimento
correspondente a uma função e um inteiro positivo n (n >= 1) e devolve a derivada de
ordem n da função. Lembre-se que a derivada de ordem n de uma função é a derivada
da derivada de ordem n - 1. Utilize o procedimento derivada.
9. (2) Escreva um procedimento rasto que recebe uma cadeia de caracteres correspondendo ao nome de um procedimento, e um procedimento de um argumento. O procedimento rasto devolve um procedimento de um argumento que escreve no écran (usando
o procedimento primitivo display) a indicação de que o procedimento foi avaliado e o
valor do seu argumento, escreve também o resultado do procedimento, e devolve o valor
de aplicar o procedimento original ao argumento recebido. Por exemplo, partindo do
princípio que o procedimento quadrado foi definido, podemos gerar a seguinte interacção:
> (define rasto-quadrado (rasto "quadrado" quadrado))
> (rasto-quadrado 4)
Avaliação de quadrado, com o argumento 4
Resultado 16
16
>
10. A sequência de Fibonacci (ou números de Fibonacci) é definida recursivamente do seguinte modo:

se n = 0
 0
1
se n = 1
f ib(n) =

f ib(n − 1) + f ib(n − 2) se n > 1
74
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
ou seja, depois dos dois termos iniciais, cada termo da sequência corresponde à soma
dos dois termos anteriores.
Sequências semelhantes à de Fibonacci, mas com termos iniciais diferentes, têm sido descobertas como transcrevendo vários aspectos da natureza. Um dos exemplos, a sequência
de Lucas, em honra ao Matemático francês François Lucas (1842–1891), corresponde à
sequência 3, 1, 4, 5, 9, . . ..
A sequência de Fibonacci pode ser generalizada a uma colecção de sequências, parametrizadas com base nos dois primeiros termos, a e b e definidas através da seguinte
expressão:

se n = 0
 a
b
se n = 1
Fa,b (n) =

Fa,b (n − 1) + Fa,b (n − 2) se n > 1
Assim, F0,1 (n) é uma expressão designatória correspondente ao n-ésimo termo da sequência de Fibonacci, F3,1 (n), é uma expressão designatória correspondente ao n-ésimo termo
da sequência de Lucas.
(a) (2) Defina um procedimento que dê origem a um procedimento que calcula o
n-ésimo termo da sequência generalizada de Fibonacci. O seu procedimento deve
receber como argumentos os dois primeiros termos da sequência, produzindo um
procedimento de um argumento que calcula o n-ésimo termo de uma sequência
particular. O procedimento deve gerar um processo iterativo.
(b) (2) Use o procedimento do exercício anterior para gerar outro procedimento que
calcula a sequência generalizada de Fibonacci cujos dois primeiros termos são o ano
do seu nascimento e o seu número de aluno. Usando este procedimento, calcule
o termo cuja posição corresponde a 10 somado ao mês do seu nascimento. Por
exemplo, um aluno nascido em Março de 1988 e cujo número é 12345 deverá calcular
o valor de F1988,12345 (13).
(c) (2) Um dos aspectos interessantes associados às sequências de Fibonacci generalizadas corresponde ao facto de, independentemente dos valores de a e b, o limite da
razão entre um termo e o anterior quando n tende para infinito é sempre o mesmo:
Fa,b (n + 1)
=ϕ
n→∞
Fa,b (n)
lim
em que ϕ (leia-se Phi, o qual não deve ser confundido com o número π) é dado por
√
1+ 5
ϕ=
≈ 1.6180
2
Phi é um número transcendente conhecido por proporção divina, proporção áurea ou
número de ouro. A proporção divina foi recentemente glorificada no livro de Dan
Brown, O Código da Vinci. Este número, frequentemente usado nas proporções
das pinturas renascentistas, está envolvido com a natureza do crescimento. O
número ϕ pode ser encontrado na proporção em conchas, seres humanos, e até
na relação entre os machos e fêmeas de qualquer colmeia do mundo. Por esta
6.2. EXERCÍCIOS DE PROGRAMAÇÃO
75
razão, os antigos consideravam que este número tinha sido utilizado pelo Criador
do universo e chamavam-lhe a proporção divina. Esta proporção corresponde à
relação que resulta quando uma linha é dividida de tal modo que o comprimento
total da linha tem a mesma relação com o comprimento do segmento maior que o
comprimento do segmento maior tem com o comprimento do segmento menor.
Usando um método de aproximações sucessivas semelhante ao apresentado na Secção 2.4.3 do livro, escreva um procedimento de ordem superior que calcule o valor
da proporção divina com uma precisão de 10 casas decimais. O argumento do seu
procedimento deverá ser um procedimento para o cálculo da sequência de Fibonacci. O seu procedimento deverá utilizar expressões “let” para evitar cálculos
repetidos.
76
CAPÍTULO 6. PROCEDIMENTOS DE ORDEM SUPERIOR
Capítulo 7
O desenvolvimento de programas
7.1
Exercícios de revisão
1. Diga quais são as fases por que passa o desenvolvimento de um programa e o que se faz
em cada uma delas.
2. Enuncie e explique cada um dos tópicos que são habitualmente focados na documentação
de utilização que acompanha um programa.
3. Em programação podemos ter erros sintácticos e erros semânticos. Defina cada um deles
e dê exemplos.
4. Durante o desenvolvimento de um programa, após a programação da solução, segue-se
a fase de testes. Explique no que consiste a fase de testes.
5. O que é a depuração? Que tipos de depuração são efectuados nos programas e para que
tipos de erros?
6. O que é a depuração da base para o topo? Qual a sua vantagem?
7. Comente a seguinte expressão: “A documentação de um programa deve ser efectuada
após o código terminado, para garantir que não existem erros nessa mesma documentação”.
8. Escolha a única resposta correcta. A documentação de um programa:
(a) Apenas deve ser escrita após o programa ter sido concluído.
(b) É constituída por vários tipos de documentos.
(c) Não pode ser alterada na fase de manutenção.
(d) Deve ser evitada, sempre que possível, pois corresponde a um trabalho desnecessário.
9. Escolha a única resposta incorrecta. Em relação à metodologia de desenvolvimento de
programas pode dizer-se que:
(a) Na fase da programação da solução decide-se a representação para as estruturas de
informação.
78
CAPÍTULO 7. O DESENVOLVIMENTO DE PROGRAMAS
(b) A depuração lida com erros semânticos e erros sintácticos.
(c) A fase de desenvolvimento da solução recorre a uma linguagem de programação.
(d) A fase de testes nunca permite garantir a ausência completa de erros.
7.2
Exercícios de programação
1. (2) Sugira casos de teste para o procedimento seguinte:
(define (saudacao hora)
(cond ((> hora 12) "Boa tarde !")
((> hora 19) "Boa noite !")
(else "Bom dia !")))
2. (1) Com base nos casos de teste concebidos, explique qual o problema com o procedimento saudacao.
3. (2) Sugira casos de teste para o procedimento seguinte:
(define (misterio a)
(cond ((> a 0) #t)
((< a 3) #t)
((= a 1) (+ a 5))
(else (misterio (- a 2)))))
4. (1) Com base nos casos de teste concebidos, explique qual o problema com o procedimento misterio.