Python实现BETTERCHANGE找零算法返回结果异常如何修复

你的代码运算顺序错误，未先对可兑换的硬币数量取整就直接扣减对应金额，相当于逻辑上允许使用非整数枚硬币：第一次循环时40除以25得到1.6，直接用1.6计算扣减金额的话会直接把40全部扣完，后续面值的兑换数量自然全部为0，才会得到错误输出[1, 0, 0, 0, 0]。

做两处调整即可：

• 无需将待找零金额转为浮点数，直接用整数运算避免潜在的精度问题
• 调整循环内的运算顺序：先计算当前面值最多可兑换的整数枚数，再用整数枚数计算剩余待找零金额

修改后的代码如下：

def BETTERCHANGE(M,c,d):
    r = M
    result = []
    for k in range(1,d+1):
        # 先取当前面值最多可兑换的整数枚数
        i = r // c[k-1]
        result.append(i)
        # 再扣减对应整数枚数的金额
        r = r - c[k-1]*i
    return result

M = 40
c = [25,20,10,5,1]
d = 5
print(BETTERCHANGE(M,c,d))

运行上述代码即可得到你需要的输出[1, 0, 1, 1, 0]，和教材描述的错误返回结果一致。

内容的提问来源于stack exchange，提问作者riven