Introdução à Programação em Python

(4) Exercícios programação funcional e multiparadigma

Carlos Caleiro, Jaime Ramos

Dep. Matemática, IST - 2016

(versão de 27 de Fevereiro de 2019)

1 - Programação funcional

Nos exercícios seguintes não deve utilizar recursão, nem composição iterativa, nem composição sequencial de comandos. As funções devem ser definidas utilizando as primitivas map, reduce, all, any, filter, nest, fixedpoint podendo também recorrer a outras funções sobre listas que considere necessárias, nomeadamente definições por compreensão. Recorde que para poder o combinador reduce precisa de o importar:

In [4]:
from functools import reduce

e que os combinadores nest e fixedpoint foram definidos no Notebook 07 sobre Programação Funcional e comparação entre paradigmas de programação:

In [5]:
def nest(f,n,x):
    return reduce(lambda a,b:f(a),range(n),x)
In [6]:
def fixedpoint(f,x):
    while x!=f(x):
        x=f(x)
    return x

1. Defina a função soma_nat que recebe como argumento um número natural $n$ e devolve a soma de todos os números naturais até $n$.

In [51]:
soma_nat(10)
Out[51]:
55

2. Defina a função quadrados que recebe como argumento um número natural $n$ devolve a lista dos $n$ primeiros quadrados perfeitos.

In [12]:
quadrados(5)
Out[12]:
[1, 4, 9, 16, 25]

3. Defina a função quadrados_inv que recebe como argumento um número natural $n$ devolve a lista dos $n$ primeiros quadrados perfeitos, por ordem decrescente.

In [21]:
quadrados_inv(5)
Out[21]:
[25, 16, 9, 4, 1]

4. Defina a função num_perf que recebe como argumento um número inteiro positivo e devolve True se esse número for um número perfeito e False em caso contrário. Recorde que um número perfeito é um número natural que é igual à soma de todos os seus divisores próprios, isto é, a soma de todos os divisores excluindo o próprio número. Pode se assim o entender, definir funções auxiliares, desde que definidas no paradigma funcional.

In [26]:
num_perf(6)
Out[26]:
True
In [27]:
num_perf(5)
Out[27]:
False

5. Defina a função inverte_lista que recebe como argumento uma lista e devolve essa lista invertida.

In [32]:
inverteLista([1,2,3])
Out[32]:
[3, 2, 1]

6. Defina a função indices_pares que recebe como argumento uma lista de números inteiros $w$ e devolve a lista dos elementos de $w$ em posições pares.

In [34]:
indices_pares([4,3,7,1,2,9])
Out[34]:
[4, 7, 2]

7. Defina a função triangulo que recebe como argumento um número natural $n$ e devolve uma lista em que o primeiro elemento é a lista [1], o segundo elemento é a lista [1, 2] e assim sucessivamente até a $n$.

In [58]:
triangulo(4)
Out[58]:
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]

8. Defina a função prod_lista que recebe como argumento uma lista de números inteiros e devolve o produto dos seus elementos.

In [63]:
prod_lista([2,4,6])
Out[63]:
48
In [64]:
prod_lista([])
Out[64]:
1

9. Defina a função conta que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $x$ e devolve o número de ocorrências de $x$ em $w$.

In [73]:
conta([1,2,3,2,1,2],1)
Out[73]:
2

10. Defina a função contem_parQ que recebe como argumento uma lista de números inteiros $w$ e devolve True se $w$ contém um número par e False em caso contrário.

In [80]:
contem_parQ([3,5,7,9,11])
Out[80]:
False
In [81]:
contem_parQ([3,4,7,9,11])
Out[81]:
True

11. Defina a função todos_imparesQ que recebe como argumento uma lista de números inteiros $w$ e devolve True se $w$ contém apenas números ímpares e False em caso contrário.

In [82]:
todos_imparesQ([3,5,7,9,11])
Out[82]:
True
In [83]:
todos_imparesQ([3,4,7,9,11])
Out[83]:
False

12. Defina a função pertenceQ que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $n$ e devolve True se $n$ ocorre em $w$ e False em caso contrário.

In [87]:
pertenceQ([1,2,3,4],5)
Out[87]:
False
In [88]:
pertenceQ([1,2,3,4],2)
Out[88]:
True

13. Defina a função int_listaQ que recebe com argumento uma lista e devolve True se a lista for constituida exclusivamente por números inteiros e False em caso contrário.

In [116]:
int_listaQ([1,2,-3,4,9])
Out[116]:
True
In [117]:
int_listaQ([1.1,3,-3])
Out[117]:
False

