Can someone help me with this Greedy Algorithm question? Please walk me through

Question

Can someone help me with this Greedy Algorithm question? Please walk me through your steps, not just give me the answer, I want to be a able to replicate and learn what you are doing.

Given that you have coins in 1 cent, 5 cent, 10 cent, 25 cent and 1 dollar (100 cents) form. Develop a greedy algorithm pay the customer with the smallest number of coins. For example, 28 cents can be paid by using one 25 cent coin, 3 one cent coins. You only have to describe the algorithm and write the pseudocode. No code is necessary. (20) Prove that your algorithm does indeed give the correct answer (20)

Explanation / Answer

Here is the algorithm as per your requirements.

1) Start
2) Declare variables onecent, fivecent, tencent, twentyficecent, onedollar and num
3) Accept the num i.e the total amount for which you want to pay the coins.
4) Convert the num into cents
5) divide num with 100 and find out the result and the remainder
6) assign the remainder to num
7) assign the division result to onedollar
8) divide num with 25 and find out the result and the remainder
9) assign the remainder to num
10) assign the division result to twentyfivecents
11) divide num with 10 and find out the result and the remainder
12) assign the remainder to num
13) assign the division result to tencents
14) divide num with 5 and find out the result and the remainder
15) assign the remainder to num
16) assign the division result to fivecents
17) assign num to onecent
18) print variables onecent, fivecent, tencent, twentyficecent, onedollar
19) End

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---