Todas as funções devem definidas imperativamente e devem ser testadas para garantir que funcionam como é esperado. Cada exercício sobre listas pode (e deve) ser resolvido de várias maneiras:
len para determinar a guarda do ciclo1. 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 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.
num_perf(6)
num_perf(5)
5. 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(27)
6. Defina a função quadrados que recebe como argumento um número natural $n$ e devolve a lista dos $n$ primeiros quadrados perfeitos $n$.
quadrados(6)
7. 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)
8. 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])
9. 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([])
10. 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])
11. 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)
12. Defina a função maior_dif que recebe como argumento duas listas não vazia de números inteiros $w1$ e $w2$, de igual comprimento, e devolve a diferença entre o maior número inteiro de $w1$ e o menor número inteiro de $w2$.
maior_dif([1,2,3],[4,5,6])
maior_dif([4,5,6],[1,2,3])
13. 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])
14. 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])
15. 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])
16. 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])
17. Defina a função posicoesMaximo que recebe como argumento uma lista de inteiros $w$ e devolve a lista das posiçoes onde ocorre maior elemento.
posicoesMaximo([1,2,3,2,1,2,3])
posicoesMaximo([])
18. 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)
19. 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)
20. 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([])
21. 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)
22. 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)
23. Defina a função seleccao que recebe como argumentos uma lista de números inteiros $w$ e um predicado e devolve a lista de todos os elementos de $w$ que verificam esse predicado.
seleccao([],primoQ)
seleccao([1,2,3,4,5,6,7,8,9,10],primoQ)
24. 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,[])
25. 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])
26. 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([])
27. Defina a função lista_igualQ que recebe como argumentos duas listas 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,2,2])
lista_igualQ([],[])
lista_igualQ((1,2,3),[1,2])
28. 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 3 que ocorrem em $w$ e a dos múltiplos de 5 que ocorrem em $w$.
separaMult3e5([1,2,3,4,5,9,15])
separaMult3e5([1,3,9,12,4,2])
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.
29. 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])
permutacao([1,2,3],[1,2,3,4])
30. 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,3,5],[2,4,6])
intercala([],[1,2,3])
intercala([1,3,5],[2,4])
31. 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)
1. 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([[1,4,6],[2],[8,8,8,8],[]])
temPrimoQ([[1,2,6],[4],[8,8,8,8],[]])
temPrimoQ([[4,4,4,4],[],[4,4,4,4]])
2. Defina a função prodMatriz que recebe como argumento uma matriz de números e devolve o produto de todos os seus elementos.
prodMatriz([[1,2,3],[4,5,6]])
3. Defina a função mediaColunasPares que recebe uma matriz e devolve a média dos elementos nas colunas de índice par da matriz.
mediaColunasPares([[1,2,3,4,5],[5,4,3,2,1],[0,2,4,6,5]])
mediaColunasPares([[1,2,3,4],[4,3,2,1]])
4. 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$.
indPrimos([[1,2,3,4],[2,3,5,7,11],[],[4,6,8,9]])
5. Defina a função transposta que recebe como argumento uma matriz e devolve a sua trasposta.
transposta([[1,2,3],[4,5,6]])
6. 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$.
from math import inf
sup_listas1([])
sup_listas1([[],[],[]])
sup_listas1([[5,2,5],[3,8,1],[0]])
7. 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([])
sup_listas2([[],[],[]])
sup_listas2([[5,2,5],[3,8,1],[0]])
8. 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])
9. Defina a função produtoMatrizes que recebe como argumento duas matrizes e devolve a sua matriz produto. Verifique que a dimensão das matrizes recebidas é tal que é possível realizar o seu produto (se tal não for possível, a função deve devolver mensagem de erro).
Sugestão: Pode, se assim o entender, definir uma função auxiliar para multiplicar a linha de uma matriz pela coluna da outra matriz.
produtoMatrizes([[1,2],[3,4]],[[1,2,3],[4,5,6]])
1. Considere o problema de calcular a área por baixo de um gráfico de uma função $f$ (o integral de $f$) num intervalo $[a,b]$.
Defina a função aproximaIntegral que recebe como argumentos uma função $f$, os extremos do intervalo de integração $a$ e $b$, e um parâmetro $n$ e calcula uma aproximação do integral de $f$ nesse intervalo.
A ideia consiste em dividir o intervalo $[a,b]$ em $n$-subintervalos consecutivos, com $n$ suficientemente grande para se obter a aproximação desejada:
$$ [a,b] = [x_0,x_1]\cup\dots\cup[x_{n-1},x_n] $$e aproximar a função em cada um dos intervalos $[x_{i-1},x_i]$ por $f(x_{i-1})$.
Nestas condições, o valor do integral é aproximado por:
$$ \sum_{i=1}^{n} (x_i-x_{i-1}) f(x_{i-1}). $$Escolhendo todos os intervalos com a mesma amplitude
$$ d = \frac{b-a}{n} $$tem-se que $x_i = x_{i-1}+d$, ou então, que $x_i= a + i\times d$, e chega-se a $$ \sum_{i=1}^{n} d\times f(a+(i-1)\times d). $$
ou seja,
$$ d\times\sum_{i=1}^{n} f(a+(i-1)\times d). $$def g(x):
return (1+x)**(-1)
aproximaIntegral(g,0,1.5,5)
aproximaIntegral(g,0,1.5,500000)
2. Considere o problema de calcular a raíz de uma equação não linear num intervalo $[a,b]$ com aproximação de pelo menos $\epsilon$, usando o método da bissecção a seguir descrito. Defina a função bisseccao que recebe como argumento uma função $f$, os extremos do intervalos $a$ e $b$, e a aproximação $\epsilon$ e devolve a aproximação da solução da equação $f(x)=0$ no intervalo, caso exista.
O método da bissecção é um método iterativo para encontrar raízes de funções baseado no Teorema do Valor Intermédio. Pretende-se encontrar uma solução da equação $f(x)=0$, admitindo que $f$ é contínua em $[a,b]$ e que $f(a)f(b)<0$.
Tome-se $a_0=a$, $b_0=b$, $I_0=[a_0, b_0]$ e repita-se iterativamente o seguinte processo.
Seja $x_i$ o ponto médio do intervalo $I_i$. Uma das três condições seguintes verifica-se:
No terceiro caso, não é preciso fazer mais nada. Para os outros dois casos, repete-se o processo considerando, no primeiro caso, $I_{i+1}=[a_i, x_i]$, e no segundo caso, $I_{i+1}=[x_i, b_i]$.
Aplicando este procedimento sucessivamente, é calculada uma sequência de intervalos $I_0\supset I_1\supset\ I_2\supset\dots$ onde a raíz $r\in I_k$ para todo o $k$. O procedimento termina quando a amplitude do intervalo for menor do que a aproximação pretendida $\epsilon$ e devolve o ponto médio desse intervalo. Note que a amplitude do intervalo se reduz a metade em cada iteração.
import numpy as np
def h(x):
return x**2-np.e**x
bisseccao(h,-1,0,0.00001)
1. Diz-se que uma lista tem elemento maioritário se mais de metade dos seus elementos forem iguais. Defina a função maioritario que recebe como argumento uma lista $w$ e devolve o elemento maioritário de $w$, caso exista, e o número de ocorrências desse elemento. No caso de a lista não ter elemento maioritário a função não devolve valor.
maioritario([3,2,3,3,3,1])
maioritario([1,2,3,2])
maioritario([4,4,4,3,5,4,5,6,4,4,3,4])
x,n=maioritario([4,4,4,3,5,4,5,6,4,4,3,4])
x
n
2. O reconhecimento de padrões consiste em verificar se uma determinada sequência padrão $p$ ocorre numa outra sequência $s$. Considere que, quer a sequência padrão $p$, quer a sequência $s$, são listas. Pretende-se verificar se os elementos da lista $p$ ocorrem na lista $s$, pela mesma ordem e consecutivamente. Apresentam-se em seguida alguns exemplos.
Defina uma função reconhece que recebe como argumento duas listas $p$ e $s$ e devolve True se o padrão $p$ ocorre na sequência $s$, e devolve False em caso contrário.
reconhece([1,2,3],[1,2,3,4,5])
reconhece([4,3,4],[2,1,4,2,3,4,5])
reconhece([5,2,7],[5,2,7])
reconhece([9,4],[3,2,4,2,9,4])
reconhece([7,4,3],[7,4,7,4,3,7,2,7])
3. Defina a função e1 que recebe como argumento uma matriz quadrada de números inteiros e calcula a lista dos pares $[i,j]$ tais que a soma da linha $i$ é igual à soma da coluna $j$.
Sugestão: defina uma função auxiliar eqsum tal que eqsum(m,i,j) seja True no caso de a soma da linha i de m ser igual à soma da coluna j e False em caso contrário.
e1([[3, 4, 5], [5, 3, 2], [2, 3, 4]])
4. Defina a função e2 que recebe como argumento uma matriz de números inteiros e calcula a lista dos pares $[i,x]$ tais que a soma dos elementos da linha $i$ é igual a $x$.
e2([[3,4,5],[5,3,2],[2,3,4]])
5. Defina a função triangularSupQ que recebe como argumento uma matriz quadrada de números inteiros e determina se a matriz é triangular superior (isto é, todos os elementos abaixo da diagonal principal são nulos).
triangularSupQ([[1,2,3],[0,4,5],[0,0,6]])
triangularSupQ([[1,0,0],[2,3,0],[4,5,6]])
6. Defina a função e3 que recebe como argumento uma matriz quadrada de números inteiros e calcula o produto de todos os elementos pares acima da diagonal principal.
e3([[3, 4, 5], [5, 3, 2], [2, 3, 4]])
7. Defina a função e4 que recebe como argumento uma matriz quadrada de números inteiros e calcula o produto de todos os elementos ímpares abaixo da diagonal principal.
e4([[3, 4, 5], [5, 3, 2], [2, 3, 4]])
8. Defina imperativamente em Python uma função particaoQ que dada uma lista de números $w$ devolve True se existe $I\subseteq\{0,\dots,\tt{len}(w)\}$ tal que $\sum_{i\in I} w[i]$ é igual a $\sum_{i\notin I} w[i]$, e False em caso contrário.
Nomeadamente, particaoQ([1,2,3,3,1]) deverá ser True (pois 2+3 é igual 1+3+1), mas particaoQ([1,2,4]) deverá ser False.
Neste exercício não pode usar definições por compreensão nem métodos. As únicas operações sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), cálculo do comprimento (len) e concatenação (+). Pode usar range.
9. Defina imperativamente em Python uma função quants que dada uma lista $w$ de números positivos e um número alvo $k$ não negativo devolve a lista de todas as listas de quantidades naturais $[q_0,\dots,q_{\tt{len}(w)-1}]$ tais que
$$
\sum_{i=0}^{\tt{len}(w)-1} (q_i\ast w[i]==k).
$$
Nomeadamente, quants([1,2,5],6) deverá ser [[6,0,0], [0,3,0], [2,2,0], [4,1,0], [1,0,1]].
Neste exercício não pode usar definições por compreensão nem métodos. As únicas operações sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), cálculo do comprimento (len) e concatenação (+). Pode usar range.
10. Sabe-se que para todo o número inteiro positivo $n$ existem inteiros não-negativos $i,j,k$ que são palíndromos (na habitual notação decimal) tais que $n=i+j+k$. Por exemplo, tem-se $31415926=31400413+15251+262$.
Defina imperativamente em $Python$ uma função threepals que dado um número inteiro positivo n devolva um triplo de palíndromos (i,j,k) cuja soma seja n. Pode usar, sem a definir, uma função auxiliar palQ que dado um número natural devolve True se se tratar de um palíndromo, e False caso contrário.
11. Pelo teorema fundamental da aritmética, todo o número inteiro positivo tem uma factorização única como produto de números primos.
Defina imperativamente em Python uma função factor que dado um inteiro positivo ${\tt n}$ devolva a factorização de ${\tt n}$ na forma de uma lista de pares ${\tt [(p}_{\tt 1}{\tt , e}_{\tt 1}\tt{), . . . , (p}_{\tt k}{\tt , e}_{\tt k}{\tt)]}$ onde cada ${\tt p}_{\tt i}$ é um número primo e cada ${\tt e}_{\tt i}$ é um inteiro positivo tais que ${\tt n}={\tt p}_{\tt 1}^{{\tt e}_{\tt 1}}\times\dots\times {\tt p}_{\tt k}^{{\tt e}_{\tt k}}$.
Por exemplo, factor(200) deverá ser [(2, 3), (5, 2)].
12. Suponha que a cada lista de números $w$ da forma $[a_0,a_1,\dots,a_n]$ se associa o polinómio $p_w(x)=a_0+a_1x+a_2x^2+\dots+a_n x^n$.
Defina imperativamente em Python uma função prod que dadas duas listas de números u e v devolve a lista r tal que $p_r(x)=p_u(x)\times p_v(x)$. Por exemplo, prod([3,1,1],[1,2]) deverá resultar na lista [3,7,3,2], já que se tem $(3+x+x^2)\times (1+2x)=3+7x+3x^2+2x^3$.
Neste exercício não pode usar definições por compreensão nem métodos. As únicas operações sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), comparação com a lista vazia (==[]), cálculo do comprimento (len) e concatenação (+).