Aulas Práticas, LEIC, IP1, 2000/2001

Introdução à Programação de Computadores I

Trabalhos de casa

Aula 1
Aula 2
Aula 3
Aula 4
Aulas 5 e 6
Aula 7
Aulas 8 e 9
Aula 10

Autores

F. Nunes Ferreira
Cristina Ribeiro

Aula nº 1 - Avaliação de Expressões, Interpretação de Procedimentos

1.1 (Avaliação de Expressões com Procedimentos Primitivos)

Para cada uma das expressões seguintes, tentar prever um resultado e confirmar usando o interpretador.

   (+ 22.5 3)           -> 
   (- (+ 75 12) 4 1)	-> 
   (expt 2 (/ 1 2))	-> 
   (* (+ 14 -6) 3E5)	->

1.2 (Definição de Constantes e Uso em Expressões com Primitivas)

Prever o resultado de avaliar as expressões seguintes em Scheme, pela ordem indicada, e confirmar usando o interpretador.

   (define a 2)	        -> 
   (define b 7)	        -> 
   (+ a b)	        ->
   (expt (- b a) a)	->
   (define b 8)	        -> 
   (+ a b)	        ->

1.3 (Significado de Procedimentos Compostos)

Observe as definições de procedimentos a seguir. Descubra o que se pretende que cada um signifique e proponha nomes mais sugestivos.

   (define coisa1
      (lambda (numero)
         (expt numero (/ 1 3))))
   (define coisa2
      (lambda (numero)
         (* 3.14159 (* 2 numero))))
   (define coisa3
      (lambda (numero1 numero2)
         (/ (+ numero1 numero2) 2)))

1.4 (Definir Procedimento)

Escreva um procedimento area-triangulo que tome 2 argumentos, a base e a altura, e retorne a área do triângulo respectivo.

1.5 (Definir Procedimento)

Escreva um procedimento quadrados-maiores que tenha 3 números como argumentos e que devolva a soma dos quadrados dos 2 números maiores.

Aula nº 2 - Procedimentos e Recursividade

2.1 (Analisar Procedimento)

Considere a seguinte definição

   (define mais-abs
      (lambda (a b)
         ((if (> b 0) + -) a b)))

Explique o funcionamento do procedimento indicado e teste-o.

2.2 (Ano Bissexto)

