Algorithm help

[Kyouryoku]

Hey guys,
I'm doing an introductory programming course at uni and I've come across a question in the assignment that has me stumped.

This is the question:
You are asked to write a simple C program that will accept an integer value in the range of 5-95 and in increments of 5 at a time, representing the number of cents to give to a customer in their change. The program should calculate how many coins of each denomination and display this to the user. Valid coin values are 50, 20, 10 and 5. Your solution (program and algorithm) should be modular in nature. This requires the submission of a high-level algorithm and suitable decompositions of each step.

Righto, modular programming, got the basics of that.

What I've done is split it into the following:
GetData - get the number from the user
CalcData - Calculate how many coins to display
OutputData - Tell the user how many coins of a specific denomination etc.

I think its all good so far? (Hope so!)

I've got GetData down, basically ask for an input, read the input and save it to an integer.

CalcData is where I've gotten really confused. I can visualise it in my head but can't get it down onto paper. What I understand is that I have to take the integer that was entered previously, and then calculate how many possible variations that it can be made up of by different denominations and then output those.
I originally thought of
if (intname) = 5
printf ("it has 1 possible outcome - 1 5 cent coin:");
else
if (intname) = 10
printf (it has two possible combinations - 2 5 cent coins and or 1 10 cent coin)

etc etc
I'm sure there is a lot simpler way of doing that, and also it would be outputting the information in that module, making OutputData completely pointless.

Am I on the right track?
Any help would be appreciated,

thanks,
Richard

[MrViggy]

You probably want to use the mod operator (%), and start with the largest coin. Keep dividing the input number by coin amount until your result is 0.

Viggy

[kumaresh_ana]

As far as I understand the problem, you need not print all the possible combinations. Instead just print one solution (ss MrViggy said).

denomination[4] = {50, 20, 10, 5};
output[4] = {0, 0, 0, 0};
for(i = 0; i < 4 && input != 0; ++i)
{
if(input > denomination[i])
{
output[i] = input / denomination[i];
input = input % denomination[i];
}
}

Now your display function can read the output[] and print the result.

[ajbharani]

Richard,

Of course, this forum deals with Algorithms and datastructures. Please use a more appropriate title.

Bharani.