patterncMinor
A program to represent a coin amount using the smallest number of coins
Viewed 0 times
coinsmallestthenumberrepresentamountcoinsprogramusing
Problem
Recently, I was learning about greedy algorithms. One example that was given was an algorithm for exchanging a given money amount using the smallest number of coins. After the lecture, I wrote a C program implementing this:
Because my program can accept arbitrary inputs, this greedy algorithm may not always output the most optimal solution, but I am still interested in the quality of my implementation.
#include
#include
#include
static int compareDenominations(const void *a, const void *b) {
return (*((int*) b) - *((int*) a));
}
int main(int argc, char *argv[]) {
long amount;
int count;
long *denominations;
if (argc > 2) {
errno = 0;
amount = strtol(argv[1], NULL, 10);
if (errno || amount = denominations[i]) {
amount -= denominations[i];
denominationCount++;
}
denominations[i] = denominationCount;
}
if (amount) {
puts("The coin amount could not be represented using the given denominations.");
return EXIT_FAILURE;
}
printf("Counts: [ ");
for (i = 0; i < count; i++) {
printf("%ld ", denominations[i]);
}
puts("]");
return EXIT_SUCCESS;
}Because my program can accept arbitrary inputs, this greedy algorithm may not always output the most optimal solution, but I am still interested in the quality of my implementation.
Solution
-
Don't invent error messages. If
-
Flat is better than nested. I recommend to handle
-
Qudos for
-
The algorithm may fail to find a solution.
Don't invent error messages. If
strtol sets errno, use perror() to print a precise reason for a failure.-
Flat is better than nested. I recommend to handle
argc
-
Testing for duplicated denomination is easier after they are sorted.
-
while (amount >= denominations[i]) loop is a long way to say
denominationCount = amount / denomination[i];
amount %= denomination[i];
-
You may want to break the for (i = 0; i -
Qudos for
sizeof(*denominations). -
The algorithm may fail to find a solution.
Code Snippets
denominationCount = amount / denomination[i];
amount %= denomination[i];Context
StackExchange Code Review Q#145238, answer score: 8
Revisions (0)
No revisions yet.