Back
Coin_Changing.cpp
Save
// Coin_Changing.cpp #include <bits/stdc++.h> using namespace std; int Swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } int Quick_Sort(int a[], int left, int right) { int pivot = a[(left + right) / 2]; int i = left; int j = right; while (i < j) { while (a[i] > pivot) { i++; } while (a[j] < pivot) { j--; } if (i <= j) { Swap(a[i], a[j]); i++; j--; } } if (i < right) { Quick_Sort(a, i, right); } if (left < j) { Quick_Sort(a, left, j); } } int Cashiers_Algorithm(int *c, int m, long n, int *s) { Quick_Sort(c, 0, 4); int i = 0; while (n > 0 && i < m) { s[i] = n / c[i]; n %= c[i]; i++; } if (n > 0) return false; else return true; } int main() { int m = 5; long n = 34; int c[] = {1, 5, 10, 25, 100}; int *s = (int*)calloc(m, sizeof(int)); cout << "m = " << m << endl; cout << "n = " << n << endl; if (Cashiers_Algorithm(c, m, n, s)) { for (int i = 0; i < m; i++) { cout << s[i] << " "; } } return 0; }