- قيد الملء
- يُقرأ منها
- الإجابة
مسألة صرف العملات
إذا كانت لديك بضعة أنواع من العملات، فكيف تدفع مبلغًا محددًا بأقل عدد ممكن منها، وبكم طريقة يمكن فعل ذلك أصلًا؟ الإجابة الجشعة، أي البدء بأكبر عملة، تنجح مع النقود الحقيقية لكنها تفشل مع بعض مجموعات العملات. أما الجدول الذي يبني كل مبلغ من المبالغ الأصغر فيصل دائمًا إلى الإجابة الصحيحة. انقر عملة في الطبق لتضيفها إلى المنضدة، وانقر عملة على المنضدة لتستعيدها. يمتلئ المقياس نحو المبلغ: كوّنه بالضبط بأقل عدد ممكن من العملات. يعرض «أقل عدد من العملات» أفضل إجابة، ويعرض «الجشع» ما تحصل عليه إذا أخذت دائمًا أكبر عملة تتسع، وهو ليس دائمًا الأقل. غيّر العملات (بالسنت) والمبلغ في اللوحة. يعرض عرض «الجدول» كيف تجد البرمجة الديناميكية أقل عدد من العملات، أو كيف تعدّ طرق تكوين المبلغ: اضغط «تشغيل» لتشاهد الجدول يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة، واسحب شريط الخطوات للانتقال إلى أي موضع. يمكن استخدام كل عملة بقدر ما تشاء. عند تحديد الجدول، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- انقر على العملات في الصينية لتكوين المبلغ بالضبط، وشاهد المؤشر يمتلئ بالسنتات.
- حاول استخدام أقل عدد ممكن من العملات، ثم اضغط «أقل عدد من العملات» أو «الجشع» للمقارنة.
- افتح عرض «الجدول» واضغط «تشغيل» لتشاهد كل خلية وهي تقرأ المبلغ الأصغر الذي تعتمد عليه.
أقل عدد من العملات
المبلغ 0 لا يحتاج إلى أي عملة. ولكل مبلغ أكبر، جرّب كل عملة لا تزيد عليه: ما يتبقى بعد تلك العملة مبلغ أصغر موجود بالفعل في الجدول، فإضافة عملة واحدة تعطي مرشحًا. يوضع أصغر مرشح في الخلية، وتُحفظ العملة التي أعطته في الصف الذي تحتها. عندما يمتلئ الجدول، تُقرأ العملات بالرجوع من المبلغ المطلوب: خذ آخر عملة له، وانتقل إلى المبلغ المتبقي، وكرر حتى تصل إلى 0.
عدد الطرق
لعدّ التوافيق بدلًا من الترتيبات، يضيف الجدول عملة واحدة في كل صف. تعدّ الخلية طرق تكوين مبلغها بالعملات حتى صفها: الطرق التي لا تستخدم أحدث عملة، وهي الخلية التي فوقها، مضافًا إليها الطرق التي تستخدم أحدث عملة مرة واحدة على الأقل، وهي الخلية التي تبعد إلى اليسار في الصف نفسه عددًا من الأعمدة يساوي قيمة العملة. ولأن العملات تُضاف بترتيب ثابت، فإن 1 + 2 و2 + 1 طريقة واحدة وتُعد مرة واحدة.
الأسئلة المتداولة
لماذا تفشل الطريقة الجشعة؟
تأخذ الطريقة الجشعة دائمًا أكبر عملة تتسع ولا تعيد النظر أبدًا. مع العملات 1 و3 و4 ومبلغ 6، تأخذ 4 ثم 1 و1: ثلاث عملات، بينما تكفي عملتان من فئة 3. وفي أنظمة العملات مثل اليورو أو الدولار الأمريكي تصادف أن تكون الطريقة الجشعة مثلى؛ وتسمى هذه الأنظمة أنظمة قانونية (canonical).
ما الفرق بين عدّ الطرق وعدّ الترتيبات؟
الطرق تعامل 1 + 2 و2 + 1 على أنهما التوفيقة نفسها؛ أما الترتيبات فتعدّهما منفصلتين. يعدّ التطبيق الطرق بإضافة العملات صفًا بعد صف. أما عدّ الترتيبات فيمر بالمبالغ بالترتيب ويجرّب كل عملة لكل مبلغ.
ما مدى سرعة خوارزمية صرف العملات؟
يحتاج كلا الجدولين إلى عدد من الخطوات يساوي عدد أنواع العملات مضروبًا في المبلغ. وهذا سريع للمبالغ التي تبلغ الآلاف، لكن المبلغ قد يكون عددًا هائلًا، لذلك إذا قيست المسألة بعدد الأرقام فهي NP-صعبة بوجه عام.
ماذا لو تعذّر تكوين مبلغ ما؟
تبقى خليته عند ∞، مثل المبلغين 1 و3 مع العملتين 2 و5. وفي وضع «عدد الطرق» يكون العدد ببساطة 0.
هل يُرسل أي شيء إلى أي مكان؟
لا. كل شيء يُحسب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر