自学内容网 自学内容网
自学内容网 > 正文

【算法与设计分析】第1关：找零钱问题

🕗 发布于 2024-10-18 02:57 算法  

任务描述
编程要求
测试说明
任务描述
本关任务：设计一个贪心算法，使得找的钱币张数最少。

商店售货员找给 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张

开始你的任务吧，祝你成功！

题目描述：

题目要求根据用户输入的一个金额 𝑛计算出该金额使用最少数量的纸币进行找零的情况。具体来说，我们需要找出不同面值的纸币（100元、50元、20元、10元、5元、2元、1元）各自需要多少张，以使得总共正好等于 n 元。

解题思路

1.定义面值数组：首先定义一个数组denominations来存储所有的面值。
2.计算每种面值的张数：对于每一个面值，计算该面值可以使用的张数。
3.更新剩余金额：每次计算完一个面值之后，从总金额中减去该面值所使用的总金额。
4.输出结果：最后输出每种面值所需要的张数。

代码实现步骤

  1. 导入必要的包

import java.util.Scanner;

  1. 定义主类和主方法
public class SmallChange {
    public static void main(String[] args) {

3.创建Scanner对象

Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象，用于从标准输入读取数据

4.获取需要找零的金额n

int n = scanner.nextInt(); // 读取用户输入的需要找零的金额

5.定义面值数组

int [] denominations = {100,50,20,10,5,2,1};// 定义面值数组
  1. 创建数组记录每种面值的纸币张数
int [] count = new int[denominations .length];// 创建数组记录每种面值的纸币张数
  1. 使用贪心算法计算每种面值的纸币张数
for(int i =0;i<denominations.length;i++){
count[i] = n/denominations[i]; //计算当前面值的张数
n-= count[i] * denominations[i];// 更新剩余需要找零的金额

]
  1. 输出结果
for (int i = 0; i < denominations.length; i++) {
    System.out.printf("%d元 %d张\n", denominations[i], count[i]); // 输出每种面值所需的张数
}
  1. 关闭 Scanner 对象
scanner.close(); // 关闭 Scanner 对象，释放资源

完整代码

package step1;

import java.util.Scanner;

public class SmallChange {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象，用于从标准输入读取数据

        // 获取需要找给顾客的钱 n 元
        int n = scanner.nextInt(); // 读取用户输入的需要找零的金额
        
        // 定义面值数组
        int[] denominations = {100, 50, 20, 10, 5, 2, 1}; // 定义面值数组
        
        // 用于记录每种面值的纸币张数
        int[] count = new int[denominations.length];

        // 使用贪心算法计算每种面值的纸币张数
        for (int i = 0; i < denominations.length; i++) {
            count[i] = n / denominations[i]; // 计算当前面值的张数
            n -= count[i] * denominations[i]; // 更新剩余需要找零的金额
        }

        // 输出结果
        for (int i = 0; i < denominations.length; i++) {
            System.out.printf("%d元 %d张\n", denominations[i], count[i]); // 输出每种面值所需的张数
        }

        scanner.close(); // 关闭 Scanner 对象，释放资源
    }
}

运行测试

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

可能出现的疑惑：

for (int i = 0; i < denominations.length; i++) {
    count[i] = n / denominations[i]; // 计算当前面值的张数
    n -= count[i] * denominations[i]; // 更新剩余需要找零的金额
}

详细解释

循环初始化：

for (int i = 0; i < denominations.length; i++)：

初始化循环变量 i 为 0。
循环条件为 i < denominations.length，即 i 小于面值数组的长度。
每次循环结束时，i 自增 1。
计算当前面值的张数：

count[i] = n / denominations[i]：

n 是当前剩余需要找零的金额。
denominations[i] 是当前处理的面值。
n / denominations[i] 计算出当前面值可以使用的张数。
结果存入 count 数组的第 i 个元素。
更新剩余需要找零的金额：

n -= count[i] * denominations[i]：

count[i] 是当前面值的张数。
denominations[i] 是当前处理的面值。
count[i] * denominations[i] 计算出当前面值使用的总金额。
从剩余金额 n 中减去当前面值使用的总金额。
逐步演示
假设用户输入的金额为 237 元，面值数组为 {100, 50, 20, 10, 5, 2, 1}。

第 1 次循环（i = 0）
denominations[i] = 100
count[i] = n / 100 = 237 / 100 = 2
n -= count[i] * denominations[i] = 2 * 100 = 200
n 更新为 237 - 200 = 37

第 2 次循环（i = 1）
denominations[i] = 50
count[i] = n / 50 = 37 / 50 = 0
n -= count[i] * denominations[i] = 0 * 50 = 0
n 保持不变，仍为 37

第 3 次循环（i = 2）
denominations[i] = 20
count[i] = n / 20 = 37 / 20 = 1
n -= count[i] * denominations[i] = 1 * 20 = 20
n 更新为 37 - 20 = 17

第 4 次循环（i = 3）
denominations[i] = 10
count[i] = n / 10 = 17 / 10 = 1
n -= count[i] * denominations[i] = 1 * 10 = 10
n 更新为 17 - 10 = 7

第 5 次循环（i = 4）
denominations[i] = 5
count[i] = n / 5 = 7 / 5 = 1
n -= count[i] * denominations[i] = 1 * 5 = 5
n 更新为 7 - 5 = 2

第 6 次循环（i = 5）
denominations[i] = 2
count[i] = n / 2 = 2 / 2 = 1
n -= count[i] * denominations[i] = 1 * 2 = 2
n 更新为 2 - 2 = 0

第 7 次循环（i = 6）
denominations[i] = 1
count[i] = n / 1 = 0 / 1 = 0
n -= count[i] * denominations[i] = 0 * 1 = 0
n 保持不变，仍为 0

最终结果
最终，count 数组的内容为 {2, 0, 1, 1, 1, 1, 0}，表示：

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

出每种面值所需的张数 循环输出解释：

for (int i = 0; i < denominations.length; i++) {
    System.out.printf("%d元 %d张\n", denominations[i], count[i]); // 输出每种面值所需的张数
}

详细解释

for (int i = 0; i < denominations.length; i++)：

初始化循环变量 i 为 0。
循环条件为 i < denominations.length，即 i 小于面值数组的长度。
每次循环结束时，i 自增 1。
输出每种面值所需的张数：

System.out.printf("%d元 %d张\n", denominations[i], count[i])：

%d 是一个占位符，表示输出一个整数。
denominations[i] 是当前面值数组中的面值。
count[i] 是当前面值所需的张数。
\n 是换行符，用于在每次输出后换行，使输出更加清晰易读。
输出示例
假设我们已经计算好了每种面值所需的张数，并且 count 数组的内容如下：

count[0] = 1 （100元 1张） count[1] = 0 （50元 0张） count[2] = 1 （20元 1张）
count[3] = 0 （10元 0张） count[4] = 0 （5元 0张） count[5] = 1 （2元 1张）
count[6] = 1 （1元 1张） 那么，这段代码将会输出：


100元 1张
50元 0张
20元 1张
10元 0张
5元 0张
2元 1张
1元 1张
逐步演示
假设我们从 n = 123 开始，并且 count 数组已经被填充完毕。

第一次循环 (i = 0)
输出 100元 1张
第二次循环 (i = 1)
输出 50元 0张
第三次循环 (i = 2)
输出 20元 1张
第四次循环 (i = 3)
输出 10元 0张
第五次循环 (i = 4)
输出 5元 0张
第六次循环 (i = 5)
输出 2元 1张
第七次循环 (i = 6)
输出 1元 1张
完整输出

总结：

解决问题的方法是使用贪心算法（Greedy Algorithm）。具体来说，是从最大面值开始，尽可能多地使用该面值，然后用剩余的金额重复这个过程，直到金额为零。

使用一个 for 循环，遍历 denominations 数组中的每一个元素，计算出每个面值所需的张数，并更新剩余金额。

for (int i = 0; i < denominations.length; i++) {
    count[i] = n / denominations[i]; // 计算当前面值的张数
    n -= count[i] * denominations[i]; // 更新剩余需要找零的金额
}

步骤 3: 输出结果
再次使用 for 循环，输出每种面值所需的张数。

for (int i = 0; i < denominations.length; i++) {
    System.out.printf("%d元 %d张\n", denominations[i], count[i]);
}

4. 实际应用示例
假设我们需要找零 123 元，面值数组为 {100, 50, 20, 10, 5, 2, 1}，那么：

使用 100 元，得到 1 张 100 元；

  1. 注意事项
    贪心算法适用性：这种方法适用于面值是递减的情况，且通常适用于货币系统，因为大多数货币系统的面值设计都是为了简化找零问题。
    特殊情况处理：在实际应用中，可能需要考虑一些边界情况，如输入非正数、面值数组为空等。
  2. 扩展思考
    可以尝试使用其他算法来解决类似问题，如动态规划（Dynamic Programming）。
    考虑不同的面值集合，以及如何优化算法以适应更多变的情况。

原文地址：https://blog.csdn.net/qq_43055855/article/details/142928923

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024