Lista 1 LISP (turma A)

Instruções

A lista devera ser entregue em um diskette com o seu RA. Todas as questoes da lista devem estar no arquivo lista1.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 4/4. As questões marcadas com ** não precisam estar 100% certas para a lista valer.

Nao use funções como reverse para fazer a questão 2, por exemplo. Defina a função l1-2 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 que conta o numero de elementos de uma lista. (se o argumento é um atomo, o valor retornado deve ser 0)

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

  2. Escreva a funcao L1-2 que reverte uma lista:

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

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

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

    (l1-3 '( (e) (r t) (w (w (r))))) -> 6

  4. Escreva a funcao L1-4 que reverte uma lista, inclusive suas sub listas (a qq profundidade)

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

  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 as sublistas com profundidade maior ou igual que a profundidade maxima substituidas pela lista vazia.

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

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

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

  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)))