14. Defina a função nat_listaQ que recebe com argumento uma lista e devolve True se a lista for constituida exclusivamente por números naturais e False em caso contrário.

In [121]:
nat_listaQ([1,2,3,-1])
Out[121]:
False
In [122]:
nat_listaQ([1,2,3,4])
Out[122]:
True

15. Defina a função int_lista_listaQ que recebe com argumento uma lista e devolve True se a lista for constituida exclusivamente por listas de números inteiros e False em caso contrário.

In [126]:
int_lista_listaQ([[1,2,3],[4,5,6]])
Out[126]:
True
In [127]:
int_lista_listaQ([[1,2,3],["ola",3]])
Out[127]:
False
In [128]:
int_lista_listaQ([1,[1,2,3],[4,5,6]])
Out[128]:
False

16. Defina a função escolhe_pares que recebe como argumento uma lista de números inteiros $w$ e devolve a lista dos elementos pares de $w$.

In [130]:
escolhe_pares([1,2,3,4,5,6,7,8])
Out[130]:
[2, 4, 6, 8]

17. Defina a função int_matrizQ que recebe como argumento uma lista $m$ e devolve True se $m$ for uma matriz de números inteiros e False em caso contrário.

In [138]:
int_matrizQ([[1,2],[4,5],[7,8]])
Out[138]:
True
In [139]:
int_matrizQ([[1,2],[4],[7,8]])
Out[139]:
False
In [141]:
int_matrizQ([[1,2],[4],7])
Out[141]:
False

18. Defina a função retira_negativos que recebe como argumento uma lista de números inteiros e devolve a lista resultante de retirar todos os números negativos.

In [135]:
retira_negativos([1,2,3,-4,5,-6])
Out[135]:
[1, 2, 3, 5]

19. Defina a função div que recebe como argumentos dois números naturais $m$ e $n$ e devolve o resultado da divisão inteira de $m$ por $n$. Neste exercício não pode recorrer às operações aritméticas de multiplicação, divisão e resto da divisão inteira.

In [217]:
div(7,2)
Out[217]:
3

20. Defina a função prim_alg que recebe como argumento um número natural $n$ e devolve o primeiro algarismo (o mais significativo) na representação decimal de $n$.

In [215]:
prim_alg(8935)
Out[215]:
8

21. Defina a função media_digitos que recebe como argumento um número natural e devolve a média dos seus digitos.

In [213]:
media_digitos(14276)
Out[213]:
4.0

22. Defina a função permutacao que recebe como argumentos duas listas $w1$ e $w2$ e devolve True se $w2$ for permutação de $w1$, e devolve False em caso contrário.

In [191]:
permutacao([1,2,3],[3,2,1])
Out[191]:
True
In [193]:
permutacao([1,1,2,3],[3,2,1])
Out[193]:
False

23. Defina função comprimento que recebe como argumento uma lista e devolve o seu comprimento. Não pode, como é óbvio, recorrer à função len.

In [195]:
comprimento([2,3,5,2,2])
Out[195]:
5

24. Defina a função intercala que recebe como argumentos duas listas $w1$ e $w2$ e devolve a lista resultante de intercalar os elementos de $w1$ com os de $w2$.

In [11]:
intercala([1,3,5],[2,4,6])
Out[11]:
[1, 2, 3, 4, 5, 6]
In [12]:
intercala([1,3,5,7],[2])
Out[12]:
[1, 2, 3, 5, 7]

25. Defina a função apaga que recebe como argumentos uma lista de inteiros $w$ e um número inteiro $k$ e devolve a lista que resulta de apagar de $w$ todas as ocorrências de $k$.

In [199]:
apaga([1,2,1,3,1,4,1,5],1)
Out[199]:
[2, 3, 4, 5]

26. Defina a função maximo que recebe como argumento uma lista não vazia de números inteiros e devolve o seu máximo.

In [203]:
maximo([14,-1,5,19,0])
Out[203]:
19

27. Defina a função lposicoes que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $k$ e devolve a lista das posições em que $k$ ocorre em $w$.

In [206]:
lposicoes([1,2,3,4,12,2,4,3,2],2)
Out[206]:
[1, 5, 8]

28. Defina a função pos_max que recebe como argumento uma lista de números inteiro e devolve a lista das posições onde ocorre o máximo da lista.

In [208]:
pos_max([1,2,3,1,2,3])
Out[208]:
[2, 5]

