Project Euler31: فهم حل البرنامج

Question

أحاول فهم حل ل مشروع أولر #31 لقد وجدت في المنتديات.

المشكلة هي أننا نعطي عملات معدنية مع القيم التالية:

coins=[1,2,5,10,20,50,100,200]

نحن مكلفون بتوليد جميع الطرق الممكنة للوصول إلى 200. على سبيل المثال ، سيكون 10*10+100 = 200 طريقة ممكنة.

1. السؤال 2: كيف يعمل الرمز أدناه! تبدو أنيقة للغاية وبسيطة ومباشرة مقارنةً بنهجي ، ويعمل بشكل أسرع.

بينما كنت أتصفح المنتديات ، وجدت هذا الحل:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

السطر الأول هو مجرد قائمة قيم العملة. السطر الثاني هو إنشاء صفيف مع 1 تليها 200 0. لكن الأسطر الأربعة التالية جعلتني مرتبكًا. أعتقد أنه يزيد من عدد الطرق الممكنة في الصفيف ، لذلك سيعطي Case_Num [200] الإدخال الأخير في القائمة ، لكن ليس لدي أي فكرة عن كيفية عمله.

Answer 1

هذا حل جميل جدا كما قلت. يبني الكود على نفسه من خلال كل تكرار من 1-200 مع كل مبلة عملة.

يتكون مجموعة case_num في البداية من [1 ، 0 ، 0 ، 0 ، 0 ، 0 ... 0 ، 0 ، 0

ما يعنيه هذه الأرقام (بصرف النظر عن الأولي 1) هو عدد الطرق التي يمكنك من خلالها بناء المجموع المعطى (يمثله فهرس الرقم) باستخدام العملات المعدنية في P_List التي تكررت بها حتى الآن.

العملة الأولى في P_List هي 1. لذلك إذا كان يمكن أن يتناسب 1 داخل الفهرس ، فإنك تأخذ القيمة في الفهرس السابق وإضافتها إلى الفهرس الحالي. يعمل هذا لأنه إذا كانت هناك 5 طرق معروفة للوصول إلى 25 ووجدت عملة معدنية من الحجم 1 ، فستكون هناك أيضًا 5 طرق للوصول إلى 26 .

لذلك بعد التكرار مع 1 سوف ينتهي بك الأمر [1 ، 1 ، 1 ، 1 ، 1 ... 1 ، 1

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

على سبيل المثال ، لا يتناسب 2 داخل الفهرس 1 ولكنه يناسب الفهرس 2. لذا قمت للتو بإنشاء طريقة جديدة للوصول إلى 2 من 0 حتى تأخذ كل الطرق التي يمكنك من خلالها الوصول إلى 0 وإضافتها إلى الفهرس الحالي. في الفهرس 27 ، يناسب 2 داخل الفهرس حتى تأخذ عدد الطرق التي يمكنك من خلالها الوصول إلى 25 وإضافتها إلى 27 لأنه لديك الآن (كل هذه الطرق للوصول إلى 25 + واحد 2 عملة) + (كل الطرق كان عليك الوصول إلى 27 قبل أن تعرف أن لديك عملات معدنية بحجم 2).

لذلك بعد التكرار مع 2 سوف ينتهي بك الأمر مع [1 ، 1 ، 2 ، 2 ، 3 ، 3 ، 4 ، 4 ...

إذا كنت لا تزال تواجه مشكلة ، فقد يكون الأمر يستحق ذلك لمحاولة السير عبر البرنامج بأكمله (ربما في إجمالي أقل من 50 بدلاً من 200).