Exercícios de GCC112 (LP2)

Implementar as funções abaixo usando tanto a recursão comum quanto a recursão de cauda. Pense primeiro numa solução usando recursão comum e só então pense uma solução que usa recursão de cauda:

Exercícios de Programação Funcional e Lógica

Obs.: Os itens estão mais ou menos em ordem de dificuldade.
Todos estes itens podem ser implementados usando programação lógica. Fica a seu critério adaptar o enunciado de cada um deles.
  1. menorDeDois: recebe dois valores e retorna o menor
  2. menorDeTres: recebe três valores e retorna o menor
  3. fatorial: recebe um numero natural e retorna o seu fatorial
  4. fibonacci: recebe um número inteiro positivo e retorna o n-ésimo elemento da sequência de Fibonacci
    (especificar no programa se sua sequência começa com 0 e 1 ou com 1 e 1)
  5. elemento: recebe uma lista e um número inteiro positivo para retornar o n-ésimo elemento da lista
    ex.:
    elemento 1 [3,7,4,2]   ==>   3
  6. pertence: recebe uma lista e um elemento qualquer e verifica se o elemento pertence à lista
    ex.:
    pertence 1 [3,7,4,2] ==> False
  7. nro-elementos: recebe uma lista qualquer e retorna o número de elementos na lista
    obs.: não usar a função length
  8. maior: recebe uma lista de números e retorna o maior
    obs.: não usar a função max
  9. nroOcorrencias: recebe um elemento e uma lista qualquer, retorna o número de ocorrências do elemento na lista
  10. unica-ocorrencia: recebe um elemento e uma lista e verifica se existe uma única ocorrência do elemento na lista
    ex.:
    unica_ocorrencia 2 [1,2,3,2] ==> False           unica_ocorrencia 2 [3,1] ==> False         unica_ocorrencia 2 [2] ==> True
  11. maiores-que: recebe um número e uma lista de números, retorna uma lista com os números que são maiores que o fornecido
    ex.:
    maiores_que 10 [4,6,30,3,15,3,10,7]    ==>    (30 15)
  12. concatena: recebe duas listas quaisquer e retorna um terceira lista com os elementos da primeira no início e os elementos da segunda no fim
    ex.:
    concatena [] []    ==>    []
    concatena [1,2] [3,4]    ==>    [1,2,3,4]
  13. remove: recebe um elemento e uma lista e retorna a lista sem a primeira ocorrência do elemento
  14. remover_ultimo: recebe uma lista e retorna a lista sem o último elemento
  15. remover_repetidos: recebe uma lista e retorna outra lista sem repetição de elementos
    ex.:
    remover_repetidos [7,4,3,5,7,4,4,6,4,1,2]    ==>    [7,4,3,5,6,1,2]
  16. maiores: recebe um numero natural n e uma lista de números, retorna uma lista com os n maiores números sem alterar a ordem entre os elementos
    ex.:
    maiores 4 [9,3,5,7,8,4,4,7]    ==>    [9,7,8,7]
  17. gera_sequencia: recebe um número inteiro n positivo e retorna a lista [1,-1,2,-2,3,-3, ... ,n,-n]
  18. inverte: recebe uma lista e retorna outra, que contém os mesmos elementos da primeira, em ordem invertida
  19. divide: recebe uma lista e um número natural n, retorna um par onde o primeiro elemento é uma lista com os n primeiros números da lista original e o segundo elemento é uma lista com o resto dos elementos da lista original
    ex.:
    divide [1,2,3,4] 0 ==> ([],[1,2,3,4])             divide [1,2,3,4] 2 ==> ([1,2],[3,4])
  20. intercala: recebe duas listas e retorna outra lista com os elementos das listas originais intercalados.
    ex.:
    intercala [1,2,3] [4,5] ==> [1,4,2,5,3]             intercala [] [1,2,3] ==> [1,2,3]
  21. uniao: recebe duas listas que não contenham elementos repetidos e retorna uma nova com todos os elementos das duas listas originais (sem repetição)
    ex.:
    uniao [3,6,5,7] [2,9,7,5,1]    ==>    [3,6,5,7,2,9,1]
  22. interseccao: recebe duas listas sem elementos repetidos e retorna uma lista com os elementos que são comuns às duas
    ex.:
    interseccao [3,6,5,7] [9,7,5,1,3]    ==>    [3,5,7]
  23. mesmos_elementos: recebe duas listas e verifica se elas tem os mesmos elementos
  24. sequencia: recebe dois números naturais n e m, e retorna uma lista com n elementos, onde o primeiro é m, o segundo é m+1, etc...
    ex.:
    sequencia 0 2   ==> []             sequencia 3 4   ==>   [4,5,6]
  25. insere_ordenado: recebe uma lista de números em ordem crescente e um número qualquer, retorna uma lista de números em ordem crescente com os elementos da lista inicial mais o número passado.
  26. ordenado?: recebe uma lista de números e verifica se eles estão ordenados ou não
  27. ordena: recebe uma lista com números e retorna outra lista com os números ordenados
    ex.:
    ordena [7,3,5,7,8,4,4]   ==>   [3,4,4,5,7,7,8]
  28. picos: recebe uma lista de números e retorna os números que são maiores que seus vizinhos. Considere que a lista é circular, ou seja, o início e o fim estão ligados.
    ex.:
    picos [2,3,5,10,5,5,6,2,3] ==> [10,6,3]
  29. rodar_esquerda: recebe um número natural, uma lista e retorna uma nova lista onde a posição dos elementos mudou como se eles tivessem sido "rodados"
    ex.:
    rodar_esquerda 0 [1,2,3,4,5]  ==>  [1,2,3,4,5]      rodar_esquerda 1 [1,2,3,4,5]  ==>  [2,3,4,5,1]
    rodar_esquerda 3 [1,2,3,4,5]  ==>  [4,5,1,2,3]      rodar_esquerda 9 [1,2,3,4,5]  ==>  [5,1,2,3,4]
  30. rodar_direita: recebe um número natural, uma lista e retorna uma nova lista onde a posição dos elementos mudou como se eles tivessem sido "rodados"
    ex.:
    rodar_direita 0 [1,2,3,4,5]   ==>   [1,2,3,4,5]    rodar_direita 1 [1,2,3,4,5]   ==>   [5,1,2,3,4]
    rodar_direita 3 [1,2,3,4,5]   ==>   [3,4,5,1,2]    rodar_direita 4 [1,2,3,4,5]   ==>   [2,3,4,5,1]
  31. todas_maiusculas: Recebe uma string qualquer e retorna outra string onde todas as letras são maiúsculas. Pode ser útil saber os seguintes códigos de representação de caracteres: a=97, z=122, A=65, Z=90, 0=48, 9=57, espaço=32.
    ex.: todas_maiusculas "abc 123" = "ABC 123"
  32. primeiras_maiusculas: recebe uma string qualquer e retorna outra string onde somente as iniciais são maiúsculas
    ex.:
    primeiras_maiusculas "FuLaNo bElTrAnO silva")   ==>  "Fulano Beltrano Silva"
  33. seleciona: recebe uma lista qualquer e uma lista de posições, retorna uma lista com os elementos da primeira que estavam nas posições indicadas
    ex.:
    seleciona [a,b,c,d,e,f] [1,4,3,4] ==> [a,d,c,d]
  34. separa: separa os elementos de uma lista de números nas posições com zero.
    ex.:
    separa [3,4,7,-1,0,4,7,3,0,0,9,8] ==> [[3,4,7,-1],[4,7,3],[],[9,8]]
  35. palindromo?: recebe uma string e verifica se ela é uma palíndromo ou nao
    ex.:
    palindromo? "ana"    ==> True
    palindromo? "abbccbba"    ==> True
    palindromo? "abbdbbaa"    ==> False
  36. primo?: verifica se um número é primo ou não
  37. soma_digitos: recebe um número natural e retorna a soma de seus dígitos
    ex.:
    soma_digitos 328464584658    ==>   63
  38. bolha: recebe uma lista de números e retorna a lista ordenada, pelo método da bolha (bolha burra)
  39. compactar: recebe uma lista de números e transforma todas as repetições em sub-listas de dois elementos: sendo o primeiro elemento o número de repetições encontradas e o segundo elemento é o número que repete na lista original. Os números que não repetem na lista original não devem ser alterados.
    ex.:
    compactar [2,2,2,3,4,4,2,9,5,2,4,5,5,5] ==> [3,2],[3],[2,4],[2],[9],[5],[2],[4],[3,5]]
    Em Prolog, use listas heterogêneas, ou seja, use listas apenas onde houver repetição.
  40. Dizemos que um quadrado perfeito é um numero cuja raiz quadrada é um número inteiro. Sabemos o que a raiz quadrada é um cálculo lento quando comparado à operações como adição ou multiplicação. Implemente uma função que verifica se um número é um quadrado perfeito sem usar uma função que calcula raiz quadrada.
  41. Faça um programa que encontra a representação de um número natural numa base b qualquer (1 < b < 37). Exemplo:
    muda_base 17 2 ==> "10001"
    muda_base 26 16 ==> "1A"
  42. O conjunto de todos os subconjuntos de um segundo conjunto é denominado conjuntos das partes desse segundo conjunto. Faça um programa que encontra o conjunto das partes de uma lista. Exemplo:
    partes [2,3,2,31] ==> [[],[2],[3],[31],[2,2],[2,3],[2,31],[3,31],[2,2,3],[2,2,31],[2,3,31],[2,2,3,31]]

Implementações avançadas

Após terminar todas as implementações da seção anterior, você já deverá ter acostumado seu cérebro com a programação descritiva e está pronto para tentar resolver problemas da Maratona de Programação da SBC. Obs.: Muitos dos problemas desta coleção são extremamente procedurais - cabe a você encontrar uma forma descritiva para resolvê-los.

Exercícios de Programação Funcional

  1. Implemente uma função que retorna uma lista infinita com os elementos da sequência de Fibonacci. Não é permitido usar uma função que calcule o n-ésimo elemento da sequência de Fibonacci.
  2. Implemente uma função que retorna uma lista infinita com os fatoriais de todos os números inteiros. Não é permitido usar uma função que calcule o fatorial de um número.
  3. A função concatena está formalizada abaixo. Critique a descrição e diga qual a melhor descrição para a função concatena.

Exercícios Teóricos sobre Programação Descritiva

  1. Qual a diferença entre um paradigma de programação e um estilo de programação? Cite e relacione os paradigmas e estilos de programação vistos em aula.
  2. Pesquise a maneira como os estudiosos da área de linguagens de programação classificam as várias linguagens de programação existentes até encontrar pelo menos uma definição diferente da adotada pelo seu professor. Comente as diferenças.
  3. Qual a diferença entre a programação descritiva e a programação imperativa?
  4. A existência de estruturas de repetição numa linguagem descritiva pode ser considerada normal? Por quê? Explique citando vantagens e desvantagens de se usar estruturas de repetição num programa qualquer.
  5. Explique o que é recursão de cauda, suas vantagens e desvantagens em relação à recursão comum.
  6. Qualquer linguagem de programação pode tirar proveito da recursão de cauda para produzir programas mais eficientes? Justifique.
  7. Escreva uma definição formal e recursiva para a estrutura de dados lista.
  8. Escreva uma definição formal e recursiva para a estrutura de dados árvore binária.

Exercícios Teóricos de Programação Funcional

  1. Explique o que é programação funcional. Sua explicação deve dizer qual a principal característica da programação funcional. Fale sobre suas vantagens e desvantagens fazendo uma comparação com programação procedural (incluindo os assuntos tamanho do código fonte de um programa, velocidade de execução e facilidade de criação/manutenção do programa).
  2. A linguagem Scheme apresenta uma estrutura de dados conhecida como par, explique como funciona esta estrutura de dados. Sua explicação deve dizer com armazenar e como recuperar informações usando um par (cite nomes de funções). Explique como as listas podem ser implementadas usando pares.
  3. A linguagem Scheme apresenta uma estrutura de dados conhecida como par, os pares podem implementar outras estruturas de dados, como por exemplo a lista. Com relação a isto, responda: Toda lista é um par? Todo par é uma lista? Justifique.
  4. Considere o código abaixo:
    Em Scheme: (define (positivos lista)
        (if (null? lista)
            lista
            (if (> (car lista) 0)
                (cons (car lista) (positivos (cdr lista)))
                (positivos (cdr lista)) )))
    Em Haskell: 
    positivos :: [Int] -> [Int]
positivos    []     = []
positivos    (c:r)
        | c > 0     = c:(positivos r)
        | otherwise = positivos r
    Este programa foi desenvolvido para receber uma lista de números e retornar os números positivos dela (numa lista). Este programa está correto? Se estiver, prove formalmente. Se não estiver, mostre um caso em que ele não fornece um resultado correto.
  5. Cite 5 características da programação funcional, explicando o efeito de cada uma no processo de desenvolvimento de programas.

Exercícios Teóricos de Programação Orientada a Eventos

  1. Cite as duas principais características de um programa orientado a eventos.
  2. Como a programação orientada a eventos é relacionada com os vários paradigmas e estilos de programação?

Exercícios Teóricos de Programação Lógica

  1. Explique o que é programação lógica. Sua explicação deve dizer qual a principal característica da programação lógica. Fale sobre suas vantagens e desvantagens fazendo uma comparação com programação funcional (incluindo os assuntos tamanho do código fonte de um programa, velocidade de execução e facilidade de criação/manutenção do programa).
  2. Explique o que é cláusula, predicado e proposição. Explique a ligação entre eles.
  3. Explique a função do corte numa linguagem de programação lógica. Para auxiliar sua explicação, dê um exemplo de como ele pode melhorar um programa (sugestão: mostre o funcionamento do corte no predicado maior).
  4. Explique o que é árvore de decisão. Explique como ela pode ajudar a resolver problemas combinatórios.
  5. Explique como é possível implementar um loop sem usar recursão, com o auxílio de um predicado que sempre falha. Compare essa maneira de se implementar repetição com a recursão de cauda.

Esta página é mantida por Bruno Schneider