29. Defina a função ind_pares que recebe como argumento uma lista de listas de números inteiros $w=\{w1,...,wn\}$ e devolve a lista $r=\{r1,...,rn\}$ em que $ri$ é composta pelas posições dos números pares em $wi$.

In [35]:
pos_pares([[1,2,3],[4,5,6],[7,8,9,10]])
Out[35]:
[[1], [0, 2], [1, 3]]

30. Defina a função fibonacci que recebe como argumento um número natural $n$ e devolve o $n$-ésimo número da sucessão de Fibonacci. Recorde que a sucessão dos números de Fibonacci é definida recursivamente como se segue:

  • fibonacci(1)=1
  • fibonacci(2)=1
  • fibonacci(n+2)= fibonacci(n+1)+ fibonacci(n)
In [55]:
fibonacci(1)
Out[55]:
1
In [56]:
fibonacci(2)
Out[56]:
1
In [57]:
fibonacci(3)
Out[57]:
2
In [58]:
fibonacci(6)
Out[58]:
8

2 - Programação nos três paradigmas

Os exercícios que se seguem devem ser resolvidos combinando de forma inteligente os uso dos três paradigmas de de programação estudados anteriormente: programação recursiva, programação imperativa e programação funcional. Cada problema deve ser abordado de acordo com a seguinte estratégia:

  • identificar componentes independentes;
  • para cada componente, identificar o paradigma a aplicar;
  • resolver cada componente isoladamente;
  • definir a função pretendida combinando todas as funções auxiliares encontradas anteriormente.

Não se esqueça de proteger a função contra argumentos indesejados.

1. Defina a função wierd_prod que recebe como argumento uma lista de números inteiros e devolve o produto do primeiro elemento, pelo quadrado do segundo, pelo cubo do terceiro, e assim sucessivamente.

In [66]:
weird_prod([5,2,4])
Out[66]:
1280
In [67]:
weird_prod([])
Out[67]:
1
In [68]:
weird_prod(['ola'])

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-68-154b4d17e26f> in <module>()
----> 1 weird_prod(['ola'])

<ipython-input-65-9172a88072de> in weird_prod(w)
      1 def weird_prod(w):
----> 2     assert(int_listaQ(w))
      3     return produto(w)

AssertionError:

2. Defina uma função pascal que recebe como argumento um número natural $n$ e devolve a $n$-ésima linha do triângulo de Pascal. Recorde que os elementos do triângulo de Pascal podem ser definidos pelas relações seguintes, em que $p_{k,i}$ denota o elemento na posição $i$ da linha $k$:

  • $p_{k,0} = 1$
  • $p_{k,k} = 1$
  • $p_{k,i} = p_{k-1,i-1} + p_{k-1,i}$
In [79]:
pascal(1)
Out[79]:
[1]
In [80]:
pascal(2)
Out[80]:
[1, 1]
In [81]:
pascal(3)
Out[81]:
[1, 2, 1]
In [82]:
pascal(4)
Out[82]:
[1, 3, 3, 1]
In [83]:
pascal(5)
Out[83]:
[1, 4, 6, 4, 1]
In [84]:
pascal(5.1)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-84-591b6c776a7b> in <module>()
----> 1 pascal(5.1)

<ipython-input-78-3103f943ec81> in pascal(n)
      1 def pascal(n):
----> 2     assert(natQ(n))
      3     return linha(n)

AssertionError:

3. Considere o seguinte algoritmo para ordenação de listas. Dada uma lista $w$, encontrar os dois primeiros elementos consecutivos de $w$ que não estão ordenados e trocá-los. Repetir este procedimento até a lista ficar ordenada (este algoritmo é uma variante do algoritmo de ordenação bubblesort). Defina uma função troca que implemente este algoritmo de ordenação sobre listas de inteiros.

In [92]:
troca([1,4,3,5,2,6])
Out[92]:
[1, 2, 3, 4, 5, 6]

4. Defina a função determinante que calcula o determinante de uma matriz quadrada $M$ de dimensão $n$, de acordo com a fórmula: $$ det (M) = \sum_{i=1}^{n} (-1)^{i+j}\, m_{i,j}\, det(M_{ij}) $$ em que $j$ é um índice de uma das colunas de $M$ e $M_{ij}$ representa a matriz $M$ à qual foram retiradas a linha $i$ e a coluna $j$.

In [171]:
determinante([[1,2],[4,5]])
Out[171]:
-3
In [172]:
determinante([[1,5,3,4],[7,3,4,2],[9,1,3,2],[4,5,6,7]])
Out[172]:
174
In [173]:
determinante([[1,2,3],[4,5,6]])

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-173-0439d99a8372> in <module>()
----> 1 determinante([[1,2,3],[4,5,6]])

