#17095: c++ AC(附解析)


barry_1111 (123)

學校 : 臺北市私立延平高級中學
編號 : 69059
來源 : [203.72.178.252]
最後登入時間 :
2019-06-14 17:00:16
b511. 換銅板 -- 清華 MOOCs 2014 程式設計導論期末考 | From: [203.72.178.252] | 發表日期 : 2019-03-08 17:38

#include <cstdio>

int n;
int coins[5];
int counts[5];

void recursion(int money, int index) {
  // 金額已換完
  if (money == 0) {
    putchar('(');
    printf("%d", counts[0]);
    for (int i = 1; i < n; ++i) printf(",%d", counts[i]);

    puts(")");
    return;
  }
  // 換完最後一個面額後,仍然有剩餘金額,表示兌換失敗
  if (index >= n) return;

  // 計算最多可以換到幾個
  int times = money / coins[index];
  // 盡可能讓第一個面額換得最少,從不換開始算
  for (int t = 0; t <= times; ++t) {
    counts[index] = t;
    // 遞迴的部份:在扣掉當前面額之後,剩下的金額給其他的面額換
    recursion(money - coins[index] * t, index + 1);
  }
}

int main() {
  int money;
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; ++i) scanf("%d", &coins[i]);

    scanf("%d", &money);
    recursion(money, 0);
  }
  return 0;
}
 
ZeroJudge Forum