BCM0505-15 - Processamento da Informação
Laboratório 03 – 03/03
Exercícios
-
(01) Ashley ficou interessada no resultado de Diane do laboratório anterior e decidiu generalizá-lo. Ela pretende distribuir $n\geq 0$ doces a $m\geq 0$ crianças, mas agora há a possibilidade de que algumas crianças não recebam doces. Escreva uma função que recebe $n$ e $m$ e devolve o número de formas que ela pode fazer a distribuição.
Solução:
Uma ideia simples é reduzirmos o problema de Ashley ao de Diane: transformamos uma entrada ao problema de Ashley em uma entrada que seja consistente com o de Diane; aplicamos a solução obtida para o problema de Diane à entrada transformada; reinterpretarmos a resposta obtida no contexto original de Ashley. Se você ainda não estudou a solução apresentada ao problema de Diane, sugiro que o faça antes de prosseguir.Assuma que Ashley empresta um doce de cada criança antes de começar a distribuição. Ashley tem, então, $n+m$ doces para distribuir a $m$ crianças com a restrição de que cada criança recebe ao menos um doce, uma situação semelhante à de Diane. Após esta distribuição, se uma criança que recebeu somente um doce, é porque ela não recebeu nenhum dos $n$ doces; recebeu somente uma devolução ao doce que havia emprestado.
Logo, a resposta ao problema de Ashley é obtida avaliando-se $$\binom{n+m-1}{m-1}.$$
# recebe : n >= 0 e m >= 0 # devolve: $\binom{n}{m}$ def binomial (n: int, m: int) -> int: if n < m: return 0 a = b = 1 for i in range (n-m+1, n+1): a *= i for j in range (2, m): b *= j return a//b def ashley (n: int, m: int) -> int: return binomial (n+m-1, m-1)
$\square$
-
(02) Brenda está estudando como dispor rainhas – e somente rainhas – em um tabuleiro de xadrez de forma estável, sem que haja a possibilidade de ataques mútuos. Duas rainhas podem se atacar mutuamente se compartilharem uma mesma linha horizontal, vertical, ou diagonal no tabuleiro. Como primeiro passo, Brenda quer resolver o seguinte problema: em um tabuleiro $4\times 4$, cujas casas são numeradas de $(1,1)$ a $(4,4)$, dadas as posições $(x,y)$, $(z,w)$, $(u,v)$ e $(s,t)$ ocupadas por $4$ rainhas, determinar se este posicionamento é estável. Escreva uma função que resolva este problema.
Solução:
Se mais de uma rainha ocupar uma mesma linha, coluna, ou diagonal o posicionamento não é estável. Construímos uma funçãoattack()
para auxiliar na tarefa. A detecção de linhas ou colunas comuns é trivial. Para diagonais, observe que as principais são numeradas por $j-i$ e as secundárias por $n-j-i$, em que $n=4$ e $(i,j)\in\{(x,y),(z,w),(u,v),(s,t)\}.$# devolve True se ao menos dois dos valores a, b, c, d forem iguais, ou False em caso contrário def attack (a: int, b: int, c: int, d: int) -> bool: return a in (b,c,d) or b in (c,d) or c == d # devolve True se o posicionamento é estável, ou False em caso contrário def stable_queens (x: int, y: int, z: int, w: int, u: int, v: int, s: int, t: int) -> bool: return not (attack (x,z,u,s) or attack (y,w,v,t) or attack (y-x,w-z,v-u,t-s) or attack (4-y-x,4-w-z,4-v-u,4-t-s))
$\square$
-
(03) Claire deseja calcular uma aproximação para $\sin x$ via série de Taylor-Maclaurin $$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \cdots + (-1)^k\frac{x^{2k+1}}{(2k+1)!} + \cdots$$ com precisão $0<\varepsilon\ll 1$. Isto é, ela deseja somar todos os termos da série acima até que a diferença absoluta entre dois termos consecutivos seja menor que $\varepsilon$: $$\left|\frac{x^{2k+1}}{(2k+1)!} - \frac{x^{2k-1}}{(2k-1)!}\right| < \varepsilon.$$ Escreva uma função que recebe
float
s $x$ e $\varepsilon$ e devolve a aproximação desejada.Solução:
Uma codificação direta consiste em calcular cada termo da série de forma independente e somá-los até que a diferença absoluta de dois termos consecutivos seja menor que $\varepsilon$. Para isso, é conveniente utilizarmos a funçãofact()
, que calcula o fatorial de um interiro não negativo, que implementamos em sala. Por questões de clareza, ela é repetida abaixo.# calcula o fatorial de n >= 0 def fact (n: int) -> int: f = 1 while n > 1: f, n = f*n, n-1 return f # aproxima sin(x) via Taylor-Maclaurin com precisão 0 <= eps < 1 def sen_x_squander (x: float, eps: float) -> float: fj, fk = x, -x*x*x/6 k, s = 2, fj + fk while abs (fj - fk) >= eps: fj, fk = fk, (-1)**k * x**(2*k+1)/fact(2*k+1) s += fk k += 1 return s
Como já sabemos, inúmeros cálculos são feitos repetidamente no código acima. Para uma versão mais econômica, observe que $$(-1)^k\frac{x^{2k+1}}{(2k+1)!} \bigg/ (-1)^{k-1}\frac{x^{2k-1}}{(2k-1)!} = \frac{(-1)^k x^{2k+1}}{(2k+1)!} \cdot \frac{(2k-1)!}{(-1)^{k-1} x^{2k-1}} = \frac{-x^2}{2k(2k+1)}.$$ Logo, aproveitando o termo anterior para gerarmos o corrente, obtemos:
# aproxima sin(x) via Taylor-Maclaurin com precisão 0 <= eps < 1 def sen_x (x: float, eps: float) -> float: fj, fk = x, -x*x*x/6 k, s = 2, fj + fk while abs (fj - fk) >= eps: fj, fk = fk, fk * -x*x/(2*k*(2*k+1)) s += fk k += 1 return s
Nota: Python disponibiliza a função
math.sin()
. $\qquad\square$ -
(04) Danielle está trabalhando na conjectura de Collatz, que diz que dado um inteiro $n_0>0$ e definindo-se $$n_i = \begin{cases} \displaystyle\frac{n_{i-1}}{2} & \text{se $n_{i-1}$ é par,} \\ 3n_{i-1}+1 & \text{se $n_{i-1}$ é ímpar.} \end{cases}$$ para $i\geq 1$, existe um valor para $i$ tal que $n_i=1$. Apesar de ainda não conhecermos uma prova formal, a conjectura já foi testada como positiva para inúmeros valores $n_0$. Escreva uma função que recebe um
int
$n_0>0$ e devolva o menor $i\geq 0$ tal que $n_i=1$.Solução:
def collatz (n: int) -> int: i = 0 while n != 1: i, n = i+1, n//2 if n % 2 == 0 else 3*n+1 return i
$\square$
-
(05) Ellen deseja resolver um problema de busca de padrões: dados um texto $t$ e um padrão $p$, armazenados como
string
s, ela quer determinar quantas vezes $p$ ocorre em $t$. Por exemplo, se $t=$"ana e mariana gostam de banana"
e $p=$"ana"
, temos que $$\mathsf{\underline{ana}~e~mari\underline{ana}~gostam~de~b\underline{an}\underline{\underline{a}na}}$$ e, portanto, $p$ ocorre $4$ vezes em $t$. Escreva uma função que recebestring
s $t$ e $p$ e devolve o número de ocorrências de $p$ em $t$.
Nota: Umastring
é indexada como uma lista. No exemplo acima,t[0] == p[0] == 'a'
,t[1] == p[1] == 'n'
, e assim sucessivamente.Solução:
Apresentamos um algoritmo ingênuo (força bruta) que faz $O(mn)$ comparações no pior caso, em que $m=\,$len(p)
e $n=\,$len(t)
.def search (t: str, p: str) -> int: k, m, n = 0, len (p), len (t) for i in range (n - m + 1): if t[i] == p[0]: j = 1 while j < m and t[i+j] == p[j]: j += 1 if j == m: k += 1 return k
Uma variação, utilizando fatiamento de
string
s — igualmente ingênuo; mesmo consumo de tempo no pior caso.def search_alt (t: str, p: str) -> int: k, m, n = 0, len (p), len (t) for i in range (n - m + 1): if t[i:i+m] == p: k += 1 return k
$\square$
-
(06) Florence precisa de uma extensão da função que você proveu no item anterior. Especificamente, ela deseja substituir todas as ocorrências de um padrão $p$ por outro $q$ num texto $t$ – do início para o final. Alerta à possibilidade de superposições, ela deseja ter o controle de qual variante utilizar. Por exemplo, caso $t=$
"ana e mariana gostam de banana"
, $p=$"ana"
e $q=$"olga"
, a substituição com superposições é $$\mathsf{olga~e~mariolga~gostam~de~bolgolga}$$ já a sem superposições é $$\mathsf{olga~e~mariolga~gostam~de~bolgana}$$ Escreva uma função que recebe trêsstring
s $t$, $p$ e $q$ e umbool
$s$ e substitui todas as ocorrências de $p$ em $t$ por $q$ com superposições ses == True
, e sem superposições casos == False
. Nota: as substituições devem ser feitas no próprio texto $t$; para isso, use separações ([a:b]
) e concatenação (+
).Solução:
A substituição sem superposições é simples e não apresenta problemas: basta controlarmos um laço em que o parâmetro de término muda ao longo do processamento (um dos objetivos do exercício).A com superposições é ligeiramente mais delicada: se $p\neq q$ e $p$ ocorre em $q$ não somente como prefixo, o processo não tem fim! Você percebeu isso? Logo, é necessário supor que tal situação não ocorre – isto pode ser facilmente verificado à priori com a função do item anterior. Por exemplo, para $p=$
"ana"
,- se $q=p+r$, em que $r$ é uma
string
— potencialmente vazia — que não começa com"na"
e não contém $p$, a substituição deve funcionar sem problemas; - se $q=u+p+v$, em que $u$ e $v$ são
string
s com $u$ não vazia e $v$ qualquer (inclusive vazia), o processo de substituição com superposições é infinito!
O objetivo desta variação era mostrar que potenciais laços infinitos podem estar escondidos atrás da falta de hipóteses precisas.
def replace (t: str, p: str, q: str, s: bool) -> str: i, n, m, l = 0, len (t), len (p), len (q) while i < n - m + 1: if t[i:i+m] == p: t = t[:i] + q + t[i+m:] n = n - m + l i += 1 if s else l else i += 1 return t
$\square$
- se $q=p+r$, em que $r$ é uma
-
(07) Gaia deseja calcular os coeficientes de Bézout de dois inteiros positivos $m$ e $n$, isto é, inteiros $a$ e $b$ relativamente primos tais que $$am + bn = \mathsf{mdc}(m,n).$$ Escreva uma função que recebe
int
s $m>0$ e $n>0$ e devolve o par $(a,b)$.Solução:
Para explicação de como calcular $a$ e $b$, veja dedução na Solução da lista 1, exercício 3.def bezout (m: int, n: int) -> (int, int, int): ri, rj = max(m,n), min(m,n) ai, aj = 1, 0 bi, bj = 0, 1 while True: qj, rk = ri//rj, ri%rj ai, aj = aj, ai - aj*qj bi, bj = bj, bi - bj*qj if rk == 0: return rj, aj, bj ri, rj = rj, rk
$\square$
-
(08) Hannah tem sequências de $n\geq 3$ inteiros $A$ e deseja determinar o terceiro menor elemento em $A$. Ajude-a construindo uma função que resolve tal problema. Nota: não use nenhuma função que ordene os elementos de $A$.
Solução:
Vamos oferecer uma solução mais geral, que funciona para um $A$ com qualquer número de elementos.
Selen(A) < 3
, o valor devolvido é $\infty.$from math import inf as oo def trd_min (A: [int]) -> int: x = y = z = oo # menor, segundo e terceiro menores em A, respectivamente for a in A: if x > a: x, y, z = a, x, y elif y > a: y, z = a, y elif z > a: z = a return z
$\square$
-
(09) Isabella tem um inteiro $x$ e quer determinar se uma dada sequência de $n\geq 0$ inteiros $A$ possui dois elementos distintos cuja soma é igual a $x$. Em outras palavras, ela quer determinar se existem índices $0\leq i\neq j< n$ tais que $A[i]+A[j]=x$. Escreva uma função que recebe $A$ e $x$ e devolve o par $(i,j)$ em caso afirmativo, ou $(n,n)$ em caso contrário.
Solução:
Apresentamos primeiro uma solução cujo consumo de tempo é $O(n^2)$, em que $n$ é o número de elementos em $A$.def pair_sum_nn (A: [int], x: int) -> (int, int): n = len (A) for i in range (n-1): for j in range (i+1, n): if A[i] + A[j] == x: return (i,j) return (n,n)
Se ordenarmos $A$, é possível resolver o problema em tempo $O(n\log n)$.
def pair_sum_nlogn (A: [int], x: int) -> (int, int): n = len (A) A.sort() i, j = 0, n-1 while i < j: if A[i] + A[j] < x: i += 1 elif A[i] + A[j] > x: j -= 1 else: return (i,j) return (n,n)
Pergunta: por que o código acima funciona?
$\square$ -
(10) Julie está estudando platôs em sequências $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros, isto é, segmentos $[i\,..j]$ de $A$ tais que $$a_i=a_{i+1}=\cdots=a_{j-1}=a_j,$$ com $i\leq j$. Escreva uma função que recebe uma lista de
int
s $A$ e devolve o início ($\,i\,$) e o final ($\,j\,$) do maior platô em $A$. Nota: o que deve ser devolvido caso $A$ seja vazia?Solução:
CasoA = []
, o maior platô tem comprimento zero e os índices devolvidos devem satisfazer $i>j$; vamos fixar $i=0$ e $j=-1$.def plateau (A: [int]) -> (int, int): if len (A) == 0: return (0,-1) i = j = k = 0; l, n = 1, len (A) while l < n: while l < n and A[l] == A[k]: l += 1 if j - i < l-1 - k: i, j = k, l-1 k = l return (i,j)
$\square$
-
(11) Kathrin tem uma lista de notas $A=[a_0,a_1,\ldots,a_{n-1}]$ e deseja normalizá-las. Escreva uma função que recebe uma lista de
float
s $A$ e determina:- a média de $A$ $$\mu = \frac{1}{n}\sum_{i=0}^{n-1} a_i,$$
- o desvio padrão de $A$ $$\sigma = \left(\left(\frac{1}{n}\sum_{i=0}^{n-1} a_i^2\right) - \mu^2\right)^{\frac{1}{2}},$$
- uma lista $B=[b_0,b_1,\ldots,b_{n-1}]$, de notas normalizadas, tal que $$b_i = \frac{a_i-\mu}{\sigma}.$$
Devolva $\mu$, $\sigma$ e $B$.
Nota: você pode usarB.append()
para incluir novos elementos ao final de $B$, inicialmente vazia (B = []
), o criar $B$ diretamente via um predicado adequado.Solução:
def average (A: [float]) -> float: return 0 if len (A) == 0 else sum (A) / len (A) def std_dev (A: [float], mu = None) -> float: if mu == None: mu = average (A) s2 = 0 if len (A) == 0 else sum ([a*a for a in A]) / len (A) return math.sqrt (s2 - mu*mu) def normalize (A: [float]) -> (float, float, [float]): mu = average (A) sigma = std_dev (A, mu) return (mu, sigma, [(a-mu)/sigma for a in A])
$\square$
-
(12) Louise quer usar a função construída para Kathrin no item anterior para calcular conceitos de acordo com a tabela abaixo. $$\begin{array}{|c|c|} \hline \text{nota normalizada em} & \text{conceito} \\ \hline (3\sigma/2,+\infty] & A \\ \hline (\sigma,3\sigma/2] & B \\ \hline (\sigma/2,\sigma] & C \\ \hline (0,\sigma/2] & D \\ \hline (-\infty,0] & F \\ \hline \end{array}$$ Escreva uma função que recebe um desvio padrão $\sigma$ e uma lista $B$ de notas normalizadas e devolve uma lista $C$ de conceitos (como
string
s). Nota: $B$ e $C$ devem naturalmente seguir a mesma ordem.Solução:
def grade (B: [float], sigma) -> [str]: C = [] for b in B: if b > 3*sigma/2: C += ["A"] elif b > sigma: C += ["B"] elif b > sigma/2: C += ["C"] elif b > 0: C += ["D"] else: C += ["F"] return C
$\square$
-
(13) Melanie definiu uma sequência $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros como par-piramidal se $a_0$ é par, $a_1$ e $a_2$ são ímpares, $a_3,a_4$ e $a_5$ são pares, $a_6,a_7,a_8$ e $a_9$ são ímpares, e assim sucessivamente. Escreva uma função que recebe uma lista $A$ de
int
s e determina se $A$ é par-piramidal.Solução:
Observe, inicialmente, que o número $n$ de elementos em $A$ deve ser igual a $k(k+1)/2$, para algum inteiro $k\geq 1$. Resolvendo a equação em função de $k$, obtemos que $$k = \frac{-1+\sqrt{1+8n}}{2}.$$ Logo, $A$ tem um comprimento apropriado se, e somente se, a substituição de $n=\,$len (A)
na expressão acima resulta em um valor inteiro — o que pode ser checado comk % 1 == 0
. Em sendo o caso, devemos ter $k-1$ alternancias de paridade em $A$.def par_piramidal (A: [int]) -> bool: k = (-1 + math.sqrt (1 + 8*len(A)))/2 if len(A) == 0 or k % 1 != 0: return False m, parity = 0, 0 for j in range (1, int (k) + 1): for i in range (j): if A[m] % 2 != parity: return False m += 1 parity = 1 if parity == 0 else 0 # parity = int (not bool (parity)) return True
$\square$
-
(14) Nassim está estudando sequências de inteiros que possuem alternância de sinal. Uma sequência $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros é $k$-alternante, para $k\geq 1$, se:
- $A$ pode ser dividida em
n // k
blocos (de elementos contíguos) de mesmo comprimento, - os elementos de um bloco são todos positivos ($+$) ou negativos ($-$),
- blocos adjacentes possuem sinais distintos ($+-+-\cdots$ ou $-+-+\cdots$).
Por exemplo:
- $[1,2,3,-8,-8,-8,1,1,5]$ é $3$-alternante,
- $[-1,-2,3,4,-1,-2,5,6]$ é $2$-alternante,
- $[1,2,3,4,5]$ é $5$-alternante,
- $[1,2,-1,3]$ não é alternante; diremos neste caso que ela é $0$-alternante.
Escreva uma função que recebe uma lista de
int
s $A$ e devolve um valor $k\geq 0$ tal que $A$ é $k$-alternante.Solução:
Se $A$ for vazia ou possuir um zero (o único inteiro sem sinal), ela é $0$-alternante. Se $A$ for unitária, ela é $1$-alternante.def alternante (A: [int]) -> int: n = len (A) if n in (0,1): return n # determinação de k k = 1 while k < n and A[k-1] * A[k] > 0: k += 1 if k < n and A[k-1] == 0 or n % k != 0: return 0 # verificação do resto de A m = 1 if k > 1 else 0 for i in range (1, n // k): for j in range (i*k, (i+1)*k - m): if A[j] * A[j+1] <= 0: return 0 return k
$\square$
- $A$ pode ser dividida em
-
(15) Octavia aprendeu que uma lista $A[0\,..n-1]$ é unimodal se existe um índice $j\in\{-1,0,1,\ldots,n-1\}$ tal que os elementos da sub-lista $A[0\,..j]$ estão em ordem crescente e os da sub-lista $A[j+1\,..n-1]$ estão em ordem decrescente. Em outras palavras, $A$ é unimodal se $$ A[0] \leq A[1] \leq \cdots \leq A[j] > A[j+1] \geq A[j+2] \geq \cdots \geq A[n-1].$$ Escreva uma função que recebe uma lista $A$ e decide se $A$ é unimodal. Em caso afirmativo, devolva o valor $j$ determinado; em caso negativo, devolva $n$.
Solução:
Observe que se $A$ estiver em ordem crescente ou decrescente, ela é unimodal. Os valores corretos para $j$ nestes casos são $-1$ e $n-1$, respectivamente.def is_unimodal (A: [float]) -> int: n, i = len(A), 0 while i < n-1 and A[i] <= A[i+1]: i += 1 j = -1 if i == 0 else i i += 1 while i < n-1 and A[i] >= A[i+1]: i += 1 if i == n-1: j = n return j
$\square$
-
(16) Phoebe precisa de uma função que recebe uma lista $A[0\,..n-1]$ de inteiros e devolve
True
se existem elementos repetidos em $A$, ouFalse
em caso contrário. Ajude-a escrevendo tal função.Solução:
Apresentamos, inicialmente, uma solução $O(n^2)$.def repetition_nn (A: [int]) -> bool: n = len (A) for i in range (n-1): for j in range (1, n): if A[i] == A[j]: return True return False
Se ordenarmos $A$, é possível resolver o problema em tempo $O(n\log n)$.
def repetition_nlogn (A: [int]) -> bool: A.sort() for i in range (1, len(A)): if A[i-1] == A[i]: return True return False
$\square$