مسألة صرف العملات

يأخذ أمين الصندوق عند إعطاء الباقي أكبر عملة تتسع، ثم التي تليها، ومع اليورو أو الدولار يعطي ذلك دائمًا أقل عدد من العملات. لكن غيّر العملات إلى 1 و3 و4، وستدفع العادة نفسها 6 بثلاث عملات بينما تكفي اثنتان. أما البرمجة الديناميكية فتجد الحد الأدنى الحقيقي لأي عملات.

صف من المبالغ، مع كل منها أقل عدد من العملات يكوّنه، فوق عملات بثلاثة أحجام مختلفة
صف من المبالغ، مع كل منها أقل عدد من العملات يكوّنه، فوق عملات بثلاثة أحجام مختلفة

سؤالان

تأتي مسألة صرف العملات بصيغتين. الأولى تسأل عن أقل عدد من العملات يكوّن مبلغًا محددًا؛ وتسمى أيضًا مسألة إعطاء الباقي. والثانية تسأل كم توفيقة مختلفة من العملات تكوّنه. وفي الصيغتين يمكن استخدام كل نوع من العملات بقدر ما تشاء، وتُحل كلتاهما ببناء الإجابة لكل مبلغ من إجابات المبالغ الأصغر.

أقل عدد من العملات خطوة بخطوة

أنشئ صفًا من الخلايا للمبالغ من 0 حتى المبلغ المطلوب. المبلغ 0 يحتاج إلى 0 عملة؛ وكل مبلغ آخر يبدأ باللانهاية. مرّ بالمبالغ بالترتيب، وجرّب لكل منها كل عملة c تتسع: خلية المبلغ ناقص c، مضافًا إليها عملة واحدة، هي مرشح. احتفظ بالأصغر. تعتمد كل خلية فقط على الخلايا التي على يسارها، وهي نهائية بالفعل، لذلك يملأ مرور واحد الصف كله.

مثال

مع العملات 1 و3 و4: المبلغ 1 يحتاج إلى عملة واحدة، و2 إلى عملتين، و3 إلى عملة واحدة (عملة 3 واحدة)، و4 إلى عملة واحدة. للمبلغ 5، جرّب 1 (4 يحتاج إلى 1، إذن 2 من العملات)، و3 (2 يحتاج إلى 2، إذن 3 من العملات)، و4 (1 يحتاج إلى 1، إذن 2 من العملات): الأفضل 2. وللمبلغ 6، جرّب 1 (5 يحتاج إلى 2، إذن 3)، و3 (3 يحتاج إلى 1، إذن 2)، و4 (2 يحتاج إلى 2، إذن 3): الأفضل 2، بـ 3 + 3. أما الطريقة الجشعة فكانت ستدفع 4 + 1 + 1.

عدّ الطرق

لعدّ التوافيق، أضف العملات واحدة تلو الأخرى. مع العملة الأولى وحدها، يمكن تكوين كل مبلغ بطريقة واحدة أو لا يمكن تكوينه أصلًا. عندما تنضم عملة جديدة c، تكون طرق تكوين المبلغ a هي الطرق القديمة، من دون c، مضافًا إليها طرق تكوين a − c مع السماح باستخدام c مرة أخرى، لأن كل واحدة منها تصبح طريقة لتكوين a بإضافة c أخرى. مع العملات 1 و2 و5 هناك 4 طرق لتكوين 5: 5، و2 + 2 + 1، و2 + 1 + 1 + 1، و1 + 1 + 1 + 1 + 1.

متى تكفي الطريقة الجشعة

يسمى نظام العملات الذي تعطي فيه الطريقة الجشعة دائمًا أقل عدد من العملات نظامًا قانونيًا. ومعظم العملات الحديثة مصممة بهذه الطريقة، وفي عام 1994 وصف ديفيد بيرسون اختبارًا يفحص نظام العملات بعدد من الخطوات لا ينمو إلا نموًا متعدد الحدود مع عدد العملات. ولم تكن العملات البريطانية القديمة قانونية: فالطريقة الجشعة تدفع 48 بنسًا بنصف كراون وشلن وقطعة ستة بنسات، بينما تكفي قطعتا فلورين.

استكشفها بنفسك

افتح التطبيق، وانتقل إلى عرض «الجدول»، واضغط «خطوة». في وضع «أقل عدد من العملات»، الخلية البرتقالية هي المبلغ الجاري حسابه، والخلية الزرقاء هي المبلغ الأصغر الذي تتركه العملة؛ والصف الذي تحتها يحفظ آخر عملة، وفي النهاية تُقرأ العملات بالرجوع على طوله. انتقل إلى «عدد الطرق» وشاهد الأعداد تكبر صفًا بعد صف مع انضمام كل عملة.

الأسئلة المتداولة

هل مسألة صرف العملات مسألة حقيبة ظهر؟

إنها قريبة منها جدًا. فصيغة أقل عدد من العملات هي مسألة حقيبة ظهر غير محدودة، فيها كل عملة عنصر وزنه قيمته الاسمية، ويجب ملء الحقيبة تمامًا، والهدف أقل عدد من العناصر.

ما التعقيد الزمني؟

O(k·A) لعدد k من أنواع العملات ومبلغ A، في الصيغتين. يحتوي جدول أقل عدد من العملات على A + 1 خلية، وجدول الطرق على (k + 1)·(A + 1) خلية، مع أن صفًا واحدًا يكفي إذا حُدّثت الخلايا في مكانها.

لماذا تُعد العملات بترتيب ثابت؟

لو جرّب كل مبلغ كل عملة، لعُدّت 1 + 2 و2 + 1 طريقتين. إضافة العملات صفًا بعد صف تعني أن التوفيقة تُبنى دائمًا من العملات الأسبق أولًا، فتُعد كل واحدة مرة واحدة بالضبط.

هل يمكن استرجاع العملات في حالة عدد الطرق؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب صرف العملات