برنامج بيثون عودي إلى حلل إلى عوامل رئيس وعدد

Question

وكتبت البرنامج التالي لحلل إلى عوامل رئيس وعدد:

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

وثابتة "، تتم طباعة القيمة التي تم إرجاعها بشكل صحيح، ويبدو أن قيمة بعد عاد إلى أن الطباعة لا شيء، في كل وقت. ما أنا في عداد المفقودين؟

وأيضا، كيف يمكنني تحسين برنامج (الاستمرار في استخدام العودية)

Answer 1

وليس لديه وظيفة 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]

Answer 2

إذا كنت تريد أن تفعل ذلك العودية تماما، أود أن أوصى هذا الرمز، فإنه لا يعود الإجابة الصحيحة والطريقة التي يعمل بها واضح جدا. إذا كنت تريد أن تجعل البرنامج فعالة قدر ممكن انصح لك عصا واحدة من الطرق السابقة.

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]

Answer 3

و @أنتوني أجاب سؤالك الأصلي حول 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 مزيد من تحسين (تجنب الجذر التربيعي، التحفيظ، ...) للوصول إلى نحو أداء أفضل.

Answer 4

وهناك أكثر الإصدار أسلوب عملي.

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

Answer 5

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

وهو عليه غرامة.