BCM0505-15 - Processamento da Informação

Laboratório 02 – 18/02

Exercícios

• (01) Alice vai à lanchonete e decide comprar $k$ cafés e $n$ salgados, cujos preços unitários são $p$ e $q$ reais, respectivamente. Nesta semana, há uma promoção: a compra de um café com um salgado está com $20\%$ de desconto frente ao preço usual. Escreva uma função que calcule o valor a ser pago por Alice.

  Solução:
  

  def preco_a_pagar (k: int, n: int, p: float, q: float) -> float:
    c = min (p, q)
    return 0.8*(p+q)*c + p*(k-c) + q*(n-c)
  

  Um código para teste:

  k = int (input ("Quant. cafés: "))
  n = int (input ("Quant. salgados: "))
  p = float (input ("Preço cafés: "))  
  q = float (input ("Preço salgados: "))  
  print ("Total a pagar: ", preco_a_pagar (k, n, p, q))
  

  $\square$

• (02) Beverly precisa pintar o exterior de um tanque cilíndrico de raio $r$ e altura $h$, parte de sua nova escultura. Sabe-se que cada lata de tinta com $l$ litros custa $c$ reais e possibilita a pintura de $p$ metros quadrados por litro. Escreva uma função que calcule o número de latas a ser comprado e o valor a ser pago. Nota: use math.pi e math.ceil().

  Solução:
  

  import math
  def num_latas (r: float, h: float, l: float, c: float, p: float) -> (int, float):
    n = math.ceil (2*math.pi*r*(r + h)/(p*l))
    return n, n*c
  

  $\square$

• (03) * Carol está estudando partículas que se movimentam uni-dimensionalmente em função de uma variável $t\in\mathbb{R}$ de acordo com
  $$P(t)=at^3+bt^2+ct+d,$$ um polinômio de grau $3$ em que $a,b,c$ e $d$ são reais e $a\neq 0$. Dados $P(t)$ e um intervalo $T=[t_0,t_1]\subset\mathbb{R}$, ela deseja determinar um ponto de mínimo para $P(t)$ em $T$. Escreva uma função que recebe floats $(a,b,c,d,t_0,t_1)$ e devolva um tal mínimo.
  Nota: como $T$ é um intervalo fechado (não inclui $-\infty$ ou $+\infty$) e $P(t)$ é contínuo e limitado (além de ser diferenciável) em $T$, sabemos que um mínimo (global) existe.

  Solução:
  Primeiro, criamos uma função quer avalia $P(t)$ para um dado $t$.

  def eval_poly (a: float, b: float, c: float, d: float, t: float) -> float:
    return a*t**3 + b*t*t + c*t + d
  

  Como o intervalo $T$ é fechado, $t_0$ e $t_1$ são pontos críticos; podemos avaliar $P(t_0)$ e $P(t_1)$ com a função acima. Outros pontos $t\in(t_0,t_1)$ são críticos se $P'(t)=0$. A derivada de $P(t)$ com relação a $t$ é $$P'(t) = 3at^2 + 2bt + c.$$ Podemos determinar as raízes de $P'(t)$ utilizando a fórmula de Bháskara que codificamos na aula anterior — repetimos o código abaixo para conveniência.

  import math
  # recebe : coeficientes a, b e c do polinômio ax^2+bx+c
  # devolve: (n,x1,x2), em que n é o número de raízes reais; x1 <= x2 são raízes reais (caso n >= 1) ou NaN em caso contrário
  def bhaskara (a: float, b: float, c: float) -> (int, float, float):
    delta = b*b - 4*a*c
    if delta < 0:
      return (0, math.nan, math.nan)
    elif delta == 0:
      z = -b/(2*a)
      return (1, z, z)
    else:
      return (2, (-b - math.sqrt(delta))/(2*a), (-b + math.sqrt(delta))/(2*a))
  

  Uma condição suficiente para um ponto crítico $z\in(t_0,t_1)$ ser um mínimo local é que $P''(z) > 0$. Temos que $$P''(t) = 6at + 2b.$$ Observe, no entanto, que tal condição não é necessária: existem pontos críticos $z$ que são mínimos locais para os quais $P''(z) = 0$. Estes mínimos podem ser detectados calculando-se $P(z-\varepsilon)$ e $P(z+\varepsilon)$ e verificando-se que $$P(z-\varepsilon) > P(z) \qquad \text{e} \qquad P(z+\varepsilon) > P(z)$$ para $0<\varepsilon\ll 1$ pequeno.

  É conveniente construirmos uma função com as condições acima.

  def is_local_min (a: float, b: float, c: float, d: float, t: float) -> bool:
    if 6*a*t + 2*b > 0: return True
    eps = 1e-8
    x = eval_poly (a, b, c, d, t-eps)
    y = eval_poly (a, b, c, d, t)
    z = eval_poly (a, b, c, d, t+eps)
    if x > y and z > y:
      return True
    else:
      return False
  

  Estamos supondo que $\varepsilon=1.0\times 10^{-8}$ é pequeno o suficiente e que $t_0 < t-\varepsilon < t+\varepsilon < t_1$. A determinação de um mínimo para $P(t)$ em $T$ é feita abaixo.

  def min_cubic_poly (a: float, b: float, c: float, d: float, t0: float, t1: float) -> float:
    p0 = eval_poly (a, b, c, d, t0)
    p1 = eval_poly (a, b, c, d, t1)
    pm = min (p0, p1)
    n, pj, pk = bhaskara (3*a, 2*b, c)
  
    if n >= 1:
      if p0 < pj < p1 and is_local_min (a, b, c, d, pj):
        pm = min (pm, pj)
    if n == 2:
      if p0 < pk < p1 and is_local_min (a, b, c, d, pk):
        pm = min (pm, pk)    
  
    return pm
  

  $\square$

