找零问题。人民币值系统为：100 元、50 元、20 元、10 元、5 元、1 元。客 户购买了 20 元商品，递给收银员 100 元现钞，用最少的钱币数量进行找零。 要求：（1）用贪心算法设计并编写求解该问题的算法（7 分） （2）给出该算法的时间复杂度（3 分）

1. 贪心算法求解：

首先计算需要找回多少钱，即 100 - 20 = 80 元。然后按照面值从大到小的顺序依次考虑，每次尽可能地使用面值更大的钞票。因此，首先用一张 50 元的钞票，还需要找回 80 - 50 = 30 元。接着用一张 20 元的钞票，还需要找回 10 元。最后用一张 10 元的钞票和一张 5 元的钞票完成找零，共使用 4 张钞票。

因此，最少需要使用 4 张钞票完成找零。

2. 时间复杂度：

由于该算法只需要一次遍历，时间复杂度为 O(1)。

相关问题

编写一个金额找零的系统,用输入框输入一个整数,表示找零的数量,数值为1- 100。假如系统中有50、20、10、5、1这5种面额的纸币,显示每种纸币应该找的数量。例如 78元应该为50元1张、20元1张、5元1张、1元3张。

设计这样一个金额找零的系统，首先需要编写一个函数来接收用户输入的找零金额，并计算出各种面额的纸币需求。这里我们可以创建一个Python函数，如下：

def calculate_change(total_amount):
    # 定义面额及其对应纸币数量的字典
    bill_values = {
        50: 0,
        20: 0,
        10: 0,
        5: 0,
        1: 0
    }

    # 遍历面额，逐个减去直到总金额为0
    for value in sorted(bill_values.keys(), reverse=True):  # 先从大面额开始找零
        while total_amount >= value:
            bill_values[value] += 1
            total_amount -= value

    return bill_values

# 示例：用户输入找零金额
input_amount = int(input("请输入找零数量(1-100)："))
change_distribution = calculate_change(input_amount)
print("找零方案：")
for bill_value, count in change_distribution.items():
    print(f"{bill_value}元{'' if count == 1 else 's'}: {count}")

#

黑盒测试找零程序如下: 假设商店货品价格(R)皆不大于100 元(且为整数),若顾客付款在100元内(P),求找给顾客最少货币个(张)数?(货币面值50 元10 元,5 元,1 元四 种 )。

黑盒测试中的这个找零程序旨在解决当顾客支付金额P小于或等于100元时，如何给出最少的货币组合以完成找零的问题。这里的货币面额有四种：50元、10元、5元和1元。以下是算法的简单描述：

1. **判断条件**：首先检查支付金额P是否能直接用50元或100元纸币找零，如果可以，直接返回0。

2. **50元找零**：如果P能够被50整除，则用一个50元的硬币找零，P减去50元，继续这个过程直到P不足以再用50元。

3. **10元找零**：接着尝试用10元硬币填补剩余，再次减去10元，直到不能再用。

4. **5元和1元找零**：最后，用5元和1元的硬币补足剩余的差额。每次优先使用5元硬币，直到无法使用，然后用1元硬币。

**伪代码示例**：

def findChange(P):
    change = [0, 0, 0]  # 初始化四种面额的硬币计数

    while P >= 50:
        change[0] += 1  # 使用50元硬币
        P -= 50

    while P >= 10:
        change[1] += 1  # 使用10元硬币
        P -= 10

    P = round(P)  # 确保没有遗留的非整数部分，因为后续只能使用整数硬币

    while P > 0:
        if change[2] < 1:  # 如果还没有使用过5元硬币
            change[2] += 1  # 使用5元硬币
        else:
            change[3] += 1  # 否则使用1元硬币
        P -= 5

    return sum(change)