(versão de 21 de Fevereiro de 2019)
Os exercícios a seguir listados devem ser resolvidos recorrendo a funções definidas por recursão. Todas as funções devem ser testadas para garantir que funcionam como é esperado.
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$.
soma_nat(5)
2. 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.
div(7,2)
div(3,4)
3. Defina a função prim_alg
que recebe como argumento um número natural e devolve o primeiro algarismo (o mais significativo) na representação decimal de $n$.
prim_alg(5629)
prim_alg(7)
4. Defina a função media_digitos
que recebe como argumento um número natural e devolve a média dos seus digitos.
media_digitos(1234)
5. 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.
num_perf(6)
num_perf(5)
6. Considere a função $f:\mathbb{N}\to\mathbb{N}$ tal que
$$
f(x)=\begin{cases}
x/2 & \textrm{se $x$ for um número par}\\
3x+1 & \textrm{caso contrário}
\end{cases}
$$
Defina a função num_it
que recebe como argumento um número natural $n$ e devolve o número de vezes que $f$ tem de ser aplicada (recursivamente) a $n$ até se atingir o número 1, i.e., devolve o número $k$ tal que
$$
\underbrace{f(f(\dots f(n)))}_{k-\textrm{vezes}} =1.
$$
A conjectura de Collatz afirma que tal programa termina sempre, facto de que não se conhece nenhuma prova ou contraexemplo.
num_it(5)
num_it(21)
num_it(11)
7. Defina a função comb
que recebe como argumentos
dois naturais $m$ e $q$, com $m\geq q$, tal que $\texttt{comb}(m,q)= \left(\!\begin{array}{c}m\\ q\end{array}\!\right)$, as combinações de $m$, $q$ a $q$. Recorde que as combinações
satisfazem a relação
$$\left(\!\begin{array}{c}m\\ q\end{array}\!\right) = \left(\!\begin{array}{c}m-1\\ q-1\end{array}\!\right) + \left(\!\begin{array}{c}m-1\\ q\end{array}\!\right)$$
para $0< q< m$.
Claro que se soubermos que $\left(\!\begin{array}{c}m\\ q\end{array}\!\right)=\frac{m!}{q!(m-q)!}$ podemos definir esta função facilmente. No entanto, não é esse o objectivo aqui.
Note ainda que a solução óbvia para este problema, embora simples, é extremamente ineficiente. Tente perceber porquê.
comb(3,2)
8. Defina a função quadrados
que recebe como argumento um número natural $n$ e devolve a lista dos $n$ primeiros quadrados perfeitos.
quadrados(6)
9. Defina a função quadrados_inv
que recebe como argumento um número natural $n$ e devolve a lista dos quadrados perfeitos até $n$, por ordem decrescente.
quadrados_inv(6)
10. Defina a função prod_lista
que recebe como argumento uma lista de inteiros e devolve o produto dos seus elementos.
prod_lista([1,2,3,4,5,6])
11. 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.
contem_parQ([2,3,1,2,3,4])
contem_parQ([1,3,5,7])
contem_parQ([])
12. 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.
todos_imparesQ([1,3,5,7])
todos_imparesQ([])
todos_imparesQ([1,2,3,4,5])
13. 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.
pertenceQ([1,2,3],1)
pertenceQ([1,2,3],2)
pertenceQ([1,2,3],3)
pertenceQ([1,2,3],4)
14. Defina a função negpos
que recebe como argumento uma lista de números inteiros $w$ e devolve a diferença entre o número de números positivos e o número de números negativos de w
.
negpos([1,-2,-1,4,6,3])
negpos([-1,-2,-3,4])
negpos([1,-1])
15. Defina a função indices_impar
que recebe como argumento uma lista de números inteiros $w$ e devolve a lista dos elementos de $w$ em posições de índice ímpar. Recorde que a primeira posição de uma lista tem índice 0, que é um número par.
indices_impar([0,1,2,3,4,5,6])
indices_impar([0,1,2,3,4,5])
indices_impar([])
indices_impar([1,2])
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$.
escolhe_pares([1,2,3,4,4,2,6,8,9])
escolhe_pares([])
escolhe_pares([1,3,5,7,9])
17. Defina a função retira_negativos
que recebe como argumento uma lista de números inteiros $w$ e devolve a lista resultante de retirar todos os números negativos de $w$.
retira_negativos([1,-2,-3,7,0])
18. Defina a função supremo
que recebe como argumento uma lista de números inteiros $w$ e devolve o supremo de $w$. Note que o supremo do conjunto vazio é $-\infty$. Para representar $\infty$ em Python pode recorrer à seguinte extensão:
from math import inf
supremo([1,2,3,-2,5,-7])
supremo([])
supremo([3,2,1])
19. Defina a função conta
que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $k$ e devolve o número de vezes que $k$ ocorre em $w$.
conta([1,2,3,2,1,2],2)
conta([1,2,3,2,1,2],4)
conta([],5)
20. 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$.
lposicoes([1,2,3,4,2,2],2)
lposicoes([1,2,3,4,2,2],7)
lposicoes([],3)
21. Defina a função pos_max
que recebe como argumento uma lista de números inteiros e devolve o índice da primeira posição onde ocorre o máximo da lista. No caso da lista vazia, devolve -1.
pos_max([1,2,3,3,2,1,3])
22. Defina a função car_pares
que recebe como argumento uma lista de números inteiros $w$ e devolve uma lista com True
nas posições onde ocorre em $w$ um número par e False
nas outras.
car_par([2,3,4,3,2,2])
car_par([3,3,3])
car_par([])
23. Defina a função apaga1
que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $k$ e devolve a lista que resulta de apagar de $w$ a primeira ocorrência de $k$ (caso exista).
apaga1([1,2,3,4,3,2,1],3)
apaga1([1,2,3,4,3,2,1],1)
apaga1([1,2,3,4,3,2,1],5)
apaga1([],3)
24. Defina a função apaga
que recebe como argumentos uma lista de números inteiros $w$ e um número inteiro $k$ e devolve a lista que resulta de apagar de $w$ todas as ocorrências de $k$.
apaga([1,2,3,4,3,2,1],3)
apaga([1,2,3,4,3,2,1],5)
apaga([],3)
25. Defina a função seleccao
que recebe como argumentos uma lista de números inteiros $w$ e um predicado $p$ e devolve a lista de todos os elementos de $w$ que verificam $p$.
seleccao([],primoQ)
seleccao([1,2,3,4,5,6,7,8,9,10],primoQ)
26. Defina a função mapeia
que recebe como argumentos uma função $f$ e uma lista $w$ e devolve a lista que resulta de aplicar $f$ a cada um dos elementos de $w$.
def suc(x):
return x+1
mapeia(suc,[0,1,2,3,4,5])
mapeia(suc,[])
27. Uma lista $s$ diz-se sufixo de uma lista $w$ se $s$ for um segmento do fim de $w$. Defina a função sufixoQ
que recebe como argumentos duas listas $s$ e $w$ e devolve True
se $s$ for sufixo de $w$ e False
em caso contrário.
sufixoQ([3,4],[1,2,3,4])
sufixoQ([3,4],[1,2,3,4,5])
sufixoQ([1,2,3],[1,2])
sufixoQ([],[1])
sufixoQ([1,2,3],[1,2,3])
28. Defina a função temPrimoQ
que recebe como argumento uma lista de listas de números inteiros $w$ e devolve True
se alguma das sublistas $w$ tem um número primo e False
em caso contrário.
temPrimoQ([[4,4,4,4],[5,4,6,7],[2,4,3]])
temPrimoQ([[4,4,4,4],[4,4,4],[],[4]])
29. Defina a função inverteLista
que recebe como argumento uma lista $w$ e devolve a mesma lista mas invertida.
inverteLista([1,2,3,4,5])
inverteLista([])
30. Defina a função lista_igualQ
que recebe como argumentos duas lista e devolve True
se as listas forem iguais e False
em caso contrário. Não pode usar a comparação ==
entre listas.
lista_igualQ([1,2,3],[1,2,3])
lista_igualQ([1,2,3],[1,3,3])
lista_igualQ([1,2],[1,2,3])
lista_igualQ([1,2,3],[1,2])
31. Defina a função sup_listas1
que recebe como argumento uma lista de listas de números inteiros $w$ e devolve o supremo de $w$.
sup_listas1([[1,2,3],[2,3,4],[2]])
sup_listas1([[7,3,2],[],[1,2,3]])
Os exercícios seguintes são de um nível de dificuldade mais elevado. Caso considere necessário, utilize algumas das funções definidas anteriormente.
32. Defina a função sup_listas2
que recebe como argumento uma lista de listas de números inteiros $w$ e devolve uma lista de comprimento igual a $w$ contendo em cada posição o supremo de cada uma das listas de $w$ na posição correspondente.
sup_listas2([[1,2,3],[4,3,2],[],[7,7,7,7]])
33. Defina a função permutacao
que recebe como argumentos duas listas $w1$ e $w2$ e devolve True
se $w1$ for uma permutação de $w2$ e False
em caso contrário.
permutacao([1,2,3],[1,2,3])
permutacao([1,2,3],[2,3,1])
permutacao([1,1,1,2,3],[1,2,3])
34. 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$.
intercala([1,2,3],[4,5,6])
intercala([1,3,5,7,9],[2,4])
35. Defina a função indPrimos
que recebe como argumento uma lista de listas de números inteiros $w=\{w_1,\dots,w_k\}$ e devolve a lista $r=\{r_1,\dots,r_n\}$, em que $r_i$ é uma lista composta pelos índices das posições dos números primos em $w_i$.
indPrimos1([[1,2,3,4,5],[11,12,13,14,15],[],[22,33,44]])
36. Defina a função separaMult3e5
que recebe como argumento uma lista de números inteiros $w$ e devolve um par (uma lista) formado por duas listas: a dos múltiplos de 5 que ocorrem em $w$ e a dos múltiplos de 3 que ocorrem em $w$.
mult3e5([1,2,3,4,5,9,15])
mult3e5([1,2,3,4,6,7,8,9])
37. Defina a função max_soma_linha
que recebe como argumento uma matriz de números inteiros e devolve o índice da primeira linha cuja a soma dos elementos é máxima.
Sugestão: Comece por definir uma função recursiva para somar os elementos de uma linha da matriz.
m=[[1,2,3],[11,11,11],[6,7,8],[10,11,12]]
max_soma_linha(m)
38. Defina a função potencia
que recebe como argumento um dígito $k$ (que não zero) e devolve o menor natural $n$ tal que $2^n$ começa por $k$.
potencia(2)
potencia(3)
39. Defina a função repete
que recebe como argumento uma lista $w$ e devolve uma lista em que o primeiro elemento de $w$ aparece repetido 1 vez, o segundo elemento aparece repetido duas vezes e assim sucessivamente.
repete([1,2,3])
40. Defina versões iterativas das funções definidas nos exercícios 1, 7, 8, 14, 15, 16, 17, 18, 19 e 20.
1. Defina em Python uma função recursiva g1
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve o número de elementos pares que existem
nas sublistas de $w$.
Por exemplo, no caso da lista [[2,4,3,1],[3,5,7],[],[8,0,6]]
a função deve devolver 5
. Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.
2. Defina em Python uma função recursiva g2
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve True
se em
todas as sublistas de $w$ existir um número positivo.
Por exemplo, no caso da lista
[[2,4,3,1],[3,-5,-7],[],[8,0,-6]]
a função deve devolver False
porque em []
não existe nenhum número positivo.
Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.
3. Defina em Python uma função recursiva g3
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve True
se alguma das listas em $w$ tiver mais números pares do que ímpares e False
em caso contrário.
Por exemplo, no caso da lista [[2,4,3,1],[3,5,7],[8,1,6]]
a função deve devolver True
pois a lista [8,1,6]
tem mais pares que ímpares. Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.
4. Defina em Python uma função recursiva g4
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve True
se todas as listas em $w$ verificam a propriedade de mais de metade dos seus elementos serem 0 e False
em caso contrário.
Por exemplo, no caso da lista [[0,0,3,0],[0,5,0],[0,0,0]]
a função deve devolver True
pois em todas as listas mais de metade dos elementos são 0. Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.
5. Defina em Python uma função recursiva g5
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve True
se cada lista em w
tiver
igual número de elementos positivos e negativos, e False
em caso contrário.
Por exemplo, no caso da lista [[2,4,-3,-1],[-3,0,7],[-8,6]]
a função deve devolver True
pois todas as listas têm igual número de elementos positivos e negativos. Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.
6. Defina em Python uma função recursiva g6
que recebe como argumento
uma lista de listas de números inteiros $w$ e devolve o número de listas em $w$ ordenadas por ordem crescente em sentido lato, ou seja, em que cada elemento é menor ou igual que o seguinte.
Por exemplo, no caso da lista [[2,2,3,0],[1,2,5,4],[2,4,4]]
a função deve devolver 1 pois só a terceira lista está ordenada. Pode, se achar conveniente, definir funções auxiliares desde que sejam funções recursivas.