ex08 贪心找零钱

要学习的知识点

贪心法的逐步选择
硬币面值与找零
divmod() 商和余数
循环中的变量更新
贪心策略的适用限制

题目

练习 8：用面值 100、50、20、10、5、1 的硬币找零。

输入一个非负整数金额；此面值组合下按从大到小取币。

参考程序：ex08.py；空白练习：lx08.py。

完整代码

以下内容与 ex08.py 一致，可对照右侧讲解阅读。

"""练习 8：用面值 100、50、20、10、5、1 的硬币找零。
输入一个非负整数金额；此面值组合下按从大到小取币。

学习说明：
- 输入金额后先检查是否为负数；负数不符合题意。
- remaining 表示还没有找出的金额；按硬币从大到小处理。
- divmod(remaining, denomination) 返回商和余数：商是该面值所需枚数，余数留给下一面值。
- total_coins 累加所有枚数。这里的硬币面值组合支持该贪心策略。
"""
amount = int(input())
if amount < 0:
    print("amount must be non-negative")
else:
    remaining = amount
    total_coins = 0
    for denomination in (100, 50, 20, 10, 5, 1):
        count, remaining = divmod(remaining, denomination)
        print(denomination, count)
        total_coins += count
    print("total:", total_coins)

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex08_adv.py

"""练习 8 进阶版：用列表保存每种面值数量，再统一输出和求总数。"""
amount = int(input())
if amount < 0:
    print("amount must be non-negative")
else:
    denominations = (100, 50, 20, 10, 5, 1)
    counts = []
    remaining = amount
    for denomination in denominations:
        count, remaining = divmod(remaining, denomination)
        counts.append(count)

    for denomination, count in zip(denominations, counts):
        print(denomination, count)
    print("total:", sum(counts))

zip() 将面值和数量逐项配对，sum() 汇总硬币数；divmod() 仍负责每轮贪心选择，remaining 按顺序更新。

运行结果

示例输入：

程序输出：

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`divmod(a, b)`	返回二元组 (a // b, a % b)，即商和余数。	除数 b 不能为 0。
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`int(value, base=10)`	把整数文本或数值转换为整数。	int('3.5') 不合法；按指定进制解析时可传 base。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。

贪心算法像什么

想象付款找零：先尽可能多用最大面值，剩下的钱再处理。每一步只做当前选择，不回头改之前的决定，这就是贪心的直观含义。

从 100 元面值开始，商告诉我们最多能取几枚。
余数留下来交给 50 元面值处理。
继续处理 20、10、5、1 元，直到余数为零。

贪心策略并非对任意硬币系统都正确。例如面值为 1、3、4 时，找 6 元：先取 4 再取两个 1 共 3 枚；最佳是两个 3 共 2 枚。先判断题目的面值是否适用贪心。

函数与运算说明

写法	参数与返回值	本题应用
`int(input())`	读取一行文本并转换成整数。	金额不能带小数；负金额被程序拒绝。
`divmod(a, b)`	返回二元组 `(a // b, a % b)`，即商和余数。	商是当前面值硬币数量，余数是尚未找出的金额。
`range(...)`	生成整数序列供 for 循环使用。	这里直接遍历硬币面值元组，而不是使用 range。
`print(...)`	输出多个值；默认空格分隔，返回 None。	每轮打印一个面值和对应枚数。

追踪变量

count, remaining = divmod(remaining, denomination)

等号右侧先计算二元组，再按顺序赋值。假设当前剩余 86、面值 50：divmod(86, 50) 得 (1, 36)，所以 50 元取 1 枚，余 36。变量名 count 和 remaining 的含义每一轮都会重新更新。

检查程序时，验证每轮都满足“原来的剩余金额 = 面值 × 枚数 + 新余数”，且余数小于当前面值。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试金额 0、1、99、100、101；再思考换一组硬币面值时贪心是否仍然最优。

先在 lx08.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。