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

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～