Homework 9. Coin Set Design

EE3980 Algorithms
Homework 9. Coin Set Design

Currently in Taiwan, we have $1, $5, $10 and $50 NTD coins. Thus, any dollar amount
less than 100 must consist of a number of coins. For this assignment please write a function that
determines the minimum number of coins to represent a integer D, 1 ≤ D ≤ 99, using greedy
algorithm.
int NCoinGreedy(int D, int NCoin, int Coins[]);
The function parameter Ncoin represents the number of different coins and it is 4 for Taiwan’s
currency system. The array parameter Coins[] is the value of coins, arrange from small to large.
And it is Coins[] = {1, 5, 10, 50} for Taiwan’s system. Using this function, please calculate
the average number of coins one needs to carry if the probabilities of carrying $1 to $99 coins are
equal.
Suppose you are given the job of redesigning the coin set to minimize the average number
of coins to carry. Please write a C program to find the following.
1. Coins $1, $5, and $10 must be kept while $50 can be changed. Please find what should
be the value of coin replacing $50 such that the average number of coins from $1 to $99 is
minimum.
2. Coins $1, $5, and $50 must be kept while $10 can be changed. Please find what should
be the value of coin replacing $10 such that the average number of coins from $1 to $99 is
minimum.
3. Coins $1, and $5 must be kept while $10 and $50 can be changed. Please find what should
be the values of coins replacing $10 and $50 such that the average number of coins from $1
to $99 is minimum.
All those the capabilities above should be implemented in a single program and the output
of the program should look like the following:
$ a.out
For coin set {1, 5, 10, 50} the average is d.ddddd
Coin set {1, 5, 10, dd} has the minimum average of d.ddddd
Coin set {1, 5, dd, 50} has the minimum average of d.ddddd
Coin set {1, 5, dd, dd} has the minimum average of d.ddddd
1
Notes.
1. One executable and error-free C source file should be turned in. This source file should be
named as hw09.c.
2. A report file in pdf format is also needed. This file should be named as hw09a.pdf.
3. Submit your hw09.c and hw09a.pdf on EE workstations using the following command:
∼ee3980/bin/submit hw09 hw09.c hw09a.pdf
where hw09 indicates homework 9.
4. Your report should be clearly written such that I can understand it. The writing, including
English grammar, is part of the grading criteria.
2