ITSA 202405 #1: Changing Coins

Xiao Ming wants to design a coin exchange machine that can be installed in vending machines for giving change. This machine can dispense four types of coins: "$50, $10, $5, and $1". However, because it needs to consider the coin situation inside the vending machine, it will first calculate all possible change scenarios to meet all situations. Please write a program that takes an amount as input and lists all possible coin exchange results.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input consists of only 1 line, which contains a single positive integer N (1 ≤ N ≤ 100), representing the amount to be exchanged.For each possible coin exchange result, please output 4 positive integers separated by spaces:
The first integer represents the number of $50 coins.
The second integer represents the number of $10 coins.
The third integer represents the number of $5 coins.
The fourth integer represents the number of $1 coins.
Please output all possible coin exchange results, in ascending order of quantity from the highest coin value to the lowest. For example, start by outputting the results with 0 $50 coins, and if there are ties, consider the number of $10 coins, then $5 coins, and finally $1 coins.
Each line of output must end with a newline character.
110 0 0 11
0 0 1 6
0 0 2 1
0 1 0 1

Thought Process

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

In the recursion, if value == 0, it means we have reached the amount N, so we can output the data in the coin vector. It's important to note that there should be no space character after the last data. Additionally, if types == 4 and value != 0, it means we have tried all types of coins but still cannot reach N, so we can return them directly.

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

Sample Code－ITSA 202405 #1: Changing Coins

#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
Tags

Related Posts

Comments