نقدي

نقدي

مشكلة بحاجة إلى حل

لنفترض أنك تعمل في متجر ويمنحك أحد العملاء 1.00 دولار (100 سنت) مقابل حلوى تكلف 0.50 دولار (50 سنتًا). ستحتاج إلى أن تدفع لهم "التغيير"، وهو المبلغ المتبقي بعد دفع تكلفة الحلوى. عند إجراء التغيير، من المحتمل أنك تريد تقليل عدد العملات المعدنية التي توزعها لكل عميل، حتى لا تنفد (أو تزعج العميل!). في ملف اسمه cash.c في مجلد يسمى cash، قم بتنفيذ برنامج في لغة C يطبع الحد الأدنى من العملات المعدنية اللازمة لإجراء مقدار معين من التغيير، بالسنت، كما هو موضح أدناه:

Change owed: 25
1

لكن اطلب من المستخدم إجراء int أكبر من 0، بحيث يعمل البرنامج مع أي قدر من التغيير:

Change owed: 70
4

أعد مطالبة المستخدم، مرارًا وتكرارًا حسب الحاجة، إذا لم يكن إدخاله أكبر من أو يساوي 0 (أو إذا لم يكن إدخاله int على الإطلاق!).

تجريبي

الخوارزميات الجشعة

لحسن الحظ، أعطت علوم الحاسوب الصرافين في كل مكان طرقًا لتقليل أعداد العملات المستحقة: الخوارزميات الجشعة.

وفقًا للمعهد الوطني للمعايير والتكنولوجيا (NIST)، الخوارزمية الجشعة هي تلك "التي تأخذ دائمًا أفضل الحلول الفورية أو المحلية أثناء العثور على إجابة. تجد الخوارزميات الجشعة الحل الأمثل الشامل أو العالمي لبعض مشكلات التحسين، ولكنها قد تجد حلولًا أقل من الأمثل لبعض حالات المشكلات الأخرى."

ماذا يعني كل هذا؟ حسنًا، لنفترض أن أمين الصندوق مدين للعميل ببعض التغيير وفي درج أمين الصندوق هذا أرباع (25 سنتًا)، ودايمات (10 سنتات)، ونيكل (5 سنتات)، وبنسات (1 سنتات). المشكلة التي يتعين حلها هي تحديد العملات المعدنية وعدد العملات التي سيتم تسليمها إلى العميل. فكر في أمين الصندوق "الجشع" باعتباره الشخص الذي يريد أن يأخذ أكبر قدر ممكن من هذه المشكلة مع كل عملة يخرجها من الدرج. على سبيل المثال، إذا كان بعض العملاء مستحقًا بمبلغ 41 سنتًا، فإن أكبر قضمة أولى (i.e.، أفضل فورية أو محلية) يمكن الحصول عليها هي 25 سنتًا. (هذه القطعة هي "الأفضل" لأنها تقربنا من 0 سنت بشكل أسرع من أي عملة أخرى.) لاحظ أن قطعة بهذا الحجم من شأنها أن تقلل ما كان يمثل مشكلة 41 سنتًا إلى مشكلة 16 سنتًا، نظرًا لأن 41 - 25 = 16. أي أن الباقي عبارة عن مشكلة مماثلة ولكنها أصغر. وغني عن القول أن قضمة أخرى بقيمة 25 سنتًا ستكون كبيرة جدًا (على افتراض أن أمين الصندوق يفضل عدم خسارة المال)، وبالتالي فإن أمين الصندوق الجشع لدينا سينتقل إلى قضمة بحجم 10 سنتات، مما يتركه يواجه مشكلة 6 سنتات. عند هذه النقطة، يستدعي الجشع قضمة واحدة بقيمة 5 سنتات تليها قضمة واحدة، وعندها يتم حل المشكلة. يحصل العميل على ربع، ودايم واحد، ونيكل واحد، وقرش واحد: إجمالي أربع عملات معدنية.

اتضح أن هذا النهج الجشع (خوارزمية i.e.) ليس مثاليًا محليًا فحسب، بل أيضًا عالميًا بالنسبة للعملة الأمريكية (وأيضًا عملة الاتحاد الأوروبي). أي أنه طالما أن أمين الصندوق لديه ما يكفي من كل عملة، فإن هذا النهج من الأكبر إلى الأصغر سينتج أقل عدد ممكن من العملات المعدنية. كم عدد قليل؟ حسنا، أنت تخبرنا!

نصيحة

#include <cs50.h>
#include <stdio.h>

int main(void)
{

}

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents

    // Calculate how many quarters you should give customer
    // Subtract the value of those quarters from cents

    // Calculate how many dimes you should give customer
    // Subtract the value of those dimes from remaining cents

    // Calculate how many nickels you should give customer
    // Subtract the value of those nickels from remaining cents

    // Calculate how many pennies you should give customer
    // Subtract the value of those pennies from remaining cents

    // Sum the number of quarters, dimes, nickels, and pennies used
    // Print that sum
}

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);
}

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
}

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

#include <cs50.h>
#include <stdio.h>

int calculate_quarters(int cents);

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);

    // Calculate how many quarters you should give customer
    int quarters = calculate_quarters(cents);

    // Subtract the value of those quarters from cents
    cents = cents - (quarters * 25);
}

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

كيفية الاختبار

بالنسبة لهذا البرنامج، حاول اختبار الشيفرة يدويًا. إنها ممارسة جيدة:

• إذا قمت بإدخال -1، هل يطالبك برنامجك مرة أخرى؟
• إذا قمت بإدخال 0، يقوم بإخراج برنامجك 0?
• إذا قمت بإدخال 1، يقوم بإخراج برنامجك 1 (i.e.، بنس واحد)؟
• إذا قمت بإدخال 4، يقوم بإخراج برنامجك 4 (i.e.، أربعة بنسات)؟
• إذا قمت بإدخال 5، يقوم بإخراج برنامجك 1 (i.e.، نيكل واحد)؟
• إذا قمت بإدخال 24، يقوم بإخراج برنامجك 6 (i.e.، اثنان دايم وأربعة بنسات)؟
• إذا قمت بإدخال 25، يقوم بإخراج برنامجك 1 (i.e.، ربع)؟
• إذا قمت بإدخال 26، يقوم بإخراج برنامجك 2 (i.e.، ربع وبنس واحد)؟
• إذا قمت بإدخال 99، يقوم بإخراج برنامجك 9 (i.e.، ثلاثة أرباع، اثنان دايم، وأربعة بنسات)؟

صحة

check50 cs50/problems/2026/x/cash

النمط

style50 cash.c

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

submit50 cs50/problems/2026/x/cash