b511: 换铜板

这篇教学会示范 ZeroJudge 基础题库“b511: 换铜板”的解题过程。

题目需求

题目会提供五种以内不同面值的铜板，然后输入一个金额，将全部可能的找零方式列出。譬如有 3 种铜板面值分别是 1元、5 元、10 元，假设要凑出 17 元，可能会有 (2,1,1)、(2,3,0)、(7,0,1)、(7,2,0)、(12,1,0) 和(17,0,0) 的排列方式。

题目链接：b511: 换铜板

解答

这题的解法主要先列出“所有钱币的组合”，再将钱币数量乘以面额，如果总额等于题目的金额，就是正确的组合，由于钱币的面额不固定，所以必须使用 function 的方式处理，最后使用 zip 组合“数量”和“面额”，就能计算出最后的答案。

本题解法参考：https://www.youtube.com/watch?v=Zj1ti69Vtlg

参考：function、zip

while True:
  try:
    n = int(input())
    coin = [int(i) for i in input().split()]   # 錢幣面額
    mx = int(input())    # 總金額
    r = []               # 結果的串列
    def fn(f):
      h = len(f)         # 一開始是空串列
      if h == n:
        if sum([a*b for a, b in zip(f, coin)]) == mx:   # 將組合後的串列兩兩相乘
          r.append(f)    # 如果等於總額，就將結果存入 r 串列中
        return           # 串列如果長度已滿，就 return
      # print(f)         # 不清楚的話可以印出來看看
      for i in range(mx//coin[h]+1): fn(f+[i])           # 逐步往串列中添加資料
      # print(f+[i])     # 不清楚的話可以印出來看看
    fn([])    # 一開始是空串列
    r.sort()
    for i in r:
      print('(', end='')
      print(*i, sep =',', end=')')    # 打散串列後印出
      print()
  except:
    break

意见反馈