برنامج بيثون عودي إلى حلل إلى عوامل رئيس وعدد
-
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
وثابتة "، تتم طباعة القيمة التي تم إرجاعها بشكل صحيح، ويبدو أن قيمة بعد عاد إلى أن الطباعة لا شيء، في كل وقت. ما أنا في عداد المفقودين؟
وأيضا، كيف يمكنني تحسين برنامج (الاستمرار في استخدام العودية)
المحلول
وليس لديه وظيفة prime_factorize لديك عبارة إرجاع في حالة متكررة - تريد استدعاء "prime_factorize عودة (خ / ط، لي)" على خط الأخير. تحاول ذلك مع عدد الوزراء (بحيث ليست هناك حاجة للدعوة عودي) لمعرفة أنه يعمل في هذه الحالة.
وأيضا وربما كنت تريد أن تجعل التوقيع شيئا مثل:
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
بشكل صحيح. ومع ذلك، في روح من العديد من النصائح التي عرضت أيضا، وهنا refactorization بسيطة باستخدام إزالة الذيل العودية:
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
وهذا لا يعالج مشاكل الأداء الحاسمة (كبير-O السلوك هو نفس الحل الأصلي) - ولكن منذ بيثون نفسها لا تفعل الأمثل الذيل العودية، من المهم أن نتعلم كيفية القيام بذلك يدويا.
و"تغيير [غير قاعدة حدة] خطوات متكررة 'return thisfun(newargs)'
إلى args=newargs; continue
ووضع الجسم كله في حلقة while True:
" هي الفكرة الأساسية لتحسين الذيل العودية. هنا لقد قدمت أيضا لى غير وسيطة (أي سبب لذلك أن تكون وسيطة)، وضعت شرطا على while
، وتجنب continue
منذ كانت الخطوة متكررة في نهاية الجسم على أي حال.
وهذه الصيغة ستكون أساسا جيدا يمكن من خلالها تطبيق refactorings مزيد من تحسين (تجنب الجذر التربيعي، التحفيظ، ...) للوصول إلى نحو أداء أفضل.
وهناك أكثر الإصدار أسلوب عملي.
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
وهو عليه غرامة.