python - 如何计算硬币找零问题中的发生次数

Question

我有一堆[5, 10, 20, 50, 100, 500]给定值的现金票据x，找到总和为该值的最少可能票据，然后返回数组中这些票据的出现。我们假设我们只能接收可被整除的数字min(cash) = 5

例如

x = 5:
    return [1, 0, 0, 0, 0, 0]

以最少的笔记量接收 5 个，并且 5 个出现一次。

另一个例如

x = 1000
    return [0, 0, 0, 0, 0, 2]

因为最少的音符是两个 500 的。它们出现两次。这应该很容易，而且可能很容易，我想我快到了，但似乎无法绕过最后的障碍。

到目前为止，我的代码是：

def atm(x, cash=[5, 10, 20, 50, 100, 500]):
    count_5 = 0
    count_10 = 0
    count_20 = 0
    count_50 = 0
    count_100 = 0
    count_500 = 0
    if x == 5:
        return [1, 0, 0, 0, 0, 0]
    elif x == 10:
        return [0, 1, 0, 0, 0, 0]
    elif x == 20:
        return [0, 0, 1, 0, 0, 0]
    elif x == 50:
        return [0, 0, 0, 1, 0, 0]
    elif x == 100:
        return [0, 0, 0, 0, 1, 0]
    elif x == 500:
        return [0, 0, 0, 0, 0, 1]

    flag = None
    for c in cash:
        if c < x:
            flag = c
    temp_balance = round(x - flag, 2)

    if flag or temp_balance == 5:
        count_5 += 1
    if flag or temp_balance == 10:
        count_10 += 1
    if flag or temp_balance == 20:
        count_20 += 1
    if flag or temp_balance == 50:
        count_50 += 1
    if flag or temp_balance == 100:
        count_100 += 1
    if flag or temp_balance == 500:
        count_500 += 1

    return [count_5, count_10, count_20, count_50, count_100, count_500]


print(atm(150))

这返回的[1, 1, 1, 1, 1, 1]结果与我预期的不正确[0, 0, 0, 1, 1, 0]。我在这里做错了什么以及如何解决这个问题？

我已经部分使用了这个 YouTube视频，但是我没有使用递归。

我也在考虑时间复杂度，但处于创建更有效算法的早期阶段。因此，如果有更好的方法代替所有这些if elif陈述，那么我想从中学习。

标签： python

Answer 1

为什么您看到[1, 1, 1, 1, 1]（全 1）的部分问题是因为您的 if 语句中有错误：

    if flag or temp_balance == 100:

这不检查flag is 100 or temp_balance is 100它是否只是检查 if flag is non-zero OR temp_balance is 100，每次迭代都会如此。

其他一些问题：

1. 您有一个cash参数作为输入，但这不一定与您用于跟踪音符数量的变量相关。您应该找到一些方法来根据初始cash数组跟踪您的笔记。这可以像创建另一个相同长度的数组一样简单，该数组初始化为全 0，用于保存每个位置的现金钞票数量。note_count = [0 for _ in cash]
2. 不要试图提取完全匹配的特殊情况。它只会让你的代码更长。
3. 您不能对这个问题使用贪心算法。您需要动态编程之类的东西才能正常工作。考虑你的现金价值cash=[10, 50, 150, 200]，你就有了x=300。如果你使用贪心算法，你会记 3 个音符，200 个音符的 1 个音符和 50 个音符的 2 个音符，但你可以用 150 个音符的 2 个音符来做。

---

时间复杂度（用大 O 表示法表示O(n)）是关于执行长度如何作为某些输入的一个因素而增长

最典型的案例是n表示您的算法迭代的项目数（但它可以表示其他东西，例如执行一些按位数学运算的算法的输入的位长度）。如果您的现金系统的上限为某个数字，例如 10，那么您用于查找下一张现金钞票的循环将成为一个常数，因为您需要进行恒定次数的迭代以找到下一张要除以的钞票。事实上，在您的情况下，您在选择纸币方面具有恒定的时间复杂度，因为您已经明确写出了 6 个现金纸币案例。这里可变的是您的输入量，因此您的时间复杂度将取决于将给定量减少到 0 需要多长时间。

时间复杂度与两个操作之间的效率无关

当您谈论if, else if语句以及如何编写更高效的代码时，您可能会说“一个构造比另一个构造更有效或更快”是正确的，但这不是时间复杂度的含义。时间复杂度是关于执行长度如何作为某些输入的一个因素而增长的。例如，您可以通过使用字典来创建一个更有效的“选择”结构。字典具有恒定的时间访问权限，因此无论字典中有多少项，您的时间访问权限都是O(1). 但是，如果您有恒定数量的 if/else 语句，那也是O(1)因为您的 if/else 语句不会增长。它可能会慢一些，但它的复杂性仍然是不变的。