ITSA 202405 #1：換幣機

小明想設計一換幣機，可以裝在販賣機裡用於找零錢用，這台換幣機可以換出「50元、10元、5元、及1元」四種硬幣，但因為要考慮販賣機內的硬幣狀況，所以找錢時會先將換幣的狀況都先算出來，以符合所有狀況。
請您寫一個程式，輸入一個金額，該程式會列出各種可能的換幣結果。

範例測資

範例輸入範例輸出
輸入只有 1 行，為 1 個正整數 N (1 ≤ N ≤ 100），表示要找的金額數。每種換幣結果請輸出4個正整數，正整數間用空白隔開。
第1個正整數表示要幾個50元硬幣。
第2個正整數表示要幾個 10元硬幣。
第3個正整數表示要幾個5元硬幣。
第4個正整數表示要幾個1元硬幣。
請輸出所有可能的換幣結果，請依最大幣值到最小幣值之數量小到大順序輸出，例如先輸出50元硬幣0個的換幣結果，如有相同的則考慮10元硬幣數，接著比較5元、1元，以此類推。
每行輸出最後必有換行符號。
110 0 0 11
0 0 1 6
0 0 2 1
0 1 0 1

解題思路

使用遞迴的方式來將所有可能計算出來，宣告一個 void DFS，參數需要一個 Vector<int> coin 代表 4 種硬幣的數量、int value 代表目前還差多少塊錢、int types 代表目前這個遞迴要加的硬幣種類。然後可以宣告一個全域陣列 int type[4] = {50, 10, 5, 1}。

在遞迴中，如果 value == 0，就代表已經加到 N 了，就可以把 coin 中的資料進行輸出，需要注意的是最後一個資料後面不能有空格字元。另外，如果 types == 4 且 value != 0，代表已經把所有的硬幣都加過了但是沒有辦法加到 N，就直接 return。

在遞迴中跑一個 For迴圈，從 0 跑到 value/type[types]，代表剩下需要加的錢可以使用多少個目前 types 的硬幣。舉例來說，如果 value 是 11，然後 type[types] 是 1，代表可以使用 0 到 11 個 1 元硬幣。將 coin[types] 設定為 i，代表目前硬幣種類使用的數量，並且呼叫 DFS，參數要使用 coin、剩下的錢 – 目前使用的硬幣*i、types+1，代表要將去判斷下一種硬幣可以使用多少。

範例程式碼－ITSA 202405 #1：換幣機

#include <iostream>
#include <vector>
using namespace std;

int N;
const int type[4] = {50, 10, 5, 1};

void DFS(vector<int>coin, const int value , const int types) {
    if (value == 0) {
        for (int i = 0; i<4; i++) {
            cout << coin[i];
            if (i != 3) cout << " ";
        }
        cout << "\n";
        return;
    }
    if(types == 4) return;
    for (int i = 0; i<=value/type[types]; i++) {
        coin[types] = i;
        DFS(coin, value - type[types]*i, types+1);
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    cin >> N;
    vector<int>tmp;
    for (int i = 0; i<4; i++) tmp.push_back(0);
    DFS(tmp, N , 0);
}

//ITSA 202405 #1
//Dr. SeanXD
標籤

相關文章

發佈留言