Lista 2 LISP (turma B)

Instruções

Esta lista deverá ser entregue no dia 29/5. As questões marcadas com ** não precisam estar 100% certas para a lista valer.

Questões

1. Suponha que voce tem uma lista da forma ( ( aluno1 aluno2 ...) ((nota1-1 nota1-2 nota1-3) (nota2-1 nota2-2 nota2-3) ...)) onde aluno1 é um string com o nome do aluno, e nota1-* sao numeros ou nil. A nota final do aluno é a media das duas melhores notas. nill significa que o aluno nao fez aquela prova e portanto tirou 0.

   Escreva a funcao passou que dado uma lista acima imprime o Nome e nota final dos alunos que tiraram mais que 5.

2. Escreva a funcao atomos que dado uma lista de atomos, retorna uma lista de pares onde o primeiro elemento é um atomo da lista original, e o segundo é a quantidade de vezes que ele aparece. O programa deve percorrer a lista original apenas uma vez (suponha que ela tem varios milhares de atomos)

   Ex: (l2-2 '(a b a d a b b a d d b a ) retorna ((a 5) (b 4) (d 3))

3. Um grafo direcionado é representado por uma lista ( (a b) (a d) (b f) ...) onde (a b) representa que existem um arco de a para b. Escreva a funcao loops que dado uma lista acima retorna a lista dos vertices do grafo de onde saem loops de tamanho 1. Isto é, o vertice A deve estar na lista a ser retornada se existir um vertice X tal que exista um arco de A par X e de X para A. (Obviamente se de A sai um loop de tamanho 1 entao de X tambem sai um.) Pense em usar uma Hash table para representar o grafo.

4. ** Escreva a funcao lago que recebe uma matriz e uma lista com duas coordenadas (indices na matriz). A matriz é para ser interpretada como um mapa topografico de uma região quadriculada. O valor do elemento (x y) da matriz é a altura do terreno no ponto (x y).

   O segundo argumento da função é um ponto (na região quadriculada) onde esta chovendo. Assuma que a cada ponto da região, a agua da chuva sempre irá para o ponto adjacente de menor altura. Isto é, se os valores das alturas em torno de um ponto (i j) são

   5 7 3 4 . 8 8 4 7 entao a agua ira para o ponto cuja altura é 3 (i-1 j+1). Se dois pontos tem a mesma altura, a agua irá para um deles aleatoriamente.

   A função lago devera retornar uma lista das coordenadas onde se formará um lago devido a chuva. Isto é o ponto no quadriculado para onde a agua da chuva ira e de onde ela não poderá mais se mover. A função deverá retornar nil se a agua da chuva atingir alguma das bordas da região.