DESAFIO Considere a série para o número e=sumn=0^infty 1n!.
(a) Escreva um algoritmo para calcular o valor aproximado de e com os t primeiros termos da série.
(b) Obtenha a complexidade do seu algoritmo fornecendo o número de adições (incluindo subtrações), multiplicações e divisões em função do número t.
© Implemente o algoritmo em uma linguagem de programação e aproxime o valor de ecom diversos valores de t.
(d) Quantos termos da série são necessários para aproximar e com 10 dígitos de precisão?

Passo 1

Beleza, a questão fala sobre a série
e ;=;sumn=0^infty1n!
e pede quatro coisas:
a) Escrever um algoritmo que some os primeiros termos dessa série
b) Contar quantas adições, multiplicações e divisões o algoritmo faz (complexidade em função de )
c) Implementar e mostrar como fica a aproximação de para vários
d) Encontrar quantos termos são necessários para ter 10 dígitos certos
Conteúdo: somatório, fatorial, estimativa de erro de série, complexidade elementar de algoritmos. Vamos usar definição de fatorial ( ), soma parcial e estimativa de resto de série.

Passo 2

Parte (a) – algoritmo para somar os primeiros termos
  1. Inicializa
    (corresponde ao termo , que é )
    (o valor de no passo anterior)
  2. Para de 1 até :
    a) Atualiza o fatorial:

    (porque )
    b) Calcula o termo
    c) Soma na variável acumuladora:
  3. No final, é a aproximação de com termos.
Em pseudocódigo:
function aproximar_e(t):
    sum ← 1
    fact ← 1
    for n from 1 to t-1 do:
        fact ← fact * n
        term ← 1 / fact
        sum ← sum + term
    return sum

Passo 3

Parte (b) – complexidade contando operações
No laço de 1 até :
  • 1 multiplicação para atualizar fact
  • 1 divisão para gerar term
  • 1 adição para atualizar sum
Como esse corpo roda vezes, temos:
  • Multiplicações:
  • Divisões: (ou se contarmos alguma divisão extra, mas basicamente )
  • Adições:
Então a complexidade é e o número exato de cada operação é proporcional a .

Passo 4

Parte © – implementando e testando aproximações
Por exemplo, em Python (só ilustrando):
def aproximar_e(t):
    soma = 1.0
    fat  = 1.0
    for n in range(1, t):
        fat *= n
        soma += 1/fat
    return soma

for t in [1, 2, 5, 10, 15]:
    print(t, aproximar_e(t))
Resultados típicos (arredondados):
  • : 1.0
  • : 2.0
  • : 2.708333333333333
  • : 2.7182818011463845
  • : 2.71828182845823
Você vê que já com uns 10–15 termos a gente chega bem perto de .

Passo 5

Parte (d) – quantos termos para 10 dígitos de precisão?
Teoria do resto de série de Taylor diz que o erro depois de somar até gl|,e - sumk=0^n1k!gr|;<;1(n+1)! é menor que o próximo termo:
Queremos .
Basta testar fatoriais pequenos:
  • ainda é maior que
Logo, precisamos de , ou seja, somar termos de até (total de 14 termos).

Resposta

(a) Pseudocódigo acima com laço de 1 a .
(b) multiplicações, divisões, adições. Complexidade .
© Exemplos: para , para , para .
(d) São necessários 14 termos ( até 13) para garantir pelo menos 10 dígitos de precisão.

Exercícios relacionados