1

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 '14 at 18:40
4

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.

| improve this answer | |
  • 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?). – Osman Zakir Aug 9 '14 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? – Osman Zakir Aug 9 '14 at 11:50
  • 1
    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). – sinister Aug 9 '14 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. – sinister Aug 9 '14 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. – Osman Zakir Aug 10 '14 at 2:44
1

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
| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .