最少纸币数量计算：穷举法实现

最少纸币数量计算：穷举法实现

本关任务：假设目前的纸币系统包含 5 种纸币，分别为 1 元、5 元、16 元、23 元和 33 元。输入要购买物品的价格 n（1～99 元的整数），求购买该价格的物品最少需要几张纸币？

穷举法解决

根据题设，我们可以使用穷举法来解决这个问题。以下是对原程序的修改：

#include <iostream>
using namespace std;

int main()
{
    int n;
    int a, b, c, d, e;
    int minNumOfNotes = INT_MAX; // 初始化最小纸币数量为最大整数

    cin >> n; // 输入要购买物品的价格

    for(e = 0; e <= n / 33; e++){
        for(d = 0; d <= n / 23; d++){
            for(c = 0; c <= n / 16; c++){
                for(b = 0; b <= n / 5; b++){
                    a = n - 33 * e - 23 * d - 16 * c - 5 * b;
                    
                    if(a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0)
                    {
                        int totalNotes = a + b + c + d + e; // 计算纸币总数

                        if(totalNotes < minNumOfNotes)
                        {
                            minNumOfNotes = totalNotes; // 更新最小纸币数量
                        }
                    }
                }
            }
        }
    }

    cout << minNumOfNotes << endl; // 输出最少需要的纸币数量

    return 0;
}

这段代码会根据输入的价格 n，通过穷举法计算出最少需要的纸币数量，并输出结果。

总结

本程序使用穷举法，通过枚举所有可能的纸币组合来找到最少纸币数量。尽管这种方法简单易懂，但对于复杂的纸币系统或更大范围的价格，计算效率可能较低。