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$

Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!“
(desconheço a autoria; agradeço a indicação)