Рекурсивная программа Python для простого разложения числа
-
06-07-2019 - |
Вопрос
Я написал следующую программу для простого разложения на числа:
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
Ниже приведен вывод, который я получаю:
[2, 2, 3, 5, 5]
None
Altho ', возвращаемое значение печатается правильно, после возвращенного значения, кажется, не печатает ничего, все время. Чего мне не хватает?
Кроме того, как я могу улучшить программу (продолжая использовать рекурсию)
Решение
Ваша функция prime_factorize не имеет оператора return в рекурсивном случае - вы хотите вызвать " return prime_factorize (x / i, li) " на его последней строке. Попробуйте использовать простое число (чтобы рекурсивный вызов не требовался), чтобы убедиться, что в этом случае он работает.
Также вы, вероятно, хотите сделать подпись примерно такой:
def prime_factorize(x,li=None):
if li is None: li = []
в противном случае вы получите неправильные результаты при вызове его два или более раз:
>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]
Другие советы
Если вы хотите сделать это полностью рекурсивным, я бы порекомендовал этот код, он возвращает правильный ответ, и способ его работы довольно ясен. Если вы хотите сделать программу максимально эффективной, я бы порекомендовал вам придерживаться одного из ваших предыдущих методов.
def primeFact (i, f):
if i < f:
return []
if i % f == 0:
return [f] + primeFact (i / f, 2)
return primeFact (i, f + 1)
Это полностью рекурсивный способ решения вашей проблемы
>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]
@ Энтони правильно ответил на ваш первоначальный вопрос о print
. Однако, в духе нескольких советов, которые также были предложены, вот простая рефакторизация с использованием удаления хвостовой рекурсии:
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
Это не решает критически важные проблемы производительности (поведение big-O такое же, как и в исходном решении), но поскольку сам Python не выполняет оптимизацию хвостовой рекурсии, важно научиться делать это вручную. р>
" Измените рекурсивные шаги [не базовый случай] 'return thisfun (newargs)'
в args = newargs; продолжить
и поместить все тело в цикл , тогда как True:
" основная идея оптимизации хвостовой рекурсии Здесь я также сделал li не-arg (без причины быть аргументом), наложил условие на while
и избежал continue
, так как рекурсивно шаг был в конце тела в любом случае.
Эта формулировка послужит хорошей основой для дальнейшей оптимизации оптимизации рефакторинга (избегание, напоминание и т. д.) для повышения производительности.
Более функциональная версия.
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
это нормально.