<ipython-input-170-3999b3c6ae6a> in determinante(m)
      1 def determinante(m):
----> 2     assert(sq_int_matrixQ(m))
      3 
      4     return det(m)

AssertionError:

3 - Exercícios complementares

Nos exercícios deste grupo não pode usar recursão, ciclos ou atribuições. Pode usar, sem necessidade de os definir, os combinadores map, reduce, any, all, filter, nest, fixedpoint, bem como definições lambda e por compreensão.

1. Diz-se que uma função f separa dois valores a e b se f(a) é zero e f(b) não, ou vice-versa.
Implemente funcionalmente em Python uma função maxseps que dada uma lista de funções funs calcula o maior valor natural n para o qual cada par de valores distintos em 1,...,n é separável por alguma função em funs.

2. Implemente funcionalmente em Python o algoritmo de ordenação mergesort.

3. Considere o seguinte programa Python

In [ ]:
def f(w):
    def g(i):
        if 2*i>len(w) or w[i-1]!=w[len(w)-i]:
            return i
        else:
            return i+1
        
    return 2*fixedpoint(g,1)>len(w)

Implemente funcionalmente em Python, tirando partido da função f definda acima a função palQ que dado um número natural devolve True se se tratar de um palíndromo, e False em caso contrário.

4. Atente nas seguintes definições:

  • inteiros positivos $n_1,\dots,n_k$ dizem-se coprimos entre si se para qualquer número primo $p$, se $p$ divide $n_i$ então $p$ não divide $n_j$ para nenhum $j\neq i$;
  • se a factorização em primos de um inteiro positivo é $n = p_1^{e_1}\times\dots\times p_k^{e_k}$ então define-se o seu radical $\text{rad}(n) = p_1\times\dots\times p_k$ , i.e., $rad(n)$ é o produto dos primos que dividem $n$;
  • a qualidade $q(a,b,c)$ de um triplo $a,b,c$ de inteiros positivos coprimos entre si é definida por $$ q(a,b,c) = \frac{\log(c)}{log(\text{rad}(a).\text{rad}(b).\text{rad}(c))} $$
    A conjectura abc, um famoso e importante resultado em aberto em teoria de números, afirma que para qualquer $\epsilon> 0$ existe apenas uma quantidade finita de triplos $a, b, c$ inteiros positivos e coprimos entre si, com $a + b = c$, tais que $q(a, b, c) > 1 + \epsilon$.
    Implemente funcionalmente em Python a função best_abc que dado um inteiro positivo c devolve (a, b, q), onde a, b, c é o triplo com o maior valor de q(a,b,c) de entre os triplos possíveis, fixado c, e q é essa mesma qualidade.
    Pode assumir definida a função factor que dado um inteiro positivo n devolva a factorização de n como produto de números primos na forma de uma lista de pares ${\tt [(p1, e1), . . . , (pk, ek)]}$ onde cada ${\tt pi}$ é um número primo e cada ${\tt ei}$ é um inteiro positivo tais que ${\tt n}={\tt p1}^{\tt e1}\times\dots\times {\tt pk}^{\tt ek}$.

5. Um problema de satisfatibilidade é representado por uma matriz m com entradas 0, 1, ou -1. Dado um tal um problema, uma solução de m consiste de uma lista s com entradas 1 ou -1, de comprimento igual ao número de colunas de m, que satisfaça a seguinte condição:

  • para cada linha i de m existe pelo menos uma coluna j tal que m[i][j] é igual a s[j].

Por exemplo, [1, -1, 1] é uma solução do problema [[1,1,1],[-1,-1,0]]. Implemente funcionalmente em Python uma função sols que dado um problema de satisfatibilidade devolve a lista de todas as suas soluções.

6. Um problema de cobertura é representado por uma matriz quadrada m com entrada numéricas. Dado um tal problema, uma cobertura de m consiste de uma lista c com valores em 0,...,len(m)-1 que satisfaça a seguinte condição:

  • para cada entrada não nula m[i][j] de m tem-se que i ocorre em c, ou j ocorre em c, ou ambos.

Por exemplo, [0,2] é uma coberta de matriz [[0,1,0],[1,0,1],[0,1,0]]. Esta cobertura não é mínima, no entanto, pois [1] é também uma cobertura do mesmo problema.

Implemente funcionalmente Python uma função mincover que dado um problema de cobertura devolve uma sua cobertura de tamanho mínimo.