• (04) Diane pretende distribuir $n\geq 0$ doces a $m\geq 0$ crianças de forma que cada criança receba ao menos um doce. Escreva uma função que recebe ints $n$ e $m$ e devolve o número de formas que ela pode fazer a distribuição.

  Solução:
  Imagine que os $n=20$ doces estão arrumados em sequência em cima de uma mesa $$***************\,$$ e que temos $m=4$ crianças. A distribuição de $4$ doces à primeira, $6$ à segunda, $3$ à terceira e $7$ à quarta pode ser indicada pelas barras adicionadas à sequência de doces. $$|\,||*******\,$$ Em geral, distribuir $n_1+n_2+\cdots+n_m=n$, com $n_i\geq 1$, doces a $m$ crianças equivale à colocação de $m-1$ barras dentre $n-1$ espaços possíveis. Logo, desejamos calcular $\binom{n-1}{m-1}$, o número de formas de selecionarmos um subconjunto com $m-1$ elementos à partir de um conjunto de cardinalidade $n-1$.

  Desenvolvemos um código para cálculo de coeficientes binomiais no laboratório passado. Para conveniência, fornecemos outra versão abaixo.

  # 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
  

  $\square$

• (05) Emily deseja calcular a distância euclidiana entre dois pontos, $x=(x_1,x_2,x_3)$ e $y=(y_1,y_2,y_3)$ no $\mathbb{R}^3$. Escreva uma função que recebe $6$ floats ($x_1,x_2,x_3,y_1,y_2,y_3$) e devolve $\|x-y\|_2$. Nota: use a função math.sqrt().

  Solução:
  

  import math
  # recebe : x=(x1,x2,x3) e y=(y1,y2,y3) 
  # devolve: ||x-y||
  def dist (x1: float, x2: float, x3: float, y1: float, y2: float, y3: float) -> float:
    return math.sqrt ((x1 - y1)**2 + (x2 - y2)**2 + (x3 - y3)**2)
  

  Nota: Python disponibiliza a função math.dist().
  $\square$

• (06) Felicity deseja testar se alguns inteiros $0\leq k\leq 999$ são palíndromos, isto é, descrevem o mesmo valor quando lidos da esquerda para a direita ou vice-versa. Por exemplo, $8$ e $707$ são palíndromos; $10$ e $301$ não o são. Escreva uma função que recebe $k$ e determina se $k$ é palíndromo.

  Solução:
  Como $0\leq k\leq 999$, podemos fornecer um código específico para este caso.

  # recebe : um inteiro k entre 0 e 999
  # devolve: True se k é palindromo, ou False em caso contrário
  def pal_especial (k : int) -> bool:
    if k < 10: 
      return True
    elif k < 100:
      if k // 10 == k % 10:
        return True
      else:
        return False
    else:
      if k // 100 == k % 10:
        return True
      else:
        return False
  

  Outra versão, igualmente específica para o caso em que $0\leq k\leq 999$.

  # recebe : um inteiro k entre 0 e 999
  # devolve: True se k é palindromo, ou False em caso contrário
  def pal_especial2 (n):
    k = n
    m = k % 10; k //= 10
    if k > 0:
      m = m * 10 + k % 10; k //= 10
    if k > 0:
      m = m * 10 + k % 10; k //= 10
    return m == n
  

  $\square$

• (07) Gabrielle deseja estender o estudo de Felicity para todos os inteiros não negativos. Ajude-a escrevendo uma função que recebe um int $k$ e determina se $k$ é palíndromo.

  Solução:
  Diferente do caso do exercício anterior, agora precisamos de um laço.

  # recebe : um inteiro k 
  # devolve: True se k é palindromo, ou False em caso contrário
  def palindromo (k : int) -> bool:
    m, n = k, 0
    while m > 0:
      k = 10 * k + m % 10
      m = m // 10
    if k < 0:
      n *= -1
    return k == n
  

  $\square$

• (08) Heather está estudando números perfeitos, inteiros $k>0$ que são iguais à soma de seus divisores menores que $k$. Por exemplo, $6 = 1 + 2 + 3$ e $28 = 1 + 2 + 4 + 7 + 14$ são perfeitos; $9\neq 1 + 3$ e $32\neq 1 + 2 + 4 + 8 + 16$ não o são. Escreva uma função que recebe um int $k>0$ e determina se $k$ é perfeito.

  Solução:
  

  # recebe : um inteiro k 
  # devolve: True se k é perfeito, ou False em caso contrário
  def perfeito (k: int) -> bool:
    m = 0
    for d in range (1, k//2 + 1):
      if k % d == 0:
        m += d
    return k == m
  

  $\square$

• (09) Islay está estudando somas da forma $$S(a,b,c,n) := 1 + (-1)^c\frac{1}{b^a} + (-1)^{2c}\frac{1}{b^{2a}} + \cdots + (-1)^{(n-1)c}\frac{1}{b^{(n-1)a}} = \sum_{i=0}^{n-1} (-1)^{ic}\frac{1}{b^{ia}},$$ para $a,b\in\mathbb{R}$, $c\in\{0,1\}$ e $n\geq 0$ inteiro. Escreva uma função que recebe $a,b,c$ e $n$ e devolve $S(a,b,c,n)$.

  Solução:
  Um código direto:

  # recebe : floats a, b e ints c, n; c em {0,1} e n >= 0 
  # devolve: S(a,b,c,n)
  def soma_islay_fst (a: float, b: float, c: int, n: int) -> float:
    s = 0
    for i in range (n):
      s += (-1)**(i*c) + 1/(b**(i*a))
    return s
  

  Uma variação mais sucinta (utilizando a função sum), igualmente direta:

  def soma_islay_snd (a: float, b: float, c: int, n: int) -> float:
    return sum ((-1)**(i*c) + 1/(b**(i*a)) for i in range (n))  
  

  Uma análise ligeiramente mais fina revela que os códigos acima (ambos corretos) realizam mais contas que o necessário. Comparando dois termos consecutivos de $S(a,b,c,n)$, temos que $$(-1)^{ic}\frac{1}{b^{ia}} \bigg/ (-1)^{(i-1)c}\frac{1}{b^{(i-1)a}} = \frac{(-1)^{ic}}{b^{ia}} \cdot \frac{b^{(i-1)a}}{(-1)^{(i-1)c}} = \frac{(-1)^c}{b^a}.$$ Logo, podemos obter o $i$-ésimo termo multiplicando o termo anterior por $(-1)^c/b^a$, que é constante.

  # recebe : floats a, b e ints c, n; c em {0,1} e n >= 0 
  # devolve: S(a,b,c,n)
  def soma_islay (a: float, b: float, c: int, n: int) -> float:
    s, t, f = 1, 1, (-1 if c == 1 else 1) / b**a
    for i in range (1, n):
      t *= f; s += t    
    return s
  

  $\square$

• (10) Jennifer deseja converter inteiros não negativos da base decimal ($10$) para a binária ($2$). Escreva uma função que recebe um int $n\geq 0$ e devolve a expansão binária de $n$ como uma string. Por exemplo, para $n=18$, devolva "10010". Nota: utilize + para concatenar strings.

  Solução:
  Para qualquer inteiro $n\geq 0$, existem dígitos binários $b_0,b_1,\ldots,b_k$, com $k=\max\{1,\lceil\log n+1\rceil\}$ tais que $$n = b_k 2^k + \cdots + b_1 2^1 + b_0 2^0.$$ Os dígitos $b_i$ podem ser determinados via divisões sucessivas de $n$ por $2$, tomando-se os restos de tais divisões.

  # recebe : um inteiro n >= 0
  # devolve: a representação de n em binário, como uma string
  def dec_to_bin (n: int) -> str:
    b = ""
    while n > 0:
      b = str (n % 2) + b
      n = n // 2
    return b if b != "" else "0"      
  

  $\square$

• (11) Kelly deseja realizar o oposto a Jennifer, convertendo inteiros não negativos de binário para decimal. Escreva uma função que recebe uma string $b$ e devolve a expansão decimal de $b$ em um int. Por exemplo, para $b=$"1101001", devolva $105$.

  Solução:
  Para uma entrada $b=$"$b_k b_{k-1} \cdots b_0$", temos que a resposta é $n = b_k 2^k + b_{k-1} 2^{k-1} + \cdots + b_0 2^0$.

  # recebe : uma string b representando um valor inteiro n em binário
  # devolve: o valor de n em decimal
  def bin_to_dec (b: str) -> int:
    n, p = 0, 1
    for i in range (len (b) - 1, -1, -1):
      n = n + int (b[i]) * p
      p = p * 2
    return n
  

  Observe que tratamos uma representação binária vazia ("") como zero. $\qquad\square$

• (12) Lucy deseja calcular $\mathsf{mdc}(m,n)$, o máximo divisor comum a dois inteiros positivos $m$ e $n$. Por questões de performance, ela deseja que o cálculo seja feito utilizando-se o algoritmo de Euclides. Escreva uma função que recebe ints $m>0$ e $n>0$ e devolve $\mathsf{mdc}(m,n)$ como desejado.

  Solução:
  Considere que $m\geq n$, fazendo a troca dos valores se necessário. Se $n|m$ ($n$ divide $m$), temos que $n=\mathsf{mdc}(m,n)$. Em caso contrário, $m=q_1 n + r_1$, para inteiros $q_1>0$ e $n>r_1>0$. Um divisor de $n$ também é um divisor de $m$ se dividir $r_1$. Em particular, obtemos que $\mathsf{mdc}(n,r_1) = \mathsf{mdc}(m,n)$. Observe que trata-se do mesmo problema para valores menores.

  Tomando $r_{-1}=m$, $r_0=n$ e aplicando a ideia acima de forma recorrente, obtemos $$r_{-1} > r_0 > r_1 > r_2 > r_3 > \cdots > r_k > r_{k+1} = 0.$$ Logo, $r_k=\mathsf{mdc}(r_{k-1},r_k)=\mathsf{mdc}(r_{k-2},r_{k-1})=\cdots=\mathsf{mdc}(r_{-1},r_{0})$.

  Este algoritmo foi desenvolvido por Euclides ($\approx$ 300 A.C.).

  # recebe : m > 0 e n > 0 
  # devolve: mdc (m, n)
  def mdc (m: int, n: int) -> int:
    if m < n: m, n = n, m
    while True:
      r = m % n
      if r == 0: return n
      m, n = n, r
  

  Nota 1: $m$ e $n$ tais que $\mathsf{mdc}(m,n)=1$ são ditos relativamente primos.

  Nota 2: Python 3.8 introduz o operador := (walrus) que permite atribuir valores a variáveis dentro de uma expressão. Abaixo, um código para o algoritmo de Euclides utilizando este novo operador.

  # recebe : m > 0 e n > 0 
  # devolve: mdc (m, n)
  def mdc_with_walrus_operator (m: int, n: int) -> int:
    if m < n: m, n = n, m
    while (r := m % n) > 0:
      m, n = n, r
    return n 
  

  Nota 3: Python disponibiliza a função math.gcd().
  $\square$

• (13) Megan deseja calcular $\mathsf{mmc}(m,n)$, o mínimo múltiplo comum a dois inteiros positivos $m$ e $n$. Escreva uma função que recebe ints $m>0$ e $n>0$, utiliza a função para cálculo de $\mathsf{mdc}(m,n)$ do item anterior, e devolve $\mathsf{mmc}(m,n)$.

  Solução:
  
  Seja $d=\mathsf{mdc}(m,n)$. Temos, claramente, que $\frac{1}{d}mn$ é um múltiplo comum a $m$ e $n$. Afirmamos que ele é o menor. Logo, $$\mathsf{mdc}(m,n) \cdot \mathsf{mmc}(m,n) = mn.$$

  # recebe : m > 0 e n > 0 
  # devolve: mmc (m, n)
  def mmc (m: int, n: int) -> int:
    return m*n // mdc (m, n)
  

  Nota: Vamos provar a afirmação acima. Seja $d=\mathsf{mdc}(m,n)$ tal que $m=pd$ e $n=qd$, com $p$ e $q$ inteiros e $\mathsf{mdc}(p,q)=1$. Seja $c=\mathsf{mmc}(m,n)=n\ell$. Temos que $m|c$ se e somente se $m|n\ell$, o que ocorre se e somente se $p|q\ell$. Como $p$ e $q$ são relativamente primos, $p|\ell$. Por definição, $c$ é o menor múltiplo comum a $m$ e $n$. Logo, $\ell=p$ e, assim, $c=np=\frac{1}{d}mn$. $\qquad\square$

• (14) Natalie está trabalhando com frações continuadas, expressões da forma $$\frac{n}{d} = a_0 + \frac{1}{\displaystyle a_1+\frac{1}{\displaystyle a_2+\frac{1}{\displaystyle \ddots+\frac{1}{\displaystyle a_k}}}}$$ em que $n$ e $a_0$ são inteiros e $d$ e os demais coeficientes $a_1,a_2,\ldots,a_k$ são inteiros positivos. Escreva uma função que recebe $n$ e $d>0$ e determine a fração continuada equivalente ao número racional $\frac{n}{d}$, imprimindo os coeficientes $a_0,a_1,\ldots$ em ordem.
  Exemplo: $$\frac{159}{46} = 3 + \frac{21}{46} = 3 + \frac{1}{\displaystyle \frac{46}{21}} = 3 + \frac{1}{\displaystyle 2 + \frac{4}{21}} = 3 + \frac{1}{\displaystyle 2 + \frac{1}{\displaystyle \frac{21}{4}}} = 3 + \frac{1}{\displaystyle 2 + \frac{1}{\displaystyle 5 + \frac{1}{\displaystyle 4}}}$$ e assim, $a_0=3, a_1=2, a_3=5, a_3=4$.

  Solução:
  

  # recebe : inteiros n e d > 0, numerador e denominador da fração n/d
  # devolve: uma lista [a0, a1, ..., ak], coeficientes da expansão como fração continuada de n/d
  def continued_fraction (n: int, d: int) -> [int]:
    A = []
    while True:
      A.append (n // d)
      r = n % d
      if r == 0: return A
      n, d = d, r
  

  Nota: compare esta solução com a do Exercício (12).
  $\square$

• (15) Oksana recebeu uma lista de inteiros $A=[a_0,a_1,a_2,\ldots,a_{k-1}]$ enviada por Natalie, em que $a_1,a_2,\ldots,a_{k-1}$ são positivos. Oksana imagina tratar-se de coeficientes de uma fração continuada e ela deseja saber qual a fração representa por $A$. Escreva uma função que recebe a lista $A$ e devolve inteiros $n$ e $d>0$ tais que $\frac{n}{d}$ é o racional equivalente.

  Solução:
  

  # recebe : uma lista [a0, a1, ..., ak], coeficientes da expansão como fração continuada de n/d
  # devolve: inteiros n e d > 0, numerador e denominador da fração n/d  
  def reverse_continued_fraction (A: [int]) -> (int, int):
    k = len (A)
    if k == 1: return (A[0],1)
    n, d = 1, A[k-1]
    for i in range (k-2,0,-1):
      x = A[i] * d + n
      n = d
      d = x
    n = A[0]*d + n
    return (n,d)
  

  $\square$

• (16) Pam está investigando tabuleiros de xadrez generalizados, grades $n\times n$ com posições especificadas por pares de números $(x,y)$, com $1 \leq x,y \leq n$. Ela aprendeu que um passo da peça cavalo deve seguir o formato da letra L (maiúscula): à partir de uma posição inicial, o cavalo desloca-se primeiro duas posições em uma direção (Norte, Sul, Leste ou Oeste) e depois, desloca-se uma posição em uma direção ortogonal à primeira. Um passo é válido se a posição final estiver dentro do tabuleiro e seguir tais regras.
  Escreva uma função que recebe um inteiro $n>0$ e quatro inteiros $1\leq x,y,z,w\leq n$ e determina se é possível a um cavalo partindo da posição inicial $(x,y)$ atingir a posição final $(z,w)$ em até dois passos válidos.

  Solução:
  
  Codificamos as possíveis movimentações do cavalo na função rth_move() — um resultado semelhante poderia ter sido alcançado mediante o uso de uma lista. A função is_valid() verifica se, ao final de uma movimentação, o cavalo encontra-se dentro do tabuleiro. Observe que ambas as funções são definidas dentro de horse_steps() e, portanto, são locais.

  def horse_steps (n, x, y, z, w):
    def rth_move (r):
      if   r == 0: return (+2,+1)
      elif r == 1: return (+2,-1)
      elif r == 2: return (-1,+2)
      elif r == 3: return (-1,-2)
      elif r == 4: return (-2,-1)
      elif r == 5: return (-2,+1)
      elif r == 6: return (+1,-2)
      else:        return (+1,+2)
  
    def is_valid (n, x, y, i, j):
      return 1 <= x+i <= n and 1 <= y+j <= n
  
    if x == z and y == w: 
      return True
    for k in range(8):
      (i,j) = rth_move (k)
      if is_valid (n, x, y, i, j):
        if x+i == z and y+j == w:
          return True
        else:
          for l in range(8):
            (p,q) = rth_move (l)
            if is_valid (n, x+i, y+j, p, q) and x+i+p == z and y+j+q == w:
              return True
    return False
  

  $\square$