Fundamentos da Programaç˜ao de Computadores

Universidade do Minho
Escola de Engenharia
Departamento de Sistemas de Informação
Fundamentos
da
Programação de Computadores
Licenciatura em Tecnologias e Sistemas de Informação
1º Ano — 1º Semestre
Ano Lectivo 2008/2009
— Projecto 02 —
Data de Lançamento: 13 de Outubro de 2008
Data Limite de Entrega: 20 de Outubro de 2008 (12:00)
Prof. Filipe de Sá-Soares
Outubro de 2008
Observações
ˆ A resolução do Projecto pode ser efectuada individualmente ou em grupo. No caso
de resolução por grupo, os grupos de trabalho devem ser compostos por dois elementos. Adicionalmente, estabelece-se que os grupos sejam formados por elementos
pertencentes ao mesmo turno PL.
ˆ Por norma, a resolução do Projecto deve ser auto-contida, ou seja, os alunos não
devem colaborar uns com os outros na resolução dos problemas propostos, excepto
no caso da resolução em grupo, em que os alunos que formam o grupo colaboram entre
si na resolução do projecto. Se, a tı́tulo excepcional, ocorrerem colaborações com
outros alunos para a resolução dos problemas propostos, tal deve ser explicitamente
indicado nos resultados submetidos (ver ponto adiante).
ˆ A submissão dos resultados alcançados na resolução do Projecto deve ser realizada
via moodle, até à data e hora indicadas anteriormente. Cada aluno deverá submeter
o seu trabalho, quer o mesmo tenha sido elaborado individualmente quer em grupo.
Não serão aceites submissões para além dessa data/hora.
ˆ Os resultados a submeter devem constar de um ficheiro de texto (formato ASCII).
O nome do ficheiro deve ser composto pelos seguintes campos: identificação do
projecto (na forma “Pii”, em que “ii” é o número do projecto), caracter lowline,
números de aluno dos seus autores, separados por lowline, e extensão .txt. Para
o caso de projectos resolvidos de forma individual, apenas deverá ser indicado um
número de aluno (correspondente ao aluno que o resolveu).
O corpo desse ficheiro principiará com a identificação do projecto, seguindo-se a
indicação do(s) número(s) e nome(s) do(s) aluno(s) que resolveu(ram) os problemas
propostos e de eventuais colaborações (números e nomes). Depois, deverão surgir
as respostas aos problemas propostos, com a devida sinalização da questão a que se
refere cada resposta, e sem alteração de ordem (caso não responda a uma questão, não
deixe de sinalizar a identificação dessa questão, apesar de não fornecer resposta).
Seguidamente, dá-se um exemplo do inı́cio de um desses ficheiros de texto, cuja
designação deveria ser P01 12345 12346.txt. Note que nesse exemplo, não foi dada
resposta à questão A.1.iii e não existiram colaborações extra-grupo.
Projecto 01
Autores
12345 - Filipe de Sá-Soares
12346 - Miguel Abrunhosa de Brito
Colaboraç~
oes
sem colaboraç~
oes
A.1.i - 25
A.1.ii - erro
A.1.iii A.1.iv - (define a 101)
..
.
2
Questões
A. Introdução à Recursão
1. Que caracterı́stica deve apresentar um procedimento para que o mesmo dê origem a um processo recursivo?
2. Caracterize o padrão de evolução no espaço de um processo recursivo.
3. Enumere os passos fundamentais da estratégia de concepção de algoritmos recursivos, explicando em que consiste cada um desses passos.
4. Identifique os componentes dos algoritmos recursivos. Para o procedimento que
calcula os números de Fibonacci, que se apresenta de seguida, aponte quais são
esses componentes.
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
B. Avaliação de Procedimentos Recursivos
1. Considere a seguinte definição:
(define (prec x y)
(if (= x y)
0
(+ x (prec (+ x 1) y))))
Assumindo que x e y são valores inteiros, em quais das seguintes condições a
invocação do procedimento prec executará para sempre?
i.
ii.
iii.
iv.
v.
x
x
x
x
y
<
>
=
<
<
y
y
y
0
0
2. Considere o procedimento fib definido anteriormente. Aplicando o Modelo de
Substituição, apresente a evolução das seguintes avaliações:
i. (fib 2)
ii. (fib 4)
3. O seguinte procedimento calcula uma função matemática denominada função
de Ackermann.
(define (Ack x y)
(cond ((= y
((= x
((= y
(else
0) 0)
0) (* 2 y))
1) 2)
(Ack (- x 1)
(Ack x (- y 1))))))
3
i. Quais são os valores das seguintes expressões?
A. (Ack 1 10)
B. (Ack 2 4)
C. (Ack 3 3)
D. (Ack 4 3)
ii. Considere os seguintes procedimentos, em que Ack é o procedimento definido acima:
(define (f n) (Ack 0 n))
(define (g n) (Ack 1 n))
(define (h n) (Ack 2 n))
Forneça definições matemáticas concisas para as funções computadas pelos
procedimentos f, g e h, para valores inteiros positivos de n.
Por exemplo, o procedimento
(define (k n) (* 5 n n))
computa 5n2 .
C. Escrita de Procedimentos Recursivos
Neste grupo de questões não deixe de exercitar a aplicação da estratégia de concepção
de algoritmos recursivos!
1. Suponha que se pretende implementar a operação de potenciação, mas que só
se dispõe de operações mais simples como a multiplicação, adição e subtracção,
e de predicados simples. Escreva um procedimento recursivo que receba dois
argumentos, b e e, os quais pode assumir que são inteiros positivos, e que retorne
o valor de be , usando apenas aquelas operações e predicados. O procedimento
deve denominar-se pot-rec.
2. Suponha que se pretende implementar a operação de multiplicação, mas só dispomos de operações mais simples como a adição e a subtracção e de predicados
simples. Escreva um procedimento recursivo que receba dois argumentos, a e
b, os quais pode assumir que são inteiros positivos, e que retorne o produto de
a por b, usando apenas aquelas operações e predicados. O procedimento deve
denominar-se multip-rec.
3. Escreva um procedimento recursivo que receba uma potência positiva de 2 e que
retorne o logaritmo base dois desse valor. O procedimento, a denominar por
log2-simples, deve desencadear um processo recursivo e empregar apenas as
operações aritméticas básicas, tais como, +, -, * e /. Seguidamente, ilustra-se
a aplicação do procedimento a quatro valores distintos.
(log2-simples 1) ⇒ 0
(log2-simples 2) ⇒ 1
(log2-simples 4) ⇒ 2
(log2-simples 8) ⇒ 3
4. Atente na seguinte sequência numérica:
6 – 9 – 18 – 21 – 42 – 45 – . . .
Escreva um procedimento, denominado seq, que permita determinar o n-ésimo
termo dessa sequência. Por exemplo:
(seq 1) ⇒ 6
(seq 4) ⇒ 21
(seq 10) ⇒ 189
4
5. Atente na seguinte sequência numérica:
1 – 2 – 3 – 3 – 4 – 6 – 7 – 9 – 13 – . . .
i. Escreva um procedimento, denominado seqnum, que permita determinar o
n-ésimo termo dessa sequência. Por exemplo:
(seqnum 1) ⇒ 1
(seqnum 4) ⇒ 3
(seqnum 10) ⇒ 16
(seqnum 30) ⇒ 3721
ii. Para o procedimento que escreveu na alı́nea anterior, identifique os componentes do algoritmo recursivo.
6. A imagem seguinte representa as primeiras seis linhas do triângulo de Tartaglia,
também conhecido por triângulo de Pascal.
1
1
1
2
1
1
1
3
4
5
1
1
3
6
10
1
4
10
1
5
1
Escreva um procedimento, denominado combi, que permita determinar o coeficiente de ordem m que se encontra localizado na linha n do triângulo de Tartaglia. Considere que na invocação do procedimento primeiro indica o número
da linha e depois a ordem do coeficiente. A primeira linha tem ı́ndice 0 (zero) e
a ordem dos coeficientes incrementa da esquerda para a direita da linha, sendo
que a ordem do coeficiente mais à esquerda tem ı́ndice 0 (zero). Por exemplo:
(combi 0 0) ⇒ 1
(combi 2 0) ⇒ 1
(combi 2 1) ⇒ 2
(combi 2 2) ⇒ 1
(combi 5 4) ⇒ 5
Prova de Avaliação Experimental
ˆ Para os alunos avaliados segundo o perfil P1 ou segundo o perfil P2, a prova de
avaliação experimental do presente projecto decorrerá na semana que se inicia a 20
de Outubro de 2008, tendo lugar na sessão PL em que o aluno se encontrar inscrito.
ˆ A realização da prova de avaliação experimental deverá ser efectuada com recurso
ao moodle, pelo que cada aluno deve garantir previamente o correcto acesso à sua
conta na comunidade moodle FPC, sob pena de não poder realizar a prova.
ˆ Quando se apresentarem à prova de avaliação experimental, os alunos devem ser
capazes de responder às questões do presente projecto sem necessitarem de recorrer
ao interpretador Scheme.
ˆ A não comparência de um aluno avaliado segundo o perfil P1 ou segundo o perfil P2
à prova de avaliação experimental traduz-se na atribuição de uma classificação de
0 (zero) valores nessa prova.
5