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