BCM0505-15 - Processamento da Informação

Aula 03 – 21/02

Problema 3.1: Dados três inteiros $a,b,c$, rearranje-os em ordem crescente.

Uma versão via árvore de decisão, sem trocas de valores.

def decision_sort_3 (a: int, b: int, c: int) -> (int, int, int):
  if a <= b:
    if b <= c:
      return (a,b,c) 
    else:
      if a <= c:
        return (a,c,b)  
      else:
          return (c,a,b)  
  else:
    if b <= c:
      if a <= c:
        return (b,a,c)
      else:
        return (b,c,a)
    else:
      return (c,b,a)  

Uma segunda versão, com trocas.

def sort_3 (a: int, b: int, c: int) -> (int, int, int):
  if a > b: a, b = b, a
  if a > c: a, c = c, a
  if b > c: b, c = c, b
  return (a,b,c)

Problema 3.2: Dado um inteiro $n\geq 1$, determine o valor do $n$-ésimo número harmônico: $$H_n := 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}.$$

def harmonic (n: int) -> float:
  h = 0
  for i in range (1, n+1):
    h += 1/i
  return h

Outra versão utilizando a função sum().

def harmonic_sum (n: int) -> float:
  return sum (1/i for i in range (1, n+1))

Problema 3.3: A sequência de Fibonacci é definida para inteiros $n\geq 0$ como: $$F(n) = \begin{cases} 1 & \text{se } n\in\{0,1\},\\ F(n) = F(n-1) + F(n-2) & \text{se } n\geq 2. \end{cases}$$ Dado um inteiro $n\geq 0$, determine o valor de $F(n)$.

def fib (n: int) -> int:
  fi = fj = 1
  for k in range (2, n+1):
    fj = fj + fi
    fi = fj - fi  
  return fj

Problema 3.4: Dados $x\in\mathbb{R}$ e um inteiro $n\geq 0$, determine uma aproximação para $e^x$ calculando os primeiros $n+1$ termos da série de Taylor-Maclaurin: $$e^x \approx 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + \cdots + \frac{x^n}{n!}$$

Vamos fornecer duas versões. A primeira é uma codificação direta, extraída de série de $e^x$. Precisamos de uma função que calcule o fatorial de um número. Lembre-se que $$n! = \begin{cases} 1 & \text{se } n=0, \\ n(n-1)! & \text{se } n\geq 1. \end{cases}$$

def fact (n: int) -> int:
  f = 1
  for i in range (2, n+1): f *= i
  return f

def e_x_squander (x: float, n: int) -> float:
  e = 0.0
  for i in range (0, n+1):
    e += x**i / fact (i)
  return e  

O código acima, apesar de correto, chega a realizar inúmeras vezes as mesmas contas. Mais ainda, o cálculo do $i$-ésimo termo da série fica cada vez mais “caro.” O motivo é simples: nenhum cálculo feito previamente é reaproveitado.

Comparando dois termos genéricos adjacentes, vemos que $$\frac{x^i}{i!} \bigg/ \frac{x^{i-1}}{(i-1)!} = \frac{x^i}{i!} \cdot \ \frac{(i-1)!}{x^{i-1}} = \frac{x}{i}.$$ Ou seja, para obtermos o $i$-ésimo termo, basta multiplicarmos o $(i-1)$-ésimo por $x/i$. Não só esta multiplicação é mais “barata,” mas garante que o “custo” da geração de cada termo da série é o mesmo (num modelo uniforme). Logo, o código abaixo é mais eficiente.

def e_x (x: float, n: int) -> float:
  e = f = 1.0
  for i in range (1, n+1):
    f *= x/i
    e += f
  return e

Nota: Python disponibiliza as funções math.exp() e math.factorial().

Problema 3.5: Dados $x,\varepsilon\in\mathbb{R}$, com $0<\varepsilon\ll 1$, determine uma aproximação para $\cos x$ calculando os termos da série de Taylor-Maclaurin: $$\cos x \approx 1 - \frac{x^2}{2} + \frac{x^4}{4!} + \cdots + (-1)^k\frac{x^{2k}}{(2k)!} + \cdots$$ até que a diferença absoluta de dois termos consecutivos seja menor que $\varepsilon$, $$\left|\frac{x^{2k}}{(2k)!} - \frac{x^{2k-2}}{(2k-2)!}\right|<\varepsilon.$$

Temos que $$(-1)^k\frac{x^{2k}}{(2k)!} \bigg/ (-1)^{k-1}\frac{x^{2k-2}}{(2k-2)!} = \frac{(-1)^k x^{2k}}{(2k)!} \cdot \frac{(2k-2)!}{(-1)^{k-1} x^{2k-2}} = \frac{-x^2}{2k(2k-1)}.$$ Logo,

def cos_x (x: float, eps: float) -> float:
  c, fj, fk, k = 0.0, 0.0, 1.0, 0
  while abs(fk - fj) >= eps:
    c, fj, k = c+fk, fk, k+1
    fk *= -x*x/(2*k*(2*k-1))
  return c

Nota: Python disponibiliza a função math.cos().

Problema 3.6: Dado um inteiro positivo $n$, determine se $n$ é primo.

Lembre-se que se $n$ é primo, então $$\forall d\in\{2,3,\ldots,\lfloor\sqrt{n}\rfloor\} \implies d\not\mid n.$$

Observe que o número $1$ não é primo.

def is_prime (n: int) -> bool:
  if n <= 1: return False
  d = 2
  while d*d <= n:
    if n % d == 0: return False
    d += 1
  return True