Python programa recursivo para preparar fatorar um número
-
06-07-2019 - |
Pergunta
Eu escrevi o seguinte programa que fatorar um número primo:
import math
def prime_factorize(x,li=[]):
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else: #This else belongs to for
li.append(x)
print li #First print statement; This is what is returned
return li
prime_factorize(x/i,li)
if __name__=='__main__':
print prime_factorize(300) #Second print statement, WTF. why is this None
A seguir é a saída que eu recebo:
[2, 2, 3, 5, 5]
None
embora', o valor retornado é impresso corretamente, o valor retornado após parece estar imprimindo nenhum, o tempo todo. O que eu estou ausente?
Além disso, como posso melhorar o programa (continuando a usar a recursão)
Solução
A sua função prime_factorize não tem uma instrução de retorno no caso recursivo - você deseja chamar "prime_factorize retorno (x / i, li)" na sua última linha. Experimente-o com um número primo (para que a chamada recursiva não é necessário) para ver que ele funciona nesse caso.
Além disso, você provavelmente vai querer fazer a assinatura algo como:
def prime_factorize(x,li=None):
if li is None: li = []
caso contrário você obter resultados errados quando chamá-lo duas ou mais vezes:
>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]
Outras dicas
Se você quiser fazê-lo completamente recursivo, eu recomendo este código, que faz retornar a resposta correta ea forma como ele funciona é bastante claro. Se você quiser tornar o programa mais eficiente possível eu recomendo que você se ater a um de seus métodos anteriores.
def primeFact (i, f):
if i < f:
return []
if i % f == 0:
return [f] + primeFact (i / f, 2)
return primeFact (i, f + 1)
Esta é uma maneira completamente recursivo de resolver o seu problema
>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]
@ Anthony respondeu corretamente a sua pergunta original sobre print
. No entanto, no espírito das várias dicas que também foram oferecidos, aqui está uma simples refactorization usando retirada da cauda recursão:
def prime_factorize(x):
li = []
while x >= 2:
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else:
li.append(x)
return li
x //= i
Esta não aborda os problemas de desempenho cruciais (comportamento big-O é o mesmo que para a sua solução original) - mas desde que o próprio Python não faz a otimização de recursão, é importante aprender a fazê-lo manualmente.
"Alterar o [não-caso-base] etapas recursivas 'return thisfun(newargs)'
em args=newargs; continue
e colocar todo o corpo em um loop while True:
" é a idéia básica de otimização de cauda-recursão. Aqui eu também fiz li um não-arg (nenhuma razão para que ele seja um arg), colocou uma condição na while
, e evitou a continue
desde o passo recursivo foi no final do corpo de qualquer maneira.
Esta formulação seria uma boa base a partir da qual se aplicam mais refatorações de otimização (sqrt evitar, memoization, ...) para chegar em direção a um melhor desempenho.
A versão mais em estilo funcional.
def prime_factorize( number ):
def recurse( factors, x, n ):
if x<2: return factors # 0,1 dont have prime factors
if n > 1+x**0.5: # reached the upper limit
factors.append( x ) # the only prime left is x itself
return factors
if x%n==0: # x is a factor
factors.append( n )
return recurse( factors, x/n, n )
else:
return recurse( factors, x, n+1 )
return recurse( [], number, 2)
for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
#print num, ":", factors
def primeFactorization(n):
""" Return the prime factors of the given number. """
factors = []
lastresult = n
while 1:
if lastresult == 1:
break
c = 2
while 1:
if lastresult % c == 0:
break
c += 1
factors.append(c)
lastresult /= c
return factors
é bom.