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. |
| 11 | 0 0 0 11 0 0 1 6 0 0 2 1 0 1 0 1 |
Thought Process
To recursively compute all possibilities, declare a void function called DFS. It should take three parameters: a Vector coin representing the quantities of 4 types of coins, an int value representing how much money is still needed, and an int type representing the current type of coin to be added in this recursion. Additionally, you can declare a global array 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.
In the recursion, run a for loop from 0 to value / type[types], indicating how many of the current type of coin can be used to make up the remaining amount. For example, if value is 11 and type[types] is 1, it means we can use 0 to 11 $1 coins. Set coin[types] to i, indicating the quantity of the current coin type being used, and call DFS with parameters coin, the remaining amount minus the current coin's value times i, and types + 1, indicating we need to consider the next type of coin.
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