[Total 3 pts] In this study, we explore some problems that arise when employing
ID: 3784173 • Letter: #
Question
[Total 3 pts] In this study, we explore some problems that arise when employing finite data types in practice. The mini application may be downloaded at https://github.com/huiannie/FaultyTeller. In this application, the program implements a teller machine that dispenses money in specific denominations. The dispenser unit (in
the module Dispenser.java) is faulty, leading to the following behavior:
a) [2pts] There are 2 major errors in the dispenser unit. The first is coin counting. The second is the computation of the total. Correct these errors and submit the Dispenser.java module. Before you submit your program, please make sure to test your work using the driver provided. You should not modify the other modules.
b) [1pt] For each denomination, what is the maximum number of coins that this machine may dispense? Explain why.
Enter an amount (truncated to 2 decimal places) 2.21 You have requested $2.21 Dispensing 2 dollars 0 quarters 2 dimes 0 nickels 0 pennies Total dispensed $2.2 Incorrect Enter an amount (truncated to 2 decimal places) 2.09 You have requested $2.09 Dispensing 2 dollars quarters 0 dimes 1 nickels 3 pennies Total dispensed $2.0799999999999996 IncorrectExplanation / Answer
What you are looking for is Dynamic Programming.
You don't actually have to enumerate all the possible combinations for every possible values, because you can build it on top of previous answers.
You algorithm need to take 2 parameters:
And the goal is to compute the minimal set of coins required for this range.
The simplest way is to proceed in a bottom-up fashion:
It is somewhat easy, at each step we can proceed by adding at most one coin, we just need to know where. This boils down to the fact that the range [x,y] is included in [x,y+1] thus the minimal set for [x,y+1] should include the minimal set for [x,y].
As you may have noticed though, sometimes there are indecisions, ie multiple sets have the same number of coins. In this case, it can only be decided later on which one should be discarded.
It should be possible to improve its running time, when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for, I think.
For example, note that:
we add a nickel to cover [1,5] but this gives us up to [1,9] for free!
However, when dealing with outrageous input sets [2,3,5,10,25] to cover [2,99], I am unsure as how to check quickly the range covered by the new set, or it would be actually more efficient.
What you are looking for is Dynamic Programming.
You don't actually have to enumerate all the possible combinations for every possible values, because you can build it on top of previous answers.
You algorithm need to take 2 parameters:
- The list of possible coin values, here
[1, 5, 10, 25] - The range to cover, here
[1, 99]
And the goal is to compute the minimal set of coins required for this range.
The simplest way is to proceed in a bottom-up fashion:
Range Number of coins (in the minimal set) 1 5 10 25 [1,1] 1 [1,2] 2 [1,3] 3 [1,4] 4 [1,5] 5 [1,5]* 4 1 * two solutions here [1,6] 4 1 [1,9] 4 1 [1,10] 5 1 * experience tells us it's not the most viable one :p [1,10] 4 2 * not so viable either [1,10] 4 1 1 [1,11] 4 1 1 [1,19] 4 1 1 [1,20] 5 1 1 * not viable (in the long run) [1,20] 4 2 1 * not viable (in the long run) [1,20] 4 1 2 It is somewhat easy, at each step we can proceed by adding at most one coin, we just need to know where. This boils down to the fact that the range [x,y] is included in [x,y+1] thus the minimal set for [x,y+1] should include the minimal set for [x,y].
As you may have noticed though, sometimes there are indecisions, ie multiple sets have the same number of coins. In this case, it can only be decided later on which one should be discarded.
It should be possible to improve its running time, when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for, I think.
For example, note that:
[1,5] 4*1 1*5 [1,9] 4*1 1*5 we add a nickel to cover [1,5] but this gives us up to [1,9] for free!
However, when dealing with outrageous input sets [2,3,5,10,25] to cover [2,99], I am unsure as how to check quickly the range covered by the new set, or it would be actually more efficient.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.