Calculating the number of required coins in Greedy

Question

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).

Answer 1

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.

Answer 2

As mentioned in the comments, you can visit this link

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