O ano bissexto ocorre de 4 em 4 anos, com excepção dos anos de século que são bissextos só de 4 em 4 séculos, ou seja cada 400 anos. Escreva um procedimento bissexto? com argumento um número inteiro (ano) e que retorne um valor lógico (#t ou #f) indicando se o ano é bissexto.

2.3 (Dias entre datas)

Escreva um procedimento que tenha como argumentos 2 datas (3 inteiros para cada uma, indicando o ano, o mês, o dia) e calcule o número de dias entre as datas.

2.4 (Algoritmo de Euclides do Máximo Divisor Comum)

O máximo divisor comum de 2 inteiros a e b é por definição o maior inteiro que divide a e b com resto 0. O algoritmo de Euclides para o máximo divisor comum baseia-se no facto de que, quando efectuamos a divisão com resto de 2 inteiros a e b (a >= b) 2 casos podem ocorrer:

o resto é 0, m.d.c.(a,b) = b
o resto r não é 0, mdc(a,b) = mdc(b,r).

Escreva um procedimento em Scheme para calcular o máximo divisor comum usando o algoritmo de Euclides.

2.5 (Raiz quadrada)

A raiz quadrada de um número pode ser obtida de forma iterativa usando o método de Newton. A partir de uma aproximação inicial y da raiz de um número x, uma melhor aproximação pode ser obtida fazendo a média de y e x/y.

2.5.a Defina o procedimento media que calcula a média dos valores dos seus argumentos.

    (media 2 5)	        -> 3.5

2.5.b Defina o procedimento melhora-aprox que tem como argumentos o número e a aproximação da raiz e efectua uma iteração do método.

    (melhora-aprox 2 1) -> 1.5

2.5.c Defina o predicado ja-chega? com 3 argumentos: o número, o valor aproximado da raiz e um valor de erro; o predicado deve retornar #t quando o quadrado da aproximação e o número diferirem de menos do que o valor do erro dado e #f no caso contrário.

2.5.d Use os procedimentos anteriores para construir raiz, um procedimento que tem como argumentos um número, uma aproximação inicial e uma precisão e calcula a raiz quadrada do número iterativamente na precisão indicada.

Aula nº 3 - Processos Recursivos e Iterativos

3.1 (Escolher Dígitos de um Número)

Escreva um procedimento em Scheme que recebe um número inteiro positivo e devolve um número composto só pelos seus dígitos pares.

    (so-pares 2354)	-> 24
    (so-pares 5)	-> 0

Averigúe se o procedimento que usou gera um processo recursivo ou iterativo. Apresente uma solução iterativa para o problema.

3.2 (Multiplicações)

Considere os procedimentos seguintes para fazer multiplicações de inteiros.

   (define prod1
      (lambda (a b)
         (if (= b 1)
            a
            (+ a (prod1 a (sub1 b))))))

   (define prod2
      (lambda (a b)
         (if (= b 1)
            a
            (+ (if (odd? b) a 0)
               (prod2 (dobro a) (metade b))))))

Compare os procedimentos prod1, prod2 e * (a multiplicação regular do Scheme), realizando operações com números de tamanhos crescentes.

3.3 (Juros)

Os juros são calculados aplicando uma taxa de juro ao valor do capital. Quando se fazem juros compostos, à passagem de cada período os juros acumulam no capital e o total é usado como o capital para o período seguinte.

3.3.a Escreva um procedimento em Scheme que receba o capital inicial, a taxa de juro e o número de períodos de acumulação e que calcule o total acumulado no final.

3.3.b Usando o procedimento acima, compare 2 produtos oferecido pela CaixaLocal: o depósitoForte tem uma taxa de 5% ao ano e acumula semestralmente; o depósitoAJeito tem uma taxa de juro de 4.98% ao ano e acumula de 3 em 3 meses.

Aula nº 4 - Mais procedimentos recursivos

4.1 (Baralhar Números)

Escrever o procedimento vira que tem como argumento um inteiro positivo escrito em decimal na forma abcde...m e que retorna um novo inteiro que é representado por m...edcba.

4.2 (Intercalar Números)

Escrever o procedimento intercala que tem como argumentos dois inteiros positivos escritos em decimal na forma abc...d e mno...p e que retorna um novo inteiro que intercala os dígitos de ambos, ambnco...dp.

    (intercala 123 456)	          -> 142536

4.3 (Identificar Procedimento)

    (define x
       (lambda (m n)
          (cond
	     ((zero? m) n)
	     ((zero? n) m)
	     (else (x (sub1 m) (sub1 n))))))

Os argumentos m e n são garantidamente positivos. Escolha um nome apropriado para o procedimento x e justificque essa escolha.

4.4 (Primos)

Um número é primo se for divisível apenas por si próprio e por 1. Uma forma simples (e pouco eficiente ...) de testar a primalidade de um inteiro é testar como divisores todos os inteiros inferiores a ele próprio.
a) Escreva um predicado primo? que implementa a estratégia indicada para o teste de primalidade.
b) Escreva um procedimento testa-primo, com 1 argumento. O procedimento testa se o argumento é um inteiro e nesse caso verifica se é primo usando primo?. Em todos os casos é gerada uma mensagem informativa.
c) Podemos melhorar a eficiência do teste de primalidade verificando que este pode efectivamente terminar, para um inteiro n, no primeiro inteiro não superior a (sqrt n). De facto, se n não é primo pode escrever-se como n = pq, com p e q diferentes de 1. Se p for superior a (sqrt n), então q terá de ser inferior. Escreva um predicado sou-primo? que implementa esta estratégia.

Aula nº 5 e 6 - Manipulação de Listas

5.1

Diga qual o valor das seguintes expressões em Scheme:

    => (car (list 1 2 3 ))                ->
    => (cdr (car '((a b) (c))))           ->
    => (cdr (cdr '((a b) (c))))           ->
    => (list (car (+ 2 3)))               ->
    => (list (car '(+ 2 3)))              ->
    => (list '(car '(+ 2 3)))             ->

5.2

Escreva em Scheme o procedimento tira-replicas que tem como argumento uma lista de símbolos e produz uma nova lista sem ocorrências repetidas contíguas do mesmo elemento.
Ex:

    => (tira-replicas '(a b a a a c c d)  ->   (a b a c d)
    => (tira-replicas '(a b a b c))       ->   (a b a b c)

5.3

Considere o procedimento nova-lista definido a seguir, que tem como procedimento auxiliar nova-lista-aux. Explique sucintamente qual o seu efeito sobre uma lista dada e indique os valores fornecidos pelo interpretador de Scheme para as expressões indicadas abaixo.

   (define nova-lista
      (lambda (lis)
         (cond
            ((null? lis) '())
            ((null? (cdr lis)) lis)
            ((eq? (car lis) (cadr  lis)) (nova-lista-aux (cdr lis)))
            (else (cons (car lis) (nova-lista (cdr lis)))))))
   (define nova-lista-aux
      (lambda (lis)
         (cond
            ((null? lis) '())
            ((null? (cdr lis)) '())
            ((eq? (car lis) (cadr  lis)) (nova-lista-aux (cdr lis)))
            (else (nova-lista (cdr lis))))))

    => (nova-lista '(a b a a a c c))      ->      
    => (nova-lista '(a b c a b c c))      ->

5.4

Escrever o procedimento subs-first que toma 3 argumentos: novo, velho e uma lista, lis e substitui a 1ª ocorrência de velho, no nível de topo de lis, por novo.

    => (subs-first 'gato 'cão '(o meu cão é esperto)
                                          -> (o meu gato é esperto)
    => (subs-first 'dois 'um '())         -> ()

5.5

Escrever o procedimento remove-last que retira de uma lista dada, a última ocorrência de um elemento.

   => (remove-last 'a '(b a n a n a s))  -> (b a n a n s)
   => (remove-last 'a '())               -> ()

5.6

Escrever o procedimento all-same? que toma uma lista como argumento e testa se todos os seus elementos são iguais.

   => (all-same? '(a a a a a a))         -> #t
   => (all-same? '(a b a b a b))         -> #f
   => (all-same? '((a b) (a b) (a b)))   -> #t
   => (all-same? '(a))                   -> #t
   => (all-same? '())                    -> #t

5.7

O procedimento soma-aos-pares toma como argumentos dois tuplos de igual comprimento e devolve um novo tuplo, em que cada componente é a soma dos pares retirados dos dois tuplos dados.

   => (soma-aos pares '(1 3 2) '(4 -1 2))     -> (5 2 4) 
   => (soma-aos pares '(3.2 1.5) '(6.0 -2.5)) -> (9.2 -1.0) 
   => (soma-aos pares '(7) '(11))             -> (18) 
   => (soma-aos pares '() '())                -> ()

5.8

O procedimento dot-product toma como argumentos dois tuplos de igual comprimento, calcula o produto de cada par e devolve a soma dos produtos.

   => (dot-product '(3 4 -1) '(1 -2 -3))      -> -2 
   => (dot-product '(0.003 0.035) '(8 2))     -> 0.094 
   => (dot-product '(5.3e4) '(2.0e-3))        -> 106.0 
   => (dot-product '() '())                   -> 0

Aula nº 7 - Colorir Mapas

Pretende-se colorir mapas de países, com um número mínimo de cores e sem que cores iguais sejam utilizadas em países vizinhos. São considerados países vizinhos os que tiverem, pelo menos, uma linha de fronteira comum (caso dos países 1 e 2) ou até um ponto de fronteira comum (caso dos países 2 e 3). O mapa é modelado através de uma lista, tendo um elemento por cada país do mapa. O elemento correspondente a um país representa os países vizinhos desse pais. Por exemplo, o país 1, sendo o primeiro elemento da lista, tem como vizinhos os países 2, 3 e 4.

   (define mapal
      '((2 3 4)           ; pais 1
        (1 3 4 5 7)       ; pais 2
        (1 6 7 2 4)       ; pais 3
        (l 7 6 2 3 5)     ; pais 4
        (7 2 4)           ; pais 5
        (3 4 7)           ; pais 6
        (2 3 4 5 6 8)     ; pais 7
        (7)))             ; pais 8

A modelação das cores pode também ser feita através de uma lista

   (define paleta-cores
      '(C1 C2 C3 C4))      ; neste caso, utilizam-se 4 cores

A atribuição de cores aos vários paises é conseguida com uma chamada a colorir-mapa, procedimento que espera dois argumentos, ou seja, duas listas, uma que representa o mapa e outra o conjunto de cores utilizadas para colorir o mapa. Este procedimento devolve uma lista com a indicação das cores a atribuir a cada país, a começar pelo pais 1.

   => (colorir-mapa mapal paleta-cores)
  (c1 c2 c3 c4 c3 c2 c1 c2)

Uma tentativa de colorir o mapa com um conjunto de apenas três cores:

   => (colorir-mapa mapal '(cl c2 c3))
   nao ha' solucao...

1. Fazer uma abordagem de-cima-para-baixo ao programa colorir-mapa.

2. Escrever em Scheme o procedimento colorir-mapa, com base nos resultados da abordagem anterior.

Sugestão de abordagem

A tarefa colorir-mapa pode desenvolver-se como se fosse a tarefa procura-solucao que, para além de tomar um mapa com os países para colorir e uma paleta de cores, tem ainda em consideração, como é natural, uma solução de cores que vai criando. Uma solução começa vazia e vai crescendo à medida que se encontra uma boa cor para cada um dos países.

Sendo assim, podemos imaginar as seguintes tarefas de procura-solucao:

Enquanto há países no mapa para colorir, toma a primeira cor da paleta e verifica se é uma boa cor para o primeiro país do mapa. Uma cor será boa para atribuir a um país se nenhum dos países vizinhos, já com cor atribuída, a utiliza. Sendo uma boa cor, constituirá mais uma cor da solução que se procura, retira-se o país correspondente do mapa dos países a colorir, e retoma-se novamente a tarefa procura-solucao com a paleta com todas as cores. Sendo uma má cor, também se retoma procura-solucao, mas sem juntar nada à solução, sem retirar qualquer país do mapa, e reduzindo a paleta retirando-lhe a cor referida.
E se se atingir o fim da paleta, sem encontrar uma boa cor? Ou, de facto, não há solução possível, ou alguma das escolhas não foi bem feita. Assim, recua-se para a solução anterior e, a partir da cor na altura escolhida, procura-se uma nova cor e o processo prossegue. É claro que se tiver de recuar tanto que a solução fica vazia, então é porque não há mesmo solução possível.
A tarefa procura-solucao termina com solução, quando não houver mais países no mapa para colorir.

Da descrição anterior ainda se identificam algumas sub-tarefas:

Recuar na solução, uma tarefa que implica abandonar a última cor escolhida, retomando procura-solucao com a solução e com o mapa na situação anterior e com a paleta a partir da cor a rejeitar. Aqui identificam-se outras sub-tarefas, mapa-anterior, solucao-anterior e as-outras-cores a partir da cor rejeitada.
Determinar se uma cor é boa para um país, uma tarefa que implica verificar se nenhum dos países vizinhos já com cor atribuída, tem a cor em análise.

Aulas nº 8 e 9 - Procedimentos como Objectos de 1ª Classe

8.1

1. Definir o procedimento faz-acesso-1ista que tem como argumento um inteiro n e devolve o procedimento que acede ao i-ésimo elemento de uma lista.

   => ((faz-acesso-lista 3) '(a b c d)) -> d

2. Usando o procedimento anterior, definir os procedimentos primeiro, segundo e terceiro, que permitem aceder aos elementos correspondentes de uma lista.

8.2

1. Definir o procedimento faz-aplica-duas-vezes que tem como argumento uma função e retorna o procedimeento que aplica essa função 2 vezes ao argumento.

   => (define raiz-quarta (faz-aplica-duas-vezes sqrt)) -> raiz-quarta
   => (raiz-quarta 16)    -> 2

2. Generalise o procedimento anterior para a aplicação repetida a vezes de 1 função. O procedimeato faz-aplica-n-vezes tem como argumento uma função e um inteiro n e constrói o procedimento que aplica a função n vezes ao seu argumento.

   => (define raiz-oitava (faz-aplica-n-vezes sqrt 3)) -> raiz-oitava
   => (raiz-oitava 256)   -> 2

8.3

Usar o procedimento compose do livro para definir compose3, que tem como argumentos 3 procedimentos f, g e h e devolve a composição k tal que

   k(x) = f(g(h(x))

8.4

Usar número variável de argumentos (lambda não restrito) para definir um procedimento de composição compoe-muitos que forma a composição de um número arbitrário de procedimentos de 1 argumento.

   => ((compoe-muitos add1 add1 add1 add1) 3) -> 7 
   => ((compoe-muitos sqrt abs sub1 (lambda (n) (* n n))) 0.6) -> 0.8

8.5

Definir um procedimento map-aos-pares que é semelhante a map, com a excepção de que o procedimento argumento é um procedimento de 2 argumentos e não de 1. map-aos-pares usa os 1º e 2° elementos da lista como primeiro par de argumentos para o procedimento, depois os 2° e 3°, depois o 3° e 4°, e assim sucessivamente até esgotar a lista. Se a lista tiver menos de 2 elementos, map-aos-pares devolve a lista vazia.

   => (map-aos-pares + '(2 3 4 5 7)) -> (5 7 9 12)
   => (map-aos-pares max '(2 4 3 5 4 1)) -> (4 4 5 5 4)

8.6

O procedimento remove-caso tem 2 argumentos: um procedimento p e uma lista lis. O procedimento p é um predicado aplicável aos elementos de lis. O resultado de remove-caso é uma lista com todos os elementos de lis para os quais o predicado p seja falso. Exemplos de chamadas de remove-caso:

   (remove-caso odd? '(0 1 2 3 4 5 6))   => (0 2 4 6)
   (remove-caso null? '(() 1 2 () gato)) => (1 2 gato)

1. Escreva em Scheme o procedimento remove-caso.

2. Indique como usaria remove-caso para, a partir de uma lista de inteiros, excluir os que fossem quadrados perfeitos. Escreva uma chamada do procedimento para este efeito.

8.7

Num trabalho laboratorial está a refinar-se uma substância, usando um processo que se faz actuar repetidamente para aumentar o valor da sua concentração. A concentração da substância tem um valor inicial medido e o efeito da aplicação do processo sobre o seu valor está estabelecido segundo leis da física. Pretende-se realizar uma simulação para prever o número de vezes que será necessário desencadear o processo de refinação até que o valor da concentração seja o pretendido.

Escreva em Scheme um procedimento refina que recebe como argumentos um valor inicial para a concentração e uma função que representa o processo de refinação e devolve o valor da concentraçdo após uma refinaçdo. Exemplo de chamada:

   (refina 80 processo) => 90

Escreva em Scheme um procedimento repete-refina que recebe como argumentos um valor inicial para a concentração e uma função que representa o processo de refinação e um valor para a concentraçdo pretendida e que devolve o número de vezes que é necessário repetir o processo até obter uma concentração não inferior à pretendida.

   (repete-refina 80 processo 98) => 5

Nota: a função a usar em processo é suposta conhecida e não tem de ser especificada aqui. Os valores indicados como respostas são exemplos arbitrários.

Aula nº 10 - Dados Mutáveis

Considere os procedimentos Scheme para lidar com vectores.

10.1

Escrever successive-powers que cria um vector de comprimento n, cujos elementos são as potências do parâmetro base. O elemento com o indice O é a potência O de base.

 
   => ((successive-powers 2) 5)                    -> #(1 2 4 8 16)
   => (define succ-powers-3 (successive-powers 3)) -> succ-powers-3

   => (succ-powers-3 4)                            -> #(1 3 9 27) 
   => (succ-powers-3 5)                            -> #(1 3 9 27 81)

10.2

Escrever vector-search que tem como parâmetros o vector vec e o objecto obj e devolve o índice da primeira ocorrência de abj em vec.

 
   => (vector-search '#(g n p r a d 1 b s) 'a)       -> 4
   => {vector-search '1{29 13 96 -5 24 11 9 O 2) 11) -> 5 

   => (vector-search '#(29 13 96 -5 24 11 9 02) 10)  -> 10 não existe no vector

10.3

Escrever vector-reverse e vector-reverse! (estilo funcional imperativo). Ou seja, ...

 
   => (let ((a (vector 1 2 3 4 5)))
        (let ((b (vector-reverse a)))
          (display a) (newline)
          (display b)))

                                       -> #(1 2 3 4 5)
                                       -> #(5 4 3 2 1) 

   => (let ((a (vector 1 2 3 4 5)))
        (let ((b (vector-reverse! a)))
          (display a) (newline)
          (display b))) 

                                       -> #(5 4 3 2 1)
                                       -> #(5 4 3 2 1)