笔试-纸币找零算法

最近朋友面试遇到一个有意思的算法题，记录一下

题目如下：
1、现有i 张十元纸币，j张五元纸币，k张两元纸币，购物后要支付n元（i，j，k，n为整数）。要求编写一个复杂度为O(1)的函数FindSolution(i,j,k,n)功能是计算出能否用现在手上拥有的纸币是否足够并能刚好拼凑齐 n元，而不需要找零。

#! /usr/bin/env python
# -*-coding: utf-8 -*-


def test():
    print('设置拥有面值10、5、2的张数：')
    ten, five, two = [int(i) for i in input().split(',')]

    print("请输入需要计算的总金额")

    # 循环输入总金额进行计算
    # 用户输入总金额
    amount = int(input())
    while amount > 0:
        calculation(ten, five, two, amount)
        amount = int(input())
    if amount <= 0:
        print('输入金额数不能小于或等于零')
        return


# 整体思路：
# 从最大到最小面值依次使用，当出现最大面值使用后出现余数为其余下面值处理不了时考虑少使用一个或多个纸币
# 1.面值2与5能共同处理的余数为：2、4、5、6、7、8、9、10、11、12、13到无群大
# 2.面值2能处理的余数为：2、4、6、8等偶数

# 当面值10求余为1、3时，需要少一个面值10，将余数变为11、13
# 当面值5求余为1、3等奇数时，需要少一个面值5，将余数变为6、8等偶数


def calculation(ten, five, two, amount):
    # 超出拥有总金额，提升钱不够
    total = ten * 10 + five * 5 + two * 2
    if amount > total:
        print('输入金额超出总金额 %d' % total)
        return

    # 计算需要面值10的张数
    tenUse = amount // 10
    tenUse = tenUse if (ten >= tenUse) else ten
    tempRemainder = amount - tenUse * 10
    if tenUse > 0:
        if tempRemainder == 1 or tempRemainder == 3:
            tenUse -= 1
            tempRemainder += 10

    # 计算需要面值5的张数
    fiveUse = tempRemainder // 5
    fiveUse = fiveUse if (five >= fiveUse) else five
    tempRemainder -= fiveUse * 5
    if fiveUse > 0:
        if tempRemainder % 2 != 0:
            fiveUse -= 1
            tempRemainder += 5

    # 计算需要面值2的张数
    twoUse = tempRemainder // 2
    twoUse = twoUse if (two >= twoUse) else two
    tempRemainder -= twoUse * 2

    # 通过余数为零来判断是否无需找零
    if tempRemainder == 0:
        print('无需找零，使用%2d张十元，%d张五元，%d张两元' % (tenUse, fiveUse, twoUse))
    else:
        print('！存在找零，拥有%2d张十元，%d张五元，%d张两元' % (ten, five, two))


if __name__ == "__main__":
    test()

运算结果

image.png