# Calculating the number of required coins in Greedy

This is the code I've got so far:

``````#include <stdio.h>
#include <cs50.h>
#include <math.h>

int main(void);
{
float x;
x = userInput;

printf("O hai! How much change is owed?\n");
GetFloat;

if (x >= 0.0)
{

{
}
``````

I don't get how to have the program do the calculations to figure out the number of coins needed for the returning the change due.

Does the recommended reading for pset1 on the CS50 website have the information I need for this?

I just need help with writing up a working line of code for the if condition of an invalid input. I also need to be able to print the correct value when the user inputs the correct number upon being prompted again. I tried it with do-while and while loops, but it didn't work too well since the program would end as soon I entered a valid input upon being prompted (nothing after the `GetFloat()` function).

I was able to fix the problem of always getting a 1 no matter the input, but I still need to about the best way to check for and correct a situation where a user inputs a negative number, a letter, or any other character besides a decimal value as change. I do know how to do a `do...while` structure, I just need code that allows the program to do the math for coins again when the user gives valid input after being prompted. Just tell me what I need to add here along with the `do...while` loop, when I add it in at the bottom of the code (of course I'll put it before the `return 0;` line).

• This question appears to be off-topic because it is a request for individual tutoring rather than a specific, answerable question, and is not likely to be helpful for future visitors.
– Air
Aug 22, 2014 at 18:40

The Problem

Greedy is a coin change making problem, in which we are supposed to tell the minimum number of coins that add to make a certain value. The available coins are quarters(25), dimes(10), nickels(5), and pennies(1). For example, if a change of 30 is to be made, then

``````30 = 25 + 5    // this is what we need as minimum number of coins are required for the transaction
30 = 10 +10 + 10  // we don't bother of this
30 = 10 + 10 + 5 + 5   // and neither this, because the number of coins returned are greater than 2(which we got in the first case)
... and other combinations.
``````

Let `n` be the amount of change to be given and `count` be the number of coins that are to be returned.(Remember that we need to minimize the number of coins i.e. `count`). Let W = {25,10,5,1}, w(i) ∈ W, 1 <= i <= 4.

Brute Force

A simple solution that strikes to our mind is to take the value(n) and then check if it is greater than or equal to the w(i), if it is, then increase `count` by 1 and reduce `n` by w(i). Here is the python script for it.(I preferred writing .py over pseudocode)

``````n = 40  # change to be provided
count = 0
while n > 0 :
if n >= 25 :
n = n - 25
count = count + 1
elif n >= 10 :
n = n - 10
count = count + 1
elif n >= 5 :
n = n - 5
count = count + 1
elif n >= 1 :
n = n - 1
count = count + 1
print (count)
``````

http://ideone.com/2qjaCw

As beginner this was a good approach, but our algorithm has a loop that runs in O(n), so when the value of `n` is sufficiently large, then our program becomes slightly slow.(Although O(n) is not considered that poor, actually it is a good one.)

Heuristic Approach

But still there is a better way to do this, almost assumed to be in constant time.

``````n = 40 # change to be provided
count = 0
W = [25, 10, 5, 1]
temp = n
for i in range(0,4):
t = (int)(temp/W[i])
count = count + t
temp = temp - t*W[i]
print (count)
``````

http://ideone.com/ged3rS

In this approach, we keep the possible values of w(i) in an array W which is already stored. Then we iterate only 4 times(independent of what is the amount of change to be provided) and therefore we perform better even when there is a large input(the value of change).

At each iteration, we check for the amount of coins returned for a particular value of w(i). In the first iteration, we calculate the maximum number of coins worth 25 required to owe the change. And that's easily predictable that for any value `n`, the number of coins required will be the multiple of `W[i]`, which is just less than `n`, divided by `W[i]` itself. For example, let us take `n = 1024`, then,

`````` _________________________________________________________________________________
|Iteration | Value of coin under process | Value of n  | Number of coins required |
|_________________________________________________________________________________|
|          |                             |             |                          |
|   1      |            25               |    1024     | (int(1024/25)) = 40      |
|   2      |            10               |1024-25*40=24| (int(24/10)) = 2         |
|   3      |            05               |  24-10*2=4  | (int(4/5)) = 0           |
|   4      |            01               |   4-5*0=4   | (int(4/1)) = 4           |
_________________________________________________________________________________
``````

In this way, the total value of `count` becomes `40 + 2 + 0 + 4 = 46`. We store variables in `W` in descending order because we need to minimize the `count`, if we stored the values in `W` in ascending order, then we would have been maximizing the value of `count`.

• How well would this translate to C? And I also need to better understand what the W and W(i) are (and what's the "[]" for?). Aug 9, 2014 at 11:47
• Should I define the x in my code as 40, the way you did, or is mine fine the way it is in that regard? Will it be okay if I just take what you typed and convert into C for my program once I'm able to completely understand it? Aug 9, 2014 at 11:50
• No, this is a piece of code only to illustrate how you can tackle the problem. I wrote .py script because it is easy to understand(it looks almost similar to pseudocode) and for my comfort that I can directly test it on python interpreter for any bug. Then why didn't I do it in C? Do you remember the academic honesty? That's why, else that would become spoon-feeding. And this python script itself can't tackle the whole problem(even if you accurately convert it to C), there are still minor things needed to be added, that you should figure out on your own(as guided by the pset page). Aug 9, 2014 at 13:00
• The thing you did, is a bit okay, not fully. If you don't understand what W[] means, then try brute force approach only, leave heuristic one for later. Aug 9, 2014 at 13:12
• I've updated the first post twice as of now; please focus on just the second one, though, unless you want to get confused unnecessarily. Aug 10, 2014 at 2:44

Although the link demonstrates the use of while, you can also use the do-while loop. The do-while loop lets you take even the first input inside the loop.

Eg:

``````int n;
do
{
//prompt user for input
n=GetInt();
}while(n<0); //repeat the loop if the input taken by the use is negative

//code will automatically come out here if the input is positive.
//rest of the program
``````