This is a chance to use of the wonderful stack collection object to solve a practical problem. Well, it would be a practical problem if the people involved actually existed.

Destablian Coinage

The Republic of Outer Destablia has an ancient, and very strange, system of money. The basic monetary unit is called the frob, and coinage exists in several denominations of frob. However, there is no one-frob coin. The available coins are:

Coin	Abbr	Value
grop	g	3 frob
wunkus	w	7 frob
droogle	d	13 frob
krompus	k	16 frob
megakrompus	mk	37 frob

This can make it quite difficult to figure out what coins will add to a needed amount. (In a few cases it's actually impossible.)

In this lab, you will aid the people of Outer Destablia by creating a program which can figure out what coins are needed to pay a particular sum. For instance,

How many frobs do you wish to settle? 22 2 grop 1 krompus

or

How many frobs do you wish to settle? 10 1 grop 1 wunkus

or

How many frobs do you wish to settle? 11 It is not possible to pay 11 frob with official Destablian coins.

or

How many frobs do you wish to settle? 70 1 grop 2 wunkus 1 krompus 1 megakrompus

How To Find An Answer

The approach is to start with some megakropus, more than we need, and gradually substitute with smaller coins until we reach our target, or discover that we cannot. Our collection of coins (tentative solution) stays larger than our target amount, and we keep trying to reduce it until we get there. For instance, suppose we want to make ten frob. We start with enough mk to exceed ten (that only takes one of course), then replace with smaller coins to get to ten. Like this:

37:mk (37)

That's too much, so we replace it with the next coin down

16:mk (37),k (16)

Still too much. Again:

13:k (16),d (13)

So, we need to replace the d because it's still too big, but w is too small by itself, so we use two of them. (How ever many we need to avoid going below the target, ten.)

14:d (13),w (7),w (7)

We're still over, so we replace the right-most wunkus with a grop.

10:w (7),w (7),g (3)

So, we find that we can make 10 frob using one wunkus and one grop.

Here's a longer example: we need to spend 70 frob. Start out with enough mk to cover that, which is two:

74:mk (37),mk (37)

Substitute the right-most mk with a krompus. But a single k would give us only 53 frob. Two gives us only 69, so we need three. (If one of those totals were 70, we'd be done.)

85:mk (37),mk (37),k (16),k (16),k (16)

Well, that's to big, so we'll substitute a droogle for the last krompus. That still leaves us too much, so we keep up:

82:mk (37),k (16),k (16),k (16),d (13)

76:mk (37),k (16),k (16),d (13),w (7)

72:mk (37),k (16),k (16),w (7),g (3)

Well, we're down to a grop at the right. We still have too much, and there's nothing smaller than a grop. So we discard the grop and replace the krompus behind it. The next coin down from krompus is a droogle, and we'll get enough of those to avoid going below 70.

79:mk (37),k (16),k (16),g (3),d (13),d (13)

It's still too much, so reduce the right droogle.

73:mk (37),k (16),d (13),d (13),w (7)

Replace the wunkus, needing two grops to stay large enough

72:mk (37),k (16),d (13),w (7),g (3),g (3)

Again, we've reached grop on the right, but we still have too much. We must remove the grops and work on the droogle. The wunkus is the next smaller from the droogle.

74:mk (37),k (16),d (13),g (3),g (3),w (7),w (7),w (7)

Too large, replace the rightmost wunkus.

70:mk (37),k (16),w (7),w (7),w (7),g (3)

Now, we have reached the target of 70 frob, and we're done: One megakrompus, one krompus, two wunkus and a grop make 70 frob.

Saved By The Stack

As you've no doubt guessed by now, we can use a stack to solve this problem. We implement the algorithm describe above using a stack of Destablian coins to represent our trial solution. The right end of the lists in the example above correspond to the top of the stack. As in that example, the smaller coins stay closer to the top. Here is a more formal statement of the algorithm:

amount the amount to pay, in frobs stack An empty stack of Destablian coins Fill the stack with enough of the largest coin to at least pay the bill. while the total value of the coins on stack < amount do push a megakrompus onto stack Try to reduce the money on the stack by replacing the smallest coin (larger than a grop) with something smaller. while stack is not empty and the total value of the coins on the stack > amount do Find the first coin which can be replaced with a smaller one. while stack is not empty and the top of stack is a grop do pop stack If we found some coin larger than a grop, replace it with smaller ones until we again reach the amount. if stack is not empty then oldtop stack.pop() less the coin next smaller than oldtop while the total value of coins on stack < amount do push less on stack We left the loop above either because the stack has just the right value, or it's empty so we have nothing left to try. if stack is empty then It is impossible to pay amount in Destablian coins. else The coins on the stack will add up to amount

You need to know the total value of the coins on the stack. You can make a method to total the value of the stack without destroying it, but it is probably a lot easier to just keep a running value which you update whenever you change the stack. Here's what the algorithm looks like running the above example to pay 70 frob. (amount = 70). The first line shows the stack and its value after the initial filling loop, then after each iteration of the main loop.

Value	Stack
74	megakrompus megakrompus	The initial filling loop runs twice so the stack value exceeds amount.
85	megakrompus krompus krompus krompus	The top inner loop runs zero iterations since the top of the stack is not a grop. The stack not being empty, we enter the if and pop the top megakrompus into oldtop. Then less will be krompus. Now the stack contains 37, so we enter the second loop and it will run three times (entering with stack totals 37, 53, 69, and exiting with 85 after pushing the third krompus).
82	megakrompus krompus krompus droogle	Again, zero iterations for first inner loop, so oldtop becomes krompus, and less is a droogle, which we'll push once.
76	megakrompus krompus krompus wunkus	Similar, zero for first loop, one for second. oldtop is droogle; less is wunkus.
72	megakrompus krompus krompus grop	Again, this time oldtop is wunkus and less is grop.
79	megakrompus krompus droogle droogle	The outer loop keeps going since the stack is not empty, and 72 > 70. The first inner loop will run once, removing the top grop. The if is true, oldtop receives the top krompus. That makes less a droogle, and the second inner loop pushes two of them to get the stack value up from 53 to 79.
73	megakrompus krompus droogle wunkus	Again, the first inner loop has nothing to do, then oldtop and less are droogle and wunkus, respectively. The second loop runs once.
72	megakrompus krompus droogle grop grop	First inner loop does nothing, oldtop gets wunkus and less is grop. Inner loop runs twice.
74	megakrompus krompus wunkus wunkus wunkus	Now the first loop has some work to do; it runs twice to clear the grops. Then oldtop = droogle, so less is wunkus, and the inner loop must run three times.
70	megakrompus krompus wunkus wunkus grop	Again no work for top inner, oldtop gets wunkus and less is grop. One iteration on the inner loop.
70	megakrompus krompus wunkus wunkus grop	The main loop exits because 70 > 70 is false. The stack not being empty, we have found the answer.

Procedure

1. Download Coins.java and compile it. The Coins class represents the five types of Destablian coins, and contains some convenience methods for writing the main program. Have a look at it, and perhaps note how some of its methods could help with steps in the algorithm.
2. Create a class with a main method which reads in a target amount and solves the change problem by implementing the above algorithm. Report your answer by either printing a message that the figure is impossible, or by printing the final stack. Running it might look like this:

   How many frobs do you wish to pay? 59 Coins to pay 59 frob: [ megakrompus, krompus, grop, grop ]

   where you simply use System.out.println() to print the stack.
3. You are free to write additional helper methods or classes if you wish.
4. You will need to create a Scanner to prompt and read the the target value. This should be familiar territory.
5. Create a Stack of Coins.Coin to hold the current guess. Use Stack from the Java standard libraries. (Note: You should not use the search method provided by the Java Stack.)
6. You may want to create an object of class Coins. It has several useful utility methods. The smallest() and largest() methods return any grops or megakrompuses you might need, and isSmallest and isLargest can tell if the coin you just popped happens to be one of those. The smaller method will also be of use.
7. You are permitted to modify the Coins class if you wish. (That is a permission, and not a recommendation.)
8. If you need to debug, you might consider printing the value and stack each iteration, and then run your program with input 70, since you have the correct values listed above.
9. Optional Extension. The examples in the first section have a prettier way of printing the results. If you like, replace the code that prints the stack as the final answer with one that prints each coin present with counts, as:

   How many frobs do you wish to pay? 59 2 grop 1 krompus 1 megakrompus

   This involves creating a loop which pops each item from the stack, and counts repeats. There are both single and nested loop solutions. However, your program will be considered complete without this extension.
10. Send your work through Moodle. Send any Java file which you created or modified.

/* * This represents the collection of Destablian coins. */ class Coins { // This is one coin. public class Coin { private Coin(String name, int value) { m_name = name; m_value = value; } public String getName() { return m_name; } public int getValue() { return m_value; } private String m_name; private int m_value; public String toString() { return m_name; } }

// This is the collection of all the coins. private Coin[] m_coins = { new Coin("grop", 3), new Coin("wunkus", 7), new Coin("droogle", 13), new Coin("krompus", 16), new Coin("megakrompus", 37) };

/* * Methods for the collection. */

// The smallest and largest coins (a grop or a mmegakrompus, respectively). public Coin smallest() { return m_coins[0]; } public Coin largest() { return m_coins[m_coins.length-1]; }

// See if you've got one of those. boolean isSmallest(Coin c) { return c.getValue() == m_coins[0].getValue(); } boolean isLargest(Coin c) { return c.getValue() == m_coins[m_coins.length-1].getValue(); }

// In case you wanted a specific one. Zero is the // smallest one. Coin at(int i) { return m_coins[i]; }

// Find the next smaller coin, or return null if // there is none. Coin smaller(Coin than) { for(int i = 1; i < m_coins.length; ++i) { if(m_coins[i].getValue() == than.getValue()) return m_coins[i-1]; } return null; } }

write in java, thanks