MC600 - Prova Escrita 1 - LISP

Criada: 2003-09-01

Data da prova: 2003-08-26. Enunciado: aqui

Soluções e Critérios de Nota:

As provas foram corrigidas com rigor. Os seguintes critérios foram aplicados a todas as questões. Falta e excesso de parêntesis foram punidos com 0,5 por ocorrência. Ordem errada de argumentos também perdeu 0,5. Houve alguma confusão das pessoas entre cons, list e append. Quem trocou uma destas funções pela outra tambem perdeu 0,5. Por fim, houve uso de efeitos colaterais. Descontei 0,5 pela existência de efeito colateral; 1,0 se havia muito efeito colateral; e 1,5 se havia efeito colateral DEMAIS numa dada definição de função.

Na ausência de aplicabilidade de outros critérios, a função principal valia 1,5 e a auxiliar, 1,0. Os comentários (documentação) sobre as funções auxiliares também valeram nota! A função principal não precisava ser comentada, pois o enunciado já a descrevia.

Além destes critérios gerais, os critérios abaixo foram aplicados em cada questão específica. Seguem o gabarito oficial e os critérios.

  1. ;;; Questão (1) ante-ult
;;;
;;; Há duas soluções dignas de nota, uma direta e recursiva, e outra
;;; usando o reverso e não recursiva.  Elas representam as linhas
;;; principais de raciocínio que apareceram.

;;; solução 1 (direta, recursiva)

(defun ante-ult (lst)
  (cond
   ((null lst)          nil)
   ((null (cdr lst))    lst)
   ((null (cddr lst))   (cdr lst))
   ((null (cdddr lst))  (list (first lst) (third lst)))
   (t                   (ante-ult (cdr lst)))
   )
  )

;;; solução 2 (usa reverso, não recursiva)

(defun ante-ult (lst)
  (let ((rev (reverse lst)))
    (cond
     ((null rev)           nil)
     ((<= (length rev) 2)  (list (first rev)))
     (t                    (list (third rev) (first rev)))
     )
    )
  )

    O critério adotado foi:

    Houve confusão com a função last, que retorna uma LISTA com o último elemento da lista passada como parâmetro, ou NIL se o parâmetro for nulo. Muita gente pensou que last retornasse o último elemento apenas. Mas se fosse assim não haveria como diferenciar os valores retornados para uma lista vazia e para uma lista com NIL como último elemento. Quem usou last errado perdeu 0,5 por ocorrência.

    Também houve gente que testava, por exemplo, se car de cdr de cdr era nulo para ver se a lista tinha 2 elementos. Está errado, car de NIL é NIL mas car de alguma coisa ser NIL não implica nesta coisa ser NIL. Qualquer teste para tamanho que envolva algum car de uma lista é falho. Perderam 0,5 os que cometeram este erro.

  2. 
;;; Questao (2) produto

(defun produto (l1 l2)
  (if (null l1)
      nil
    (append (prod-aux (car l1) l2)
	    (produto  (cdr l1) l2))
    )
  )

(defun prod-aux (x lst)
  
  "Retorna uma lista com todos os pares da forma (X A) onde A percorre
os elementos de lst.  Exemplo: (prod-aux 'a '(b c)) retorna ((A B)(A
C))"

  (if (null lst)
      nil
    (cons (list x (car lst))
	  (prod-aux x (cdr lst))
	  )
    )
  )

    Aqui em geral as pessoas seguiram a idéia da solução acima. Houve uma pessoa que não usou função auxiliar e conseguiu o efeito desejado, mas ficou pouco claro. Quem desviou muito da idéia acima acabou se perdendo e cometendo vários outros erros.

    O enunciado dizia que os elementos eram distintos, mas isto não impede que algum dos elementos fosse NIL. Perdeu 0,5 quem achou que os elementos eram todos diferentes de NIL. Teve gente que se embananou bastante mas pelo menos retornou NIL quando um dos argumentos era NIL; estes receberam pelo menos 0,5.

  3. Solução:

    ;;; Questão (3) binario
;;;
;;; Para este eu bolei uma solução, mas vi duas outras boas soluções
;;; ao corrigir as provas.  A solução 2 tem uma desvantagem: roda em
;;; tempo quadrático.  As outras duas rodam em tempo linear.

;;; solução 1 (minha - linear)

(defun binario (n)
  (reverse (bin-aux n))
  )
  
(defun bin-aux (n)

  "Retorna uma lista com a representação binária de um inteiro não
negativo N, mas com o dígito mais significativo no final da lista.
Este algarismo mais significativo será sempre 1, exceto para N = 0
caso em que retorna NIL"

  (if (equal n 0)
      nil
    (cons (mod n 2)
	  (bin-aux (floor n 2))
	  )
    )
  )

;;; solução 2 (da prova - quadrática)

(defun binario (n)
  (if (equal n 0)
      nil
    (append (binario (floor n 2))
	    (list (mod n 2))
	    )
    )
  )

;;; solução 3 (da prova - linear)

(defun binario (n)
  (bin-acc n nil))

(defun bin-append (n lst)

  "Retorna a representação binária de N adicionada ao início da lista
LST passada como parâmetro"

  (if (equal n 0)
      lst
    (bin-append (floor n 2) (cons (mod n 2) lst))
    )
  )

    O critério utilizado foi o seguinte:

  4. ;;; Questao (4) sort

(defun sort (lst)
  (if (null lst)
      nil
    (insere (car lst) (sort (cdr lst)))
    )
  )

(defun insere (x lst)

  "Retorna uma lista contendo X inserido na posicao correta na lista
ordenada nao decrescente LST.  Exemplo: (insere 5 '(-3 0 7 10))
retorna (-3 0 5 7 10)"

  (if (null lst)
      (list x)
    (if (> x (car lst))
	(cons (car lst) (insere x (cdr lst)))
      (cons x lst)
      )
    )
  )

    O critério utilizado foi o seguinte:

© 2003 João Meidanis