• 任务描述
• 编程要求
• 测试说明

任务描述

本关任务：设计一个贪婪算法，使得找的钱币张数最少。

商店售货员找给 1 个顾客 n 元，用以下七种面值的纸币：100 元，50 元，20 元，10 元，5 元，2 元，1 元。

思考：如果商店售货员找给 1 个顾客 140 元，假设钱币的面值有九种：100 元，70 元，50 元，20 元，10 元，7 元，5 元，2 元，1 元。用贪婪算法得到的是该问题的最优解吗？

编程要求

请在右侧编辑器Begin-End处补充代码，完成本关任务，注意需要学生自己获取找的钱 n。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：123（需要找给顾客的钱 n元）

预期输出：

100元 1张 50元 0张 20元 1张 10元 0张 5元 0张 2元 1张 1元 1张

#include <stdio.h>

void main()
{
    /**********  Begin  **********/
    int n;
    //printf("请输入需要找的钱数 n 元：");
    scanf("%d", &n);
        
    int denominations[] = {100, 50, 20, 10, 5, 2, 1};
    int result[7] = {0}; // 七种面额的纸币数量
                    
    int i;
    for (i = 0; i < 7; ++i) {
        while (n >= denominations[i]) {
            result[i]++;
            n -= denominations[i];
        }
    }
    //printf("找零纸币的最少张数如下：\n");
    for (i = 0; i < 7; ++i) {
        printf("%d元 %d张\n", denominations[i], result[i]);
    }
    /**********  End  **********/
}