Lista 1 LISP (turma B)

Instruções

A lista devera ser entregue em um diskette com o seu RA. Todas as questoes da lista devem estar no arquivo lista3.lsp. Cada questão pede para voce definir uma função, defina-a com o nome pedido pois a correção será automatica. Voce pode definir suas funcoes auxiliares no arquivo.

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

Nao use funções como butlast para fazer a questão 4, por exemplo. Defina a função l1-4 usando recursao etc.

Definições:

Vamos definir profundidade de um atomo em uma lista como sendo:

e assim por diante.

Ex: a profundidade de a na lista ((a) b c) é 2 pois a e' um elemento de um elemento da lista.

Da mesma forma podemos definir a profundidade de uma sublista em um lista. Assim a sublista (b c) tem profundidade 2 na lista (a ((b c) d) e)

Outra forma de pensar nisso é ver a lista (de listas) como sendo uma arvore.

A lista (a ((b c) d) e) pode ser vista como uma arvore

+ / | \ a + e / \ + d / \ b c Assim a profundidade de d na arvore é 2, e da lista (b c) tambem é 2.

Vamos definir a profundidade de uma lista como sendo a profundidade de seu atomo mais profundo.

Questões

  1. Escreva a funcao L1-1 dado uma lista retorna apenas os elementos nas posições impares (o primeiro, o terceiro, etc)

    Ex: (l1-1 '( e r t (w q) )) retorna (e t)

  2. Escreva a funcao L1-2 que retorna a media dos elementos numericos de uma lista:

    Ex: (l1-2 '(4 r 6 (2 q))) retorna 5

    Note que o 2 não entrou na media, pois o ele pertence a uma lista, que não é um elemento numerico.

  3. Escreva a funcao L1-3 que soma o numero de emementos numericos de uma lista, incluindo ai todos as sublistas a qq profundidade dessa lista.

    Ex: (l1-3 '(5 r t (1 2))) retorna 8

    (l1-3 '( (e) (r 4) (2 (2 (r))))) -> 8

  4. Escreva a funcao L1-4 que dado uma lista retorna esta lista sem o ultimo elemento.

    Ex: (l1-4 '((e r) t w q)) -> ((e r) t w )

  5. Escreva a funcao L1-5 que dado duas listas verifica se a segunda 'e alguma sublista da primeira (em alguam profundidade)

    Ex: (l1-5 '((a b) (c) (c (e f))) '(e f)) -> T

    (l1-5 '((a b) (c) (c (e f))) '(c (e f))) -> T

    (l1-5 '((a b) (c) (c (e f))) '(c e f)) -> NIL

  6. Escreva a funcao l1-6 que dado uma lista e um numero (a profundidade maxima), retorna a primeira lista com todos os atomos com profundidade maior ou igual que a profundidade maxima nas sublistas de profundidade maxima.

    Ex: (l1-6 '((a b) (c) (c (e f) g )) 2) -> ((a b) (c) (c e f g))

    (l1-6 '(a b c) 2) -> (a b c)

    (l1-6 '((a b) (c) (c (e f) g )) 1) -> (a b c c e f g)

  7. ** Vamos assumir que uma arvore de busca binaria é representada em LISP da seguinte forma

    ( chave valor subarvore-a-esquerda subarvore-a-direita)

    assim (4 a (2 b (1 h nil nil) (3 c nil nil)) (7 a nil (9 g nil nil))) representa a arvore:

    4,a / \ 2,b 7,a / \ \ 1,h 3,c 9,g Escreva a funcao l1-7 que dado um arvore binaria e uma chave (um numero) retorna a arvore binaria sem o nó que contem tal chave.

    Ex: se a arvore acima esta armazenada no atomo xx entao: (l1-7 xx 2) retorna (por exemplo) (4 a (1 h nil (3 c nil nil)) (7 a nil (9 g nil nil)))