5

Boas pessoal, queria ajuda num exercício:

Pede para criar uma função que calcule o fatorial dos numeros de 1 a n. Ja tenho a parte recursiva, mas nao sei como fazer para que me dê de 1 a n.

def fatorial(n):
    if n == 0 or n == 1:
        return 1 
    else:
        return n * fatorial(n - 1) 

Isto dá-me o fatorial de n. Eu queria de 1 a n.

E também queria saber como faço de forma iterativa.

3
  • 1
    Cara, se isso for um exercício da faculdade, de lógica de programação, se esforce pra.
    – Puam Dias
    Commented 7/01/2016 às 21:54
  • Mas eu nao estou a conseguir fazer... dai eu estar a pedir ajuda.
    – CSAnimor
    Commented 7/01/2016 às 22:31
  • Esse tipo de pergunta desvaloriza o site Commented 8/01/2016 às 21:39

3 Respostas 3

11

Criar uma função que calcula o fatorial dum numero é um dos problemas relacionados com a recursão mais fáceis se sabes a definição matemática de fatorial dum numero, que é a seguinte:

f(0) = 1
f(1) = 1
f(n) = f(n - 1) * n, n > 1

Traduzir isto em Python é muito fácil, visto que Python é quase pseudo-código.

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return f(n - 1) * n

Esta função claramente calcula o fatorial de n, mas o que tu realmente queres é calcular o fatorial de 1 até n, dado um certo n. O que podes fazer é ter outra função recursiva que chama f partindo de 1 até n (ou de n até 1). Esta função tem que salvar os resultados em algum lugar, tipo numa lista. Aqui vai uma opção de implementação de tal função:

def _mf_r(n, i, a):
    if i <= n:        
        a.append(f(i))
        _mf_r(n, i + 1, a)
    return a

def mf_r(n):
    return _mf_r(n, 1, [])

E esta é a minha versão iterativa:

def mf_i(n):
    a = []
    for i in range(1, n + 1):
        a.append(f(i))
    return a

Fazendo alguns testes

for i in range(10):
    print(mf_r(i))
    print(mf_i(i))

Com resultados:

[]
[]
[1]
[1]
[1, 2]
[1, 2]
[1, 2, 6]
[1, 2, 6]
[1, 2, 6, 24]
[1, 2, 6, 24]
[1, 2, 6, 24, 120]
[1, 2, 6, 24, 120]
[1, 2, 6, 24, 120, 720]
[1, 2, 6, 24, 120, 720]
[1, 2, 6, 24, 120, 720, 5040]
[1, 2, 6, 24, 120, 720, 5040]
[1, 2, 6, 24, 120, 720, 5040, 40320]
[1, 2, 6, 24, 120, 720, 5040, 40320]
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

No primeiro output temos uma lista vazia porque tu querias o fatorial de 1 até n, mas os testes partem de 0.

2
  • 1
    Ao autor da pergunta: na prática, use a versão iterativa. As versões recursivas são boas como estudo, mas são menos eficientes.
    – bfavaretto
    Commented 8/01/2016 às 2:59
  • 1
    Obrigada! :) fiquei bastante esclarecida!
    – CSAnimor
    Commented 8/01/2016 às 7:16
8

Na verdade, a opção mais eficiente, neste caso, é utilizar o conceito de memoization na função, visto que o fatorial de um número qualquer n pode ser obtido por fatorial(n-1) * n e, como serão, necessariamente, calculados todos os valores dos fatoriais de 1 a n, é certo que já teremos calculado o valor de fatorial(n-1).

A implementação seria:

def fatorial_range(n):
    """ Retorna o fatorial de todos os números entre 1 e n """
    next_value = 1
    for i in range(1, n+1):
        yield next_value
        next_value *= i + 1

Veja funcionando no Repl.it | Ideone | GitHub GIST

Desta forma, a solução fica O(n), pois serão efetuadas apenas n multiplicações.

Para obter, por exemplo, os fatoriais até 5, bastaria fazer:

for fat in fatorial_range(5):
    print(fat)

Retornando:

1
2
6
24
120
7
  • 1
    Nossa, resolveu o "problema" da recursividade de modo ninja xD +1 ... acho que o boost ai deve ter sido de uns 300%
    – Syzoth
    Commented 9/05/2018 às 18:54
  • Anderson, me corrija se eu estiver enganado, mas você não usou memoization na sua resposta, mas sim implementou de maneira matematicamente inteligente o algoritmo. Memoization é um tipo de cache e você não guarda e nem recupera os resultados já obtidos. Commented 19/09/2018 às 12:12
  • Sei que a pergunta é antiga, meu medo é que alguém confunda o termo memoization quando cair aqui, pois sua resposta é boa. Commented 19/09/2018 às 12:13
  • @fernandosavio por isso comentei que apliquei o "conceito de memoization". Eu defini um gerador que calcula os valores e como o gerador mantém o contexto entre as chamadas, o valor do fatorial anterior está na memória, bastando apenas "incrementá-lo". Por ser um acesso à memória e não um recálculo do valor é que falei que foi aplicado o conceito.
    – Woss
    Commented 19/09/2018 às 12:14
  • 1
    @fernandosavio exato. O conceito do memoization é acessar em cache um valor já calculado anteriormente para não ter que recalculá-lo. Foi o que eu fiz dentro do gerador, mantendo sempre o último fatorial calculado em memória, pois no momento que for calcular o fatorial de 5, por exemplo, o fatorial de 4 está em memória, podendo fazer apenas "5 * fat(4)".
    – Woss
    Commented 19/09/2018 às 12:29
2

Cliquei no site para avaliar uma solução qualquer, após pensar por um instante, formulei funções que acho mais eficientes. (Em python 2.x e 3.x)

para fatorial de x:

def fatorial(x):
    result=1
    for i in range(x):
        result=result*(x-i)
    return result

Mais compacta e atende corretamente aos casos x=0, x=1, sem necessidade de teste if.

Para satisfazer seu pedido, pensei num laço simples, para formar a lista dos fatoriais de i, variando de um natural a, à outro b, incluindo o caso particular que vc queria(de 1 até n) (a=1, b=n):

def lista_fat(a,b):
    lista=[]
    for i in range(a,b+1):
       lista.append(fatorial(i))
    print'lista dos fatoriais de', a, 'ao',b
    print lista

Abaixo o código inteiro, com o caso particular de 1 a 10.

def fatorial(x):
    result=1
    for i in range(x):
        result=result*(x-i)
    return result

def lista_fat(a,b):
    lista=[]
    for i in range(a,b+1):
        lista.append(fatorial(i))
    print'lista dos fatoriais de', a, 'ao',b
    print lista

lista_fat(1,10)

EDIÇÃO, sintaxe para Python 3:

def fatorial(x):
    result=1
    for i in range(x):
       result=result*(x-i)
    return result

def lista_fat(a,b):
    lista=[]
    for i in range(a, b+1):
       lista.append(fatorial(i))
    print('lista dos fatoriais de {} ao {}'.format(a, b))
    print(lista)

lista_fat(1,10)

Resultado:

 lista dos fatoriais de 1 ao 10
 [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .