Voltar à pagina inicial da disciplina

Lista de Exercícios

Prolog

Desenvolva predicados para:

1. Encontrar o último elemento de uma lista.
   • ?- last([1,a,6,c,5],X).
   • X = 5
   • yes
     
     
   • ?- last([r,2,w,4,t],4).
   • no
     
     
   • ?- last([q,2,e,4,5],5).
   • yes
2. Encontrar o k-ésimo elemento de uma lista.
   • ?- kth([1,3,5,7,9],3,X).
   • X = 5
   • yes
     
     
   • ?- kth([1,3,5,7,9],6,X).
   • no
     
     
   • ?- kth([1,3,5,7,9],2,3).
   • yes
3. Contar o número de vezes que um certo elemento aparece em uma dada lista.
   • ?- count([1,3,5,7,3,9],3,X).
   • X = 2
   • yes
     
     
   • ?- count([a,b,a,a,b,a,a,c,a,b],a,X).
   • X = 6
   • yes
     
     
   • ?- count([1,3,6,7,9],5,0).
   • yes
4. Remover de um lista todas as ocorrências de um dado valor.
   • ?- remove_value([1,3,5,7,3,9],3,X).
   • X = [1,5,7,9]
   • yes
     
     
   • ?- remove_value([1,a,2,a,4,5,6],a,[1,2,4,5,6]).
   • yes
     
     
   • ?- remove_value([a,c,t,g,a,t,g],a,[c,t,g,a,t,g]).
   • no
5. Remover o k-ésimo elemento de uma lista.
   • ?- remove_kth([1,3,5,7,9],3,X).
   • X = [1,3,7,9] ;
   • no
     
     
   • ?- remove_kth([1,3,5,7,9],6,X).
   • no
     
     
   • ?- remove_kth([1,3,5,7,9],2,[1,5,7,9]).
   • yes
6. Reverter uma lista.
   • ?- reverse([1,3,5,7,9],X).
   • X = [9,7,5,3,1]
   • yes
     
     
   • ?- reverse(X,[a,b,c,d]).
   • X = [d,c,b,a]
   • yes
     
     
   • ?- reverse([1,3,5,7,9],[9,7,5,3,1]).
   • yes
7. Dividir uma lista em duas partes, de modo que a primeira parte receba os N primeiros elementos e a segunda metade receba os elementos restantes.
   • ?- split([1,3,5,7,9],3,L1,L2).
   • L1 = [1,3,5]
   • L2 = [7,9] ;
   • no
     
     
   • ?- split([1,3,5,7,9],7,L1,L2).
   • L1 = [1,3,5,7,9]
   • L2 = []
   • yes
     
     
   • ?- split([1,3,5,7,9],0,L1,L2).
   • L1 = []
   • L2 = [1,3,5,7,9]
   • yes
     
     
   • ?- split([1,3,5,7,9],3,[1,3,5],[7,9]).
   • yes
8. Encontrar o menor elemento de uma lista.
   • ?- min([3,5,1,7,9],X).
   • X = 1
   • yes
     
     
   • ?- min([3,5,1,7,9],3).
   • no
     
     
   • ?- min([3,5,1,7,9],1).
   • yes
9. Determinar a união de duas listas instanciadas representando conjuntos (listas sem repetições de elementos). O resultado da união será um conjunto, logo também não terá elementos repetidos.
   • ?- union([1,2,a,5,c],[3,4,5],X).
   • X = [1,2,a,c,3,4,5]
   • yes
     
     
   • ?- union([1,2,3,4,5,6],[4,5,6,7,8],X).
   • X = [1,2,3,4,5,6,7,8]
   • yes
10. Determinar a intersecção de duas listas instanciadas representando conjuntos (listas sem repetições de elementos). O resultado da intersecção será um conjunto, logo também não terá elementos repetidos.
    • ?- intersection([1,2,a,5,c],[3,4,5],X).
    • X = [5]
    • yes
      
      
    • ?- intersection([1,2,3,4,5,6],[4,5,6,7,8],X).
    • X = [4,5,6] ;
    • no
      
      
    • ?- intersection([1,2,3],[4,5,6,7,8],X).
    • X = []
    • yes
11. Dados dois conjuntos (listas sem repetições), verificar se o primeiro é um subconjunto do segundo. Caso seja fornecido apenas um conjunto, listar, um a um, todos os possíveis subconjuntos (em qualquer ordem).
    • ?- subset([1,3,5,7,9],[5,7,9,10]).
    • no
      
      
    • ?- subset([9,1,3,7],[1,3,5,7,9]).
    • yes
      
      
    • ?- subset(X,[9,1,3,7]).
    • X = [9, 1, 3, 7] ;
    • X = [9, 1, 3] ;
    • X = [9, 1, 7] ;
    • X = [9, 1] ;
    • X = [9, 3, 7] ;
    • X = [9, 3] ;
    • X = [9, 7] ;
    • X = [9] ;
    • X = [1, 3, 7] ;
    • X = [1, 3] ;
    • X = [1, 7] ;
    • X = [1] ;
    • X = [3, 7] ;
    • X = [3] ;
    • X = [7] ;
    • X = [] ;
    • No
12. Ordenar uma lista formada apenas por números.
    • ?- sort([1,5,3,9,7],X).
    • X = [1,3,5,7,9]).
    • yes
      
      
    • ?- sort([5,1,7,3,7,9],[1,3,5,7,7,9]).
    • yes
13. Verificar se um determinado número é primo.
    • ?- prime(27).
    • no
      
      
    • ?- prime(23).
    • yes
14. Dada uma seqüência (lista) e um inteiro k, encontrar o prefixo formado pelos k primeiros elementos da seqüência.
    • ?- prefix([1,2,3,4,5,6],3,X).
    • X = [1, 2, 3] ;
    • no
      
      
    • ?- prefix([a,b,c,d,e,f],4,P).
    • P = [a, b, c, d] ;
    • yes
      
      
    • ?- prefix([a,b,c,d,e,f],5,[a,b,c,d,e]).
    • yes
      
      
    • ?- prefix([a,b,c,d,e,f],X,[a,b,c]).
    • X = 3
    • yes
      
      
    • ?- prefix([q,w,e,r,t],N,P).
    • N = 0
    • P = [] ;
    • N = 1
    • P = [q] ;
    • N = 2
    • P = [q, w] ;
    • N = 3
    • P = [q, w, e] ;
    • N = 4
    • P = [q, w, e, r] ;
    • N = 5
    • P = [q, w, e, r, t] ;
    • no
      
      
    • ?- prefix([q,w,e,r,t],7,P).
    • no
15. Dada uma seqüência (lista) e um inteiro k, encontrar o sufixo formado pelos k últimos elementos da seqüência.
    • ?- suffix([1,2,3,4,5,6],3,X).
    • X = [4, 5, 6] ;
    • no
      
      
    • ?- suffix([a,b,c,d,e,f],4,S).
    • S = [c, d, e, f] ;
    • yes
      
      
    • ?- suffix([a,b,c,d,e,f],5,[b,c,d,e,f]).
    • yes
      
      
    • ?- suffix([a,b,c,d,e,f],X,[d,e,f]).
    • X = 3
    • yes
      
      
    • ?- suffix([1,2,3,4,5,6],N,S).
      
      
    • N = 6
    • S = [1, 2, 3, 4, 5, 6] ;
      
      
    • N = 5
    • S = [2, 3, 4, 5, 6] ;
      
      
    • N = 4
    • S = [3, 4, 5, 6] ;
      
      
    • N = 3
    • S = [4, 5, 6] ;
      
      
    • N = 2
    • S = [5, 6] ;
      
      
    • N = 1
    • S = [6] ;
      
      
    • N = 0
    • S = [] ;
    • no
16. Dadas duas seqüência (listas), determinar se a segunda seqüência é uma sub-seqüência da primeira, ou seja, se os elementos da segunda seqüência podem ser encontrados na primeira de forma consecutiva. Caso apenas a primeira seqüência seja fornecida, o predicado deve gerar, uma a uma, todas as subseqüências da seqüência (numa ordem qualquer).
    • ?- subseq([a,b,c,d,e,f,g,h],[c,d,e,f]).
    • yes
      
      
    • ?- subseq([a,b,c,d,e,f,g,h],[b,d,e,f]).
    • no
      
      
    • ?- subseq([a,b,c,d,e],X).
    • X = [] ;
    • X = [a] ;
    • X = [a, b] ;
    • X = [b] ;
    • X = [a, b, c] ;
    • X = [b, c] ;
    • X = [c] ;
    • X = [a, b, c, d] ;
    • X = [b, c, d] ;
    • X = [c, d] ;
    • X = [d] ;
    • X = [a, b, c, d, e] ;
    • X = [b, c, d, e] ;
    • X = [c, d, e] ;
    • X = [d, e] ;
    • X = [e] ;
    • no
17. Eliminar os elementos iguais consecutivos de uma lista, ou seja, se uma lista possui elementos repetidos em seqüência, eles devem ser substituídos por uma única cópia do elemento.
    • compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
    • X = [a, b, c, a, d, e]
    • yes
      
      
    • compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],[a,b,c,a,d,e]).
    • yes
18. Agrupar os elementos iguais consecutivos de uma lista em sublistas. Note que a ordem dos elementos deve permanecer inalterada.
    • pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
    • X = [[a, a, a, a], [b], [c, c], [a, a], [d], [e, e, e, e]]
    • yes
      
      
    • pack([a,a,b,c,c,c],X).
    • X = [[a,a],[b],[c,c,c]];
    • no
19. Compactar uma lista de modo que elementos iguais consecutivos sejam representados como um único termo [E,N], onde E é o elemento e N é o número de repetições.
    • ?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
    • X = [[a, 4], [b, 1], [c, 2], [a, 2], [d, 1], [e, 4]] ;
    • no
20. Dada uma seqüência (lista) e um inteiro N, rotacionar a lista N elementos para a esquerda. Caso N seja negativo, a rotação deve ser realizada para a direita.
    • ?- rotate([a,b,c,d,e,f,g,h],3,X).
    • X = [d, e, f, g, h, a, b, c]
    • yes
      
      
    • ?- rotate([a,b,c,d,e,f,g,h],-3,X).
    • X = [f, g, h, a, b, c, d, e] ;
    • no
21. Dados dois números inteiros N1, N2, gerar uma lista contendo todos os inteiros do intervalo [N1,…,N2] em ordem crescente.
    • ?- range(4,7,L).
    • L = [4, 5, 6, 7]
    • yes
      
      
    • ?- range(7,4,L).
    • L = []
    • yes
      
      
    • ?- range(7,7,[7]).
    • yes
22. Dadas duas seqüência S1 e S2 (listas) e um inteiro N, determinar se S2 é uma combinação de N elementos da seqüência S1 (com os elementos listados em S2 na mesma ordem que aparecem em S1). Caso apenas a primeira seqüência seja fornecida, o predicado deve gerar, uma a uma, todas as combinações de N elementos da seqüência (numa ordem qualquer).
    • ?- combination([a,b,c,d,e,f,g],3,[b,e,f]).
    • yes
      
      
    • ?- combination([a,b,c,d,e,f,g],4,[a,e,b,f]).
    • no
      
      
    • ?- combination([a,b,c,d,e,f,g],4,C).
    • C = [a, b, c, g] ;
    • C = [a, b, d, e] ;
    • C = [a, b, d, f] ;
    • C = [a, b, d, g] ;
    • C = [a, b, e, f] ;
    • C = [a, b, e, g] ;
    • C = [a, b, f, g] ;
    • C = [a, c, d, e] ;
    • C = [a, c, d, f] ;
    • C = [a, c, d, g] ;
    • C = [a, c, e, f] ;
    • C = [a, c, e, g] ;
    • C = [a, c, f, g] ;
    • C = [a, d, e, f] ;
    • C = [a, d, e, g] ;
    • C = [a, d, f, g] ;
    • C = [a, e, f, g] ;
    • C = [b, c, d, e] ;
    • C = [b, c, d, f] ;
    • C = [b, c, d, g] ;
    • C = [b, c, e, f] ;
    • C = [b, c, e, g] ;
    • C = [b, c, f, g] ;
    • C = [b, d, e, f] ;
    • C = [b, d, e, g]
    • no
      
      
    • ?- combination([1,2,3,4],2,L).
    • L = [1, 2] ;
    • L = [1, 3] ;
    • L = [1, 4] ;
    • L = [2, 3] ;
    • L = [2, 4] ;
    • L = [3, 4] ;
    • no

Lisp

Desenvolva funções para:

2. Encontrar o n-ésimo elemento de uma lista.
   • * (nth 3 ‘(1 3 5 7 9))
   • 7
     
     
   • * (nth 0 ‘((1 3) 5 7 9 6))
   • (1 3)
3. Contar o número de vezes que um certo elemento aparece em uma dada lista.
   • * (count 4 ‘(1 2 3 4 5 6 4))
   • 2
     
     
   • * (count ‘(1) ‘((1) 2 (1) (1 2) (1)))
   • 3
     
     
   • * (count 2 ‘(1 3 6 7 9 5 0))
   • 0
4. Remover de um lista todas as ocorrências de um dado valor.
   • * (remove_value 3 ‘(1 3 5 7 3 9))
   • (1 5 7 9)
     
     
   • * (remove_value 2 ‘(1 3 5 7 3 9))
   • (1 3 5 7 3 9)
5. Remover o k-ésimo elemento de uma lista.
   • * (remove_kth 3 ‘(1 3 5 7 9))
   • (1 3 5 9)
     
     
   • * (remove_kth 0 ‘(1 3 5 7 9 6))
   • (3 5 7 9 6)
     
     
   • * (remove_kth 10 ‘(1 3 5 7 9 6))
   • (1 3 5 7 9 6)
6. Reverter uma lista.
   • * (reverse ‘(1 3 5 7 9))
   • (9 7 5 3 1)
     
     
   • * (reverse ‘((1 . 4) (3) () (1 2 3)))
   • ((1 2 3) NIL (3) (1 . 4))
7. Dividir uma lista em duas partes, de modo que a primeira parte receba os N primeiros elementos e a segunda metade receba os elementos restantes.
   • * (split 3 ‘(1 3 5 7 9))
   • ((1 3 5) (7 9))
     
     
   • * (split 7 ‘(1 3 5 7 9))
   • ((1 3 5 7 9) NIL)
     
     
   • * (split 0 ‘(1 3 5 7 9))
   • (NIL (1 3 5 7 9))
8. Encontrar o menor elemento de uma lista formada apenas por números.
   • * (min ‘(3 5 1 7 9))
   • 1
     
     
   • * (min NIL)
   • NIL
9. Determinar a união de duas listas representando conjuntos (listas sem repetições de elementos). O resultado da união será um conjunto, logo também não terá elementos repetidos.
   • * (union ‘(1 2 5) ‘(7 2 9 11))
   • (1 2 5 7 9 11)
     
     
   • * (union ‘(1 2 3 4 5 6) ‘(4 5 6 7 8))
   • (1 2 3 4 5 6 7 8)
10. Determinar a intersecção de duas listas representando conjuntos (listas sem repetições de elementos). O resultado da intersecção será um conjunto, logo também não terá elementos repetidos.
    • * (intersection ‘(1 2 5) (3 4 5))
    • (5)
      
      
    • * (intersection ‘(1 2 3 4 5 6) ‘(4 5 6 7 8))
    • (4 5 6)
      
      
    • * (intersection ‘(1 2 3) ‘(4 5 6 7 8))
    • NIL
11. Dados dois conjuntos (listas sem repetições), verificar se o primeiro é um subconjunto do segundo.
    • * (subsetp ‘(7 8 9) ‘(5 7 9 10))
    • NIL
      
      
    • * (subsetp ‘(9 1 3 7) ‘(1 3 5 7 9))
    • T
12. Ordenar uma lista formada apenas por números.
    • * (sort ‘(1 5 3 9 7))
    • (1 3 5 7 9)
      
      
    • * (sort ‘(5 1 7 3 7 9))
    • (1 3 5 7 7 9)
13. Verificar se um determinado número é primo.
    • * (prime 27)
    • NIL
      
      
    • * (prime 23)
    • T
14. Dados um dinteiro k e uma seqüência (lista), encontrar o prefixo formado pelos k primeiros elementos da seqüência.
    • * (prefix 3 ‘(1 2 3 4 5 6))
    • (1 2 3)
      
      
    • * (prefix 4 ‘(() (1 2 3) (4 . 2) (3 . NIL) 6 7 9))
    • (NIL (1 2 3) (4 . 2) (3))
      
      
    • * (prefix 0 ‘(1 2 3 4 5 6))
    • NIL
15. Dados um inteiro k e uma seqüência (lista), encontrar o sufixo formado pelos k últimos elementos da seqüência.
    • * (suffix 3 ‘(1 2 3 4 5 6))
    • (4 5 6)
      
      
    • * (suffix 4 ‘(() (1 2 3) (4 . 2) (3 . NIL) 6 7 9))
    • ((3) 6 7 9)
      
      
    • * (suffix 0 ‘(1 2 3 4 5 6))
    • NIL
16. Dadas duas seqüência (listas), determinar se a primeira seqüência é uma sub-seqüência da segunda, ou seja, se os elementos da primeira seqüência podem ser encontrados na segunda de forma consecutiva.
    • * (subseq ‘(2 3 4 5) ‘(1 2 3 4 5 6 7 8))
    • T
      
      
    • * (subseq ‘(2 4 5 6) ‘(1 2 3 4 5 6 7 8))
    • NIL
      
      
    • * (subseq ‘() ‘(1 2 3 4 5 6 7 8))
    • T
17. Eliminar os elementos iguais consecutivos de uma lista, ou seja, se uma lista possui elementos repetidos em seqüência, eles devem ser substituídos por uma única cópia do elemento.
    • * (compress ‘(1 1 1 1 2 3 3 1 1 4 5 5 5 5))
    • (1 2 3 1 4 5)
      
      
    • * (compress ‘(0 0 0 0 0 1 1 0 0 0))
    • (0 1 0)
18. Agrupar os elementos iguais consecutivos de uma lista em sublistas. Note que a ordem dos elementos deve permanecer inalterada.
    • * (pack ‘(a a a a b c c a a d e e e e))
    • ((a a a a) (b) (c c) (a a) (d) (e e e e))
      
      
    • * (pack ‘(a a b c c c))
    • ((a a) (b) (c c c))
19. Compactar uma lista de modo que elementos iguais consecutivos sejam representados como um único termo [E,N], onde E é o elemento e N é o número de repetições.
    • * (encode ‘(a a a a b c c a a d e e e e))
    • ((a 4) (b 1) (c 2) (a 2) (d 1) (e 4))
      
      
    • * (encode ‘(0 0 0 0 0 1 1 0 0 0))
    • ((0 5) (1 2) (0 3))
20. Dada uma seqüência (lista) e um inteiro N, rotacionar a lista N elementos para a esquerda. Caso N seja negativo, a rotação deve ser realizada para a direita.
    • * (rotate 3 ‘(a b c d e f g h))
    • (d e f g h a b c)
      
      
    • * (rotate -3 ‘(a b c d e f g h))
    • (f g h a b c d e)
21. Dados dois números inteiros N1, N2, gerar uma lista contendo todos os inteiros do intervalo [N1,…,N2] em ordem crescente.
    • * (range 4 7)
    • (4 5 6 7)
      
      
    • * (range 7 4)
    • NIL
      
      
    • * (range 5 5)
    • (5)