Exercícios para Fundamentos da Programação Utilizando Múltiplos

Exercícios paraFundamentos da ProgramaçãoUtilizando Múltiplos Paradigmas

Pedro Adão, Fausto Almeida, Ana Cardoso-Cachopo, Pedro Amaro de Matos (editores)

Departamento de Engenharia InformáticaInstituto Superior TécnicoUniversidade Técnica de Lisboa

2

3

Preâmbulo

O objectivo desta publicação é disponibilizar um conjunto de exercícios que permitam aos alu-nos da cadeira de Fundamentos de Programação da Licenciatura em Engenharia Informáticae de Computadores do Instituto Superior Técnico consolidarem os conhecimentos adquiridosao longo do semestre.

Os exercícios estão divididos de acordo com os capítulos do livro adoptado pela cadeira:“Programação Utilizando Múltiplos Paradigmas”, de João Pavão Martins e Maria dos RemédiosCravo, editado pela IST Press em 2011. Sempre que tal foi considerado relevante os exercíciosforam 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, corres-pondendo o nível 1 a exercícios muito fáceis e o nível 4 a exercícios francamente difíceis. Estainformação é apresentada dentro de um quadrado cinzento antes do enunciado do exercício aque diz respeito.

Alguns destes exercícios correspondem a exercícios propostos nas sebentas (a) Exercíciosda cadeira de Introdução à Programação, Cláudia Antunes, Ana Cardoso Cachopo, JoãoCachopo, 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 71.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Abstracção Procedimental 112.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.1 Avaliação de Expressões . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.2 Definição de Procedimentos . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Recursão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2.4 Valores aproximados de funções . . . . . . . . . . . . . . . . . . . . . . . 23

3 Processos gerados por procedimentos 253.1 Exercícios de revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 Exercícios de programação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5

6 CONTEÚDO

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 processocomputacional?

2. O que é um algoritmo? Explique cada uma das suas propriedades: precisão, simplicidadee níveis de abstracçã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 à suaescolha.

5. Em que consiste a abstracção? Qual a sua vantagem?

6. Explique em que consiste o ciclo “lê-avalia-escreve”.

7. O que é a sintaxe e 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 explicandoinformalmente 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 Sobre-vivê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. (2) Traduza as seguintes expressões para notação prefixa e calcule o seu valor utilizandoo interpretador do Scheme. Mostre a árvore de avaliação para cada uma delas utilizandoo 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)

4. (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)

5. (1) Suponha que as seguintes expressões são avaliadas pelo Scheme. Na linha imedia-tamente a seguir a cada uma delas diga o que é escrito pelo interpretador do Scheme (sea 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. Osdois olhos são círculos de raio 1 recortados, o nariz é um quarto de círculo de raio 3recortado e a boca corresponde a meio círculo de raio 3, também recortado. Escrevauma 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-Bocapara 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. Digao que é escrito pelo interpretador do Scheme. Se a avaliação de alguma das expressõesder 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


1. Diga qual a diferença entre uma função matemática e um procedimento em Scheme parao 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âmetrosconcretos e quando e como é que os parâmetros formais são associados com os parâmetrosconcretos.

3. Utilizando a notação BNF, apresente a definição de uma expressão lambda. Expliquecada 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 numambiente?


2.2.1 Avaliação de Expressões

1. (1) Avalie as seguintes formas. Se alguma das avaliações der origem a um erro, expliquequal 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 queestas são fornecidas ao avaliador do Scheme pela ordem apresentada (e consequentementecada forma é dependente das anteriores).

Se a avaliação de uma forma não produzir resultados escreva -nada-. Se a avaliação deuma 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 funcionamentodeste 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 com-binação, desenhe a árvore que representa o funcionamento deste procedimento com aavaliaçã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 combi-nação, desenhe as árvores que representam o funcionamento destes procedimentos coma avaliação de (g 3) e de (h 3).


6. (2) Repare que o nosso modelo de avaliação permite a existência de combinações cujosoperadores são expressões compostas. Use esta observação para descrever o comporta-mento 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 algumadas 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 em Scheme um procedimento anónimo que soma dois ao seu argumento.

2. (1) Escreva em Scheme um procedimento anónimo para representar a função de umargumento (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 em Scheme o procedimento dobro que devolve o dobro do seu argumento.

1Exercício 1.4 de Abelson H., Sussman G. J., e Sussman J., Structure and Interpretation of ComputerPrograms, 2a Edição, p. 21, 1996.


5. (1) Escreva em Scheme o procedimento metade que recebe um número inteiro positivoe devolve um número racional que corresponde a metade do seu argumento.

6. (1) Escreva um procedimento em Scheme chamado minutos->horas que recebe uminteiro correspondente a um certo número de minutos e que devolve um número real quetraduz o número de horas correspondentes ao seu argumento.

> (minutos->horas 120)2.0> (minutos->horas 10)0.16666666666666666

7. (2) Escreva em Scheme o procedimento digitos->numero que recebe como argumen-tos três dígitos e produz o número inteiro de três algarismos constituído pelos seusargumentos e pela ordem em que aparecem.

> (digitos->numero 3 2 8)328

8. (1) Escreva um procedimento chamado area-circulo que calcula a área de um circulocujo 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 proce-dimento area-coroa que calcula a área de uma coroa circular de raio interior r1 e raioexterior r2.

10. (1) Escreva em Scheme um procedimento anónimo, que recebe dois números e devolveo maior deles.

11. (1) Defina em Scheme o procedimento media que recebe dois argumentos que devemser números e devolve o número real que corresponde à média dos seus argumentos.

12. (1) Escreva um procedimento em Scheme, chamado sinal, que receba um inteiro edevolva 1, −1 ou 0, caso o número seja, respectivamente, maior, menor ou igual a zero.

13. (1) Escreva em Scheme o procedimento intermedio que recebe três números e devolveo número com o valor intermédio.

14. (3) Escreva um procedimento em Scheme, chamado quant->qual, que recebe um real,representando uma nota quantitativa de um aluno (entre 0 e 20), e a transforma numaconstante do tipo cadeia de caracteres que corresponde a uma nota qualitativa, de acordocom a tabela

Nota Notaquantitativa qualitativa

18 a 20 Muito Bom14 a 17 Bom10 a 13 Suficiente5 a 9 Mediocre0 a 4 Mau


A nota recebida deverá ser convertida para um número inteiro, antes da conversão paraa nota qualitativa.

15. (1) Escreva um procedimento em Scheme que recebe as notas de um aluno de umacadeira C1 (nota do projecto, média dos trabalhos das práticas, nota do teste, e nota doexame final) e calcula a sua nota final de acordo com as seguintes regras:

(a) A nota na cadeira será calculada por uma média ponderada da classificação obtidanas provas realizadas, com os seguintes pesos: Projecto, 0,25; Trabalhos de casa eaulas práticas, 0.10; Teste, 0.2; Exame final 0.45.

(b) Para obter aprovação na cadeira, 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 cadeiraterá de ser superior a 9,5 valores.

O seu procedimento deve devolver a nota final da cadeira (um inteiro) no caso de o alunoter sido aprovado ou zero no caso do aluno ter sido reprovado.

16. (1) Utilizando os procedimentos desenvolvidos nos exercícios 14 e 15, escreva um pro-cedimento em Scheme que recebe as notas de um aluno da cadeira C1 (nota do projecto,média dos trabalhos das práticas, nota do teste, e nota do exame final) e calcula a suanota qualitativa final.

17. (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 aparte 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 devalor 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

18. (2) Escreva em Scheme um procedimento chamado cinco? que tem o valor verdadeiro,apenas se o seu argumento for 5. Não utilize o if, nem o cond, nem #t nem #f.

19. (2) Escreva em Scheme um procedimento (entre? val x y) que devolve #t, apenasno caso de val se encontrar entre x e y (x < val < y).

20. (2) Escreva em Scheme 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 sejatambém divisível por 400. Por exemplo, 1984 é bissexto, 1100 não é, e 2000 é bissexto.


> (bissexto? 2000)#t> (bissexto? 1900)#f

21. (2) Escreva em Scheme o procedimento data-valida? para verificar se uma data éválida. O seu procedimento deve receber 3 inteiros, em que o primeiro representa oano, o segundo, o mês, e o terceiro, o dia, e verificar se a data correspondente existe nocalendá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

22. (2) Se a, b e c representam as dimensões dos lados de um triângulo, escreva um pro-cedimento chamado triangulo? que devolve verdadeiro apenas se os valores de a, b ec puderem corresponder a lados de um triângulo, i.e., (a) nenhum dos valores a, b e cpoderá ser negativo ou nulo; (b) a soma de quaisquer destes valores tem de ser maior doque o terceiro (num triângulo, qualquer lado é menor do que a soma dos outros dois).

23. (2) Se a, b e c representam as dimensões dos lados de um triângulo, a área do triânguloé dada por √

s (s− a) (s− b) (s− c)

coms =

a+ b+ c

2

Escreva um procedimento em Scheme chamado area-triangulo que recebe como argu-mentos três inteiros representando as dimensões dos lados de um triângulo e que calculaa área do triângulo. Evite o cálculo repetido do valor de s. Verifique se as dimensõesfornecidas correspondem a um triângulo.

24. (2) Escreva em Scheme o procedimento classifica que recebe três números correspon-dentes aos comprimentos dos lados de um triângulo e decide se o triângulo é equilátero,isósceles ou escaleno.

25. (2) Escreva um procedimento em Scheme, chamado triangulo-rect?, que recebe trêsnúmeros inteiros positivos e determina se estes correspondem aos comprimentos doslados de um triângulo rectângulo.

O seu procedimento deverá satisfazer as seguintes condições:

• O procedimento devolve verdadeiro no caso dos valores recebidos corresponderemaos 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 dosquadrados dos outros dois.

26. (2) Escreva em Scheme o procedimento idade que recebe como argumentos seis nú-meros inteiros correspondentes a duas datas (um dia, mês, ano para cada data), sendoa primeira data correspondente à data de nascimento de uma pessoa e a segunda cor-respondente a uma data posterior, e devolve a idade (número de anos) dessa pessoa nasegunda data.

> (idade 3 3 1990 28 9 2011)21> (idade 3 3 1990 3 2 2011)20

27. (3) Escreva em Scheme o procedimento anterior? que recebe como argumentos seisnúmeros inteiros correspondentes a duas datas (um dia, mês, ano para cada data) edevolve #t se a primeira data for anterior à segunda e #f caso contrário. Não utilize oif, nem o cond, nem #t nem #f.

> (anterior? 1 12 2010 1 1 2011)#t> (anterior? 31 12 2010 1 12 2010)#f

28. (2) Escreva em Scheme o procedimento dias-p/-reveillon que recebe como argumen-tos dois números inteiros correspondentes a um mês e um ano e que retorna o númerode dias desde o dia 1 do mês dado até ao final desse ano.

29. (3) Escreva em Scheme o procedimento dias-entre-datas<365 que recebe como argu-mentos seis números inteiros correspondentes a duas datas (um dia, mês e ano para cadadata) com menos de 365 dias de diferença, sendo a primeira data anterior à segunda, edevolve o número de dias após a primeira data e até à segunda data (inclusive).

> (dias-entre-datas<365 1 12 2010 1 1 2011)31> (dias-entre-datas<365 2 12 2010 1 12 2011)364

Sugestão: Use o procedimento dias-p/-reveillon definido na alínea 28.

30. (3) Escreva em Scheme o procedimento proximo-29/2 que recebe como argumentostrês números inteiros correspondentes a uma data (um dia, mês e ano) e retorna o anoda 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 20.


> (proximo-29/2 29 1 2000)2000> (proximo-29/2 29 3 2000)2004> (proximo-29/2 29 1 1900)1904

31. (3) Escreva em Scheme o procedimento numero-de-29/2s que recebe como argumentosseis 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 29de Fevereiro depois da primeira data e até à segunda (inclusive).

Sugestão: Use o procedimento proximo-29/2 definido na alínea 30.

32. (3) Escreva em Scheme o procedimento dias que recebe como argumentos seis núme-ros inteiros correspondentes a duas datas (um dia, mês, ano para cada data), sendo aprimeira data anterior à segunda, e devolve o número de dias depois da primeira data eaté à 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 /nem os predicados <, > e = mas que existem os procedimentos add1, sub1 e zero? querecebem como argumento um inteiro e devolvem, respectivamente, o seu sucessor, o seuantecessor, e o resultado de verificar se o número é 0.

Neste exercício apenas poderá utilizar estas 3 operações e outras eventualmente definidasutilizando estas.

(a) (1) Escreva um procedimento em Scheme soma que recebe dois números inteirospositivos 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 em Scheme multiplica que recebe dois númerosinteiros 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 em Scheme menos que recebe dois números inteirospositivos 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 em Scheme par? que recebe um número inteiropositivo n, e retorna #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 inteirospositivos n e m, e retorna #t se o n for menor do que m e #f no caso contrário.Escreva um procedimento em Scheme quociente que recebe dois números inteirospositivos n e m, e devolve o quociente da divisão de n por m. No caso de m ser 0deverá devolver 0.Relembre que o quociente da divisão de dois números inteiros positivos n e m é omaior 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 em Scheme somatorio que recebe um número inteiropositivo n, e devolve a soma de todos os números até n.

> (somatorio 3)6> (somatorio 6)21

3. (1) Escreva um procedimento em Scheme soma-quadrados que recebe um númerointeiro 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 em Scheme factorial que recebe um número inteiropositivo n, e devolve o factorial desse número.

> (factorial 0)1> (factorial 5)120


5. (1) Escreva um procedimento em Scheme potencia que recebe dois números inteirospositivos b e n, e devolve a potência n de b, i.e., bn.

> (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 umprocedimento em Scheme numero-divisores que recebe um número inteiro positivo n,e retorna o número de divisores de n. No caso de n ser 0 deverá retornar 0.

> (numero-divisores 20)6> (numero-divisores 13)2

7. (2) Suponha definido um procedimento primo? que recebe um número inteiro positivon, e retorna #t se o número for primo e #f no caso contrário.

Escreva um procedimento em Scheme numero-primos-menores que recebe um númerointeiro positivo n, e retorna 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 positivon, e retorna #t se o número for primo e #f no caso contrário.

Escreva um procedimento em Scheme numero-divisores-primos que recebe um númerointeiro positivo n, e retorna o número de divisores primos de n. No caso de n ser 0 deveráretornar 0.

> (numero-divisores-primos 1)0> (numero-divisores-primos 20)2> (numero-divisores-primos 30)3

9. (2) Escreva um procedimento em Scheme soma-divisores que recebe um númerointeiro positivo n, e retorna a soma de todos os divisores de n. No caso de n ser 0 deveráretornar 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 talque be ≤ n. Escreva um procedimento em Scheme logaritmo que recebe dois númerosinteiros positivos n e b, e devolve o logaritmo inteiro de n na base b. No caso de n ou bserem 0 deverá retornar 0.

> (logaritmo 8 2)3> (logaritmo 7 2)2

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 em Scheme raiz que recebe dois números inteiros positivos ne e, e devolve a raiz inteira de n de índice e. No caso de e ser 0 deverá retornar 0.

> (raiz 8 3)2> (raiz 15 2)3

12. (4) Suponha definido um procedimento kesimo-factor-primo que recebe dois númerosinteiros positivos n e k, e retorna o seu k-ésimo factor primo de n.

Escreva um procedimento em Scheme kesimo-expoente que recebe dois números inteirospositivos n e k, e retorna o expoente do k-ésimo factor primo de n. No caso de n termenos de k factores primos ou k ser 0, deverá retornar 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 procedimentossobre números inteiros:

• (remainder n m) retorna o resto da divisão de n por m.• (quotient n m) retorna o quociente da divisão de n por m.

13. (3) Escreva um procedimento em Scheme numero-digitos que recebe um númerointeiro positivo n, e retorna o número de dígitos de n.

> (numero-digitos 9)1> (numero-digitos 1012)4

14. (3) Escreva um procedimento em Scheme soma-digitos que recebe um número inteiropositivo n, e retorna a soma de todos os dígitos de n.


> (soma-digitos 9)9> (soma-digitos 1012)4

15. (3) Escreva um procedimento em Scheme soma-digitos-pares que recebe um númerointeiro positivo n, e retorna a soma de todos os dígitos pares de n.

> (soma-digitos-pares 9)0> (soma-digitos-pares 1412)6

16. (4) Escreva um procedimento em Scheme digitos-impares que recebe um númerointeiro positivo n, e retorna o número composto apenas pelos seus dígitos ímpares de n.

> (digitos-impares 94558)955> (digitos-impares 2468)0

17. (4) Escreva um procedimento em Scheme muda-digito que recebe três números inteirospositivos n, k e d, e retorna o inteiro que resulta de substituir o dígito na posição k den 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 detodos os seus algarismos. Escreva um procedimento em Scheme espelho que recebe umnúmero inteiro positivo n, e retorna o seu espelho.

> (espelho 391)139> (espelho 45679)97654

19. (4) Um número binário bnbn−1 . . . b1b0 pode ser transformado num número decimalusando a seguinte formula

∑ni=0 bi2

i. Escreva um procedimento em Scheme binario-decimalque recebe um número b escrito em binário e retorna 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 bnbn−1 . . . b1b0através da seguinte recorrência: seja q0 = d e qi = quociente(qi−1, 2) para i > 0, ebi = resto(qi, 2). Escreva um procedimento em Scheme decimal-binario que recebeum número d escrito em base 10 e retorna a sua representação binária.

> (decimal-binario 33)100001> (decimal-binario 156)10011100

2.2.4 Valores aproximados de funções

1. (2) Sabe-se que a seguinte fórmula permite calcular uma aproximação da função senoaté um determinado número de termos:

seno(x) = x(1− x2

2 · 3(1− x2

4 · 5(1− x2

6 · 7(· · · ))))

Defina em Scheme 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 eo número de factores a considerar.

2. (2) A função arctg pode ser aproximada através da fórmula

arctg(z) =∞∑n=0

(−1)nz2n+1

2n+ 1= z − z3

3+z5

5− z7

7+ . . .

Defina em Scheme 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 bemcomo 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 pro-cedimento 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,

é sucessivamente melhorado utilizando a fórmulay+x

y

2 .

Por exemplo, para calcular√

3, poderíamos efectuar os seguintes cálculos:

Passo Aproximação Nova aproximação1 3 22 2 1.753 1.75 1.7321428574 1.732142857 1.732050815 1.73205081 1.7320508086 1.732050808 1.732050808

Considerando que uma primeira aproximação grosseira para√x pode ser x, escreva um

procedimento em Scheme 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 comos elementos neutros da adição (0) e da multiplicação (1), com a constante π e com aunidade imaginária i.

O valor de e corresponde ao número real que é a soma da seguinte série infinita

e =∞∑n=0

1

n!=

1

0!+

1

1!+

1

2!+

1

3!+ . . .

Escreva um procedimento em Scheme para calcular uma aproximação do número e,utilizando a série apresentada. A condição de paragem deve ser determinada por si edevidamente justificada.

Capítulo 3

Processos gerados por procedimentos


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 suaresposta e dê um exemplo.

5. Considere a afirmação “os procedimentos que geram processos iterativos são sempre me-lhores que os procedimentos que geram processos recursivos". Comente-a relativamenteaos seguintes aspectos: (a) memória ocupada; (b) tempo gasto; (c) facilidade de escritae leitura do programa.

6. Qual o interesse de estudar a ordem de crescimento de um processo? Compare as or-dens de crescimento (temporal e espacial) entre processos recursivos lineares e iterativoslineares.

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.


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. Depoisadmire 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 inteirossuperiores 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 calculada pelo procedimento misterio?.

(b) O processo gerado pelo procedimento misterio?-aux é iterativo ou recursivo? Jus-tifique a sua resposta.

3. (1) Considere a definição do seguinte procedimento em Scheme:

(define (misterio-aux m1 m2 r)(if (= m2 0)

r(misterio-aux m1 (- m2 1) (+ m1 r))))

(define (misterio x y)(misterio-aux x y 0))

(a) Mostre a evolução do processo originado pela execução de (misterio 7 3).

(b) O processo gerado é recursivo ou iterativo? Justifique a sua resposta.

(c) O procedimento misterio-aux é recursivo? Justifique a sua resposta.

4. (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 queseja 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 asua resposta.


5. (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 umprocesso recursivo. Se o processo gerado era recursivo, transforme o procedimento,de forma a que gere um processo iterativo.

6. (1) O número de combinações de m objectos n a n pode ser dado pela seguinte recor-rência:

C(m,n) =

1 se n = 01 se m = nC(m− 1, n) + C(m− 1, n− 1) se m > n, m > 0 e n > 0

(a) Usando a fórmula acima, escreva um procedimento em Scheme para calcular onúmero de combinações de m objectos n a n.

(b) Que tipo de processo é gerado pelo seu procedimento?

7. (1) A função de Ackermann é definida através da seguinte recorrência:1

A(m,n) =

n+ 1 se m = 0A(m− 1, 1) se m > 0 e n = 0A(m− 1, A(m,n− 1)) se m > 0 e n > 0

(a) Escreva um procedimento em Scheme Ackermann que calcula o valor da função deacordo com a expressão acima.

(b) Mostre a evolução do processo originado pela avaliação de (Ackermann 2 2).

8. (2) A função potência pode ser definida através da seguinte recorrência:

xn =

x se n = 1x.(xn−1) se n for ímpar(xn/2)2 se n for par

Escreva um procedimento potencia que gera um processo iterativo e que corresponde àrealização desta função.

1Tal como apresentada em [Machtey e Young 78], pág. 24.


9. (2) Suponha que não existe o operador * em Scheme mas que existem os procedimentossoma, quociente e par? definidos no Exercício 1 da Secção 2.2.3. Um modo de definiro produto de dois números inteiros positivos é através da seguinte recorrência:

x · y =

0 se x = 0x2 · (y + y) se x é pary + (x− 1) · y em caso contrário

(a) Defina o procedimento produto que efectua o produto de dois números inteirospositivos, de acordo com esta definição.

(b) O seu procedimento é um procedimento recursivo? Justifique a sua resposta.

(c) O seu procedimento gera um processo recursivo ou iterativo? Justifique a suaresposta.

(d) Se o processo gerado era iterativo, transforme o procedimento, de forma a que gereum processo recursivo. Se o processo gerado era recursivo, transforme o procedi-mento, de forma a que gere um processo iterativo.

10. (2) Suponha que as operações de multiplicação e potência não existiam em Scheme eque pretende calcular o quadrado de um número natural. O quadrado de um númeronatural pode ser calculado como sendo a soma de todos os números ímpares inferioresao dobro do número. Com efeito:

n 1 + . . .+ (2n− 1) n2

1 1 = 12 1+3 = 43 1+3+5 = 94 1+3+5+7 = 165 1+3+5+7+9 = 256 1+3+5+7+9+11 = 36. . . . . . . . .

Escreva em Scheme dois procedimentos que calculam o quadrado de um número naturalutilizando 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.

Note que o dobro de um número também não pode ser calculado recorrendo à operaçãode multiplicação.

11. (2) Defina um procedimento recursivo que recebe três argumentos a, b e n e que devolveo 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.

12. (2) O procedimento


(define (factorial n)(if (= n 0)

1(* n (factorial (- n 1)))))

calcula o factorial através de multiplicações da esquerda para a direita (5! = 5× 4× 3×2× 1 = 20× 3× 2× 1 = 60× 2× 1 = 120× 1 = 120).

Em alternativa, poderíamos ter efectuado as multiplicações da direita para a esquerda(5! = 5× 4× 3× 2× 1 = 5× 4× 3× 2 = 5× 4× 6 = 5× 24 = 120).

Escreva um procedimento que gera um processo iterativo e que calcula o valor de factorialmultiplicando da direita para a esquerda.

Sugestão: Vai ter de usar um parâmetro adicional para o cálculo de factorial auxiliar.

13. 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? querecebem como argumento um inteiro e devolvem, respectivamente, o seu sucessor, o seuantecessor, e o resultado de verificar se o número é 0.

Neste exercício apenas poderá utilizar estas 3 operações e outras eventualmente definidasutilizando estas.

(a) (1) (Secção 2.2.3, Ex 1a) Escreva um procedimento em Scheme soma, que gereum processo iterativo, e que recebe dois números inteiros positivos n e m, e devolvea 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 em Scheme multiplica, quegere um processo iterativo, e que recebe dois números inteiros positivos n e m, edevolve 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) (Secção 2.2.3, Ex 1c) Escreva um procedimento em Scheme menos, que gereum processo iterativo, e que recebe dois números inteiros positivos n e m, e devolvea diferença dos dois.Sugestão: Use uma ideia semelhante ao exercício 13a.

> (menos 8 2)6> (menos 2 8)-6


(d) (2) (Secção 2.2.3, Ex 1d) Escreva um procedimento em Scheme par?, que gereum processo iterativo, e que recebe um número inteiro positivo n, e retorna #t sen for par e #f no caso contrário.

> (par? 8)#t> (par? 5)#f

(e) (1) Escreva um procedimento em Scheme maior?, e que gere um processo iterativo,que recebe dois números inteiros positivos n e m, e retorna #t se o n for maior doque m e #f no caso contrário.

> (maior? 8 2)#t> (maior? 8 8)#f> (maior? 2 8)#f

(f) (1) Escreva um procedimento em Scheme igual?, e que gere um processo iterativo,que recebe dois números inteiros positivos n e m, e retorna #t se o n for igual a m e#f no caso contrário.

> (igual? 8 2)#f> (igual? 8 8)#t> (igual? 2 8)#f

(g) (1) Escreva um procedimento em Scheme menor?, e que gere um processo iterativo,que recebe dois números inteiros positivos n e m, e retorna #t se o n for menor doque m e #f no caso contrário.

> (menor? 8 2)#f> (menor? 8 8)#f> (menor? 2 8)#t

(h) (2) (Secção 2.2.3, Ex 1e) Escreva um procedimento em Scheme quociente, quegere um processo iterativo, e que recebe dois números inteiros positivos n e m, edevolve 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 é omaior inteiro r tal que r.m ≤ n.Sugestão: Utilize os procedimentos menos e menor? definidos anteriormente.

> (quociente 8 2)4


> (quociente 10 3)3

(i) (2) Escreva um procedimento em Scheme resto, que gere um processo iterativo,e que recebe dois números inteiros positivos n e m, e devolve o resto da divisão den por m. No caso de m ser 0 deverá devolver n.

> (resto 8 2)0> (resto 10 3)1

(j) (2) Escreva um procedimento em Scheme simetrico, que gere um processoiterativo, e que recebe um número inteiro n, e devolve o simetrico de n.

> (simetrico 8)-8> (simetrico -3)3

14. (1) (Secção 2.2.3, Ex 3) Escreva um procedimento em Scheme soma-quadrados, quegere um processo iterativo, e que recebe um número inteiro positivo n, e devolve a somado quadrado de todos os números até n.

> (soma-quadrados 3)14> (soma-quadrados 5)55

15. (1) (Secção 2.2.3, Ex 5) Escreva um procedimento em Scheme potencia que recebedois 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

16. (2) Um número n é quadrado perfeito se existir um m tal que m2 = n. Escreva umprocedimento em Scheme quadrados-perfeito?, que gere um processo iterativo, e querecebe um número n, e retorna #t se n for um quadrado perfeito e #f no caso contrário.

> (quadrado-perfeito? 4)#t> (quadrado-perfeito? 8)#f

17. (2) Um número n diz-se primo se os seus únicos divisores são o 1 e o próprio n. Onú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 em Scheme primo?, que gere um processo iterativo, e querecebe um número inteiro positivo n, e usando o método acima retorna #t se o númerofor primo e #f no caso contrário.

> (primo? 53)#t> (primo? 21)#f

18. (3) Um número é livre de quadrados se não for divisível por nenhum quadrado perfeitopara além de 1. Escreva um procedimento em Scheme livre-quadrados?, que gere umprocesso iterativo, e que recebe um número n, e retorna #t se n for livre de quadradose #f no caso contrário.

> (livre-quadrados? 4)#f> (livre-quadrados? 50)#f> (livre-quadrados? 70)#t

19. (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 em Scheme poderoso?, que gere umprocesso iterativo, e que recebe um número inteiro positivo n, e retorna #t se o númerofor poderoso e #f no caso contrário.

> (poderoso? 100)#t> (poderoso? 36)#t> (poderoso? 75)#f> (poderoso? 2)#f

20. (2) (Secção 2.2.3, Ex 6) Um número d é divisor de n se o resto da divisão de n por dfor 0. Escreva um procedimento em Scheme numero-divisores, que gere um processoiterativo, e que recebe um número inteiro positivo n, e retorna o número de divisores den. No caso de n ser 0 deverá retornar 0.

> (numero-divisores 20)6> (numero-divisores 13)2

21. (2) (Secção 2.2.3, Ex 9) Escreva um procedimento em Scheme soma-divisores, quegere um processo iterativo, e que recebe um número inteiro positivo n, e retorna a somade todos os divisores de n. No caso de n ser 0 deverá retornar 0.


> (soma-divisores 20)42> (soma-divisores 13)14

22. (3) (Secção 2.2.3, Ex 11) A raiz inteira de índice e de um número n é o maior númerointeiro r tal que re ≤ n. Escreva um procedimento em Scheme raiz, que gere umprocesso iterativo, e que recebe dois números inteiros positivos n e e, e devolve a raizinteira de n de índice e. No caso de e ser 0 deverá retornar 0.

> (raiz 8 3)2> (raiz 15 2)3

23. (3) Um número n diz-se triangular se n = 1 + 2 + · · · + (m − 1) + m para algum m.Escreva um procedimento em Scheme triangular?, que gere um processo iterativo, eque recebe um número inteiro positivo n, e retorna #t se o número for triangular e #fno caso contrário. No caso de n ser 0 deverá retornar #f.

> (triangular? 6)#t> (triangular? 8)#f

24. (3) Dois números n em dizem-se primos entre si se não têm nenhum divisor em comumà excepção do 1. Escreva um procedimento em Scheme primos-entre-si?, que gere umprocesso iterativo, e que recebe dois números inteiros positivos n e m, e retorna #t se osnúmeros forem primos entre si e #f no caso contrário. No caso de n ou m serem 0 deveráretornar #f.

> (primos-entre-si? 4 10)#f> (primos-entre-si? 21 10)#t

25. (3) Um número n diz-se um divisor fraco dem se todos os factores primos de n tambémsão factores primos de m. Escreva um procedimento em Scheme divisor-fraco?, quegere um processo iterativo, e que recebe dois números inteiros positivos n e m, e retorna#t se n for um divisor fraco de m e #f no caso contrário. No caso de n ou m serem 0deverá retornar #f.

> (divisor-fraco? 4 10)#t> (divisor-fraco? 10 4)#f> (divisor-fraco? 6 10)#f


26. (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 em Scheme mdc, que gere um processoiterativo, e que recebe dois números inteiros positivos n e m, e retorna o máximo divisorcomum dos dois números. No caso de n e m serem ambos 0 deverá retornar 0. Se apenasum deles for 0 deverá retornar o outro.

> (mdc 3 0)3> (mdc 12 20)4> (mdc 10 20)10

27. (4) O mínimo múltiplo comum, que gere um processo iterativo, e de dois números ne m é o menor inteiro x tal que x é divisível por n e m. Escreva um procedimentoem Scheme mmc que recebe dois números inteiros positivos n e m, e retorna o mínimomúltiplo comum dos dois números. No caso de n ou m serem 0 deverá retornar 0.

> (mmc 4 6)12> (mmc 12 5)60

28. (3) Um número n é o n-ésimo primo se for primo e existirem n − 1 números primosmenores que ele. Escreva um procedimento em Scheme nesimo-primo, que gere umprocesso iterativo, e que recebe um número inteiro positivo n, e retorna o n-ésimo númeroprimo. No caso de n ser 0 deverá retornar 0.

> (nesimo-primo 1)2> (nesimo-primo 10)29

29. (3) Um número p é primo de Mersenne se p é primo e 2p − 1 também é primo. Umnúmero n é o n-ésimo primo de Mersenne se existirem n−1 primos de Mersenne menoresque n. Os primeiros 10 primos de Mersenne são 2, 3, 5, 7, 13, 17, 19, 31, 61, 89.

Escreva um procedimento em Scheme nesimo-primo-mersenne, que gere um processoiterativo, e que recebe um número n, e retorna o n-ésimo primo de Mersenne.

> (nesimo-primo-mersenne 3)5> (nesimo-primo-mersenne 9)61

30. (3) Um número d é o k-ésimo divisor de n se for divisor de n e existirem k−1 divisoresde n menores que d. Escreva um procedimento em Scheme k-divisor, que gere umprocesso iterativo, e que recebe dois números inteiros positivos n e k, e retorna o k-ésimodivisor de n. No caso de n ser 0, ou k ser 0, ou n ter menos de k divisores deverá retornar0.


> (kesimo-divisor 20 3)4> (kesimo-divisor 20 6)20> (kesimo-divisor 20 7)0

31. (3) Um número p é o k-ésimo factor primo de n se p é primo e existem k−1 factores pri-mos de n menores que p. Escreva um procedimento em Scheme kesimo-factor-primo,que gere um processo iterativo, e que recebe dois números inteiros positivos n e k, eretorna o seu k-ésimo factor primo de n. No caso de n ter menos de k factores primosou k ser 0, deverá retornar 0.

> (kesimo-factor-primo 3 1)3> (kesimo-factor-primo 3 2)0> (kesimo-factor-primo 60 3)5

32. (4) (Secção 2.2.3, Ex 12) Escreva um procedimento em Scheme kesimo-expoente, quegere um processo iterativo, e que recebe dois números inteiros positivos n e k, e retornao expoente do k-ésimo factor primo de n. No caso de n ter menos de k factores primosou k ser 0, deverá retornar 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 procedimentossobre números inteiros:

• (remainder n m) retorna o resto da divisão de n por m.• (quotient n m) retorna o quociente da divisão de n por m.

33. (3) (Secção 2.2.3, Ex 13) Escreva um procedimento em Scheme numero-digitos, quegere um processo iterativo, e que recebe um número inteiro positivo n, e retorna o númerode dígitos de n.

> (numero-digitos 9)1> (numero-digitos 1012)4

34. (3) (Secção 2.2.3, Ex 14) Escreva um procedimento em Scheme soma-digitos, quegere um processo iterativo, e que recebe um número inteiro positivo n, e retorna a somade todos os dígitos de n.


> (soma-digitos 9)9> (soma-digitos 1012)4

35. (3) Escreva um procedimento em Scheme existe-digito?, que gere um processoiterativo, e que recebe um número inteiro positivo n e um dígito d, e retorna #t seo dígito d ocorrer em n e #f no caso contrário.

> (existe-digito? 234 3)#t> (existe-digito? 538 7)#f

36. (4) (Secção 2.2.3, Ex 16) Escreva um procedimento em Scheme digitos-impares,que gere um processo iterativo, e que recebe um número inteiro positivo n, e retorna onúmero composto apenas pelos seus dígitos ímpares de n.

> (digitos-impares 94558)955> (digitos-impares 2468)0

37. (3) O dígito de posição k de um número n é o dígito na k-ésima posição de n a partirdo dígito das unidades. Escreva um procedimento em Scheme posicao, que gere umprocesso iterativo, e que recebe dois números inteiros positivos n e k, e retorna o dígitona posicao k de n. No caso de n ter menos de k dígitos ou k ser 0, deverá retornar 0.

> (posicao 12345 2)4> (posicao 12345 7)0

38. (3) Um número é capicua se se lê igualmente da esquerda para a direita e vice-versa.Escreva um procedimento em Scheme capicua?, que gere um processo iterativo, e querecebe um número inteiro positivo n, e retorna #t se o número for uma capicua e #f nocaso contrário.

Sugestão: Use o procedimento posicao definido na alínea 37

> (capicua? 12321)#t> (capicua? 1221)#t> (capicua? 123210)#f

39. (4) (Secção 2.2.3, Ex 17) Escreva um procedimento em Scheme muda-digito, que gereum processo iterativo, e que recebe três números inteiros positivos n, k e d, e retorna ointeiro 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

40. (4) (Secção 2.2.3, Ex 18) O espelho de um número inteiro positivo é o resultado deinverter a ordem de todos os seus algarismos. Escreva um procedimento em Schemeespelho, que gere um processo iterativo, e que recebe um número inteiro positivo n, eretorna o seu espelho.

> (espelho 391)139> (espelho 45679)97654

41. (1) Usando o procedimento espelho definido acima, reescreva de novo o procedimentocapicua? definido na alínea 38.

42. (4) (Secção 2.2.3, Ex 20) Um número decimal d pode ser transformado num número bi-nário bnbn−1 . . . b1b0 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 em Scheme decimal-binario,que gere um processo iterativo, e que recebe um número d escrito em base 10 e retornaa sua representação binária.

> (decimal-binario 33)100001> (decimal-binario 156)10011100

Documents

Exercícios para Fundamentos da Programação Utilizando Múltiplos