Hi,
I have a course on algorithms this semester. I know there are quite a few programmers here, so this should be quite simple for you. I just spent 5 hours trying to figure it out in the lab, but couldn't and I'm pretty sure the answer is quite simple.
Basically, you have an ordered list of numbers:
2
3
5
5
10
20
25
30
And what you need to do is with those 'coins' give change for a 35$ note or whatever.
So what I need to do is go through all the possible iterations and match all the possibilities.
I tried doing a bubble sort kind of thing.
So what I did was:
for loop from first element in array to last (i);
{
for loop from last element of coin array to current value of i;
{
check if value = 35; then add to counter of possible ways of giving change;
check if value < 35;
{
then add to total;
if total = 35 then add to counter;
if total > 35 remove that number from the total again
}
}
}
The problem with this is that it only goes through the number once. What I mean is that let's say it manages to find out that 30+5 = 35. It then goes to the next lower value in the coin array 25 instead of finding the other 30+5 and the 30+3+2.
I hope you understand what I am talking about.
I need a way to go through each possibility. Any suggestions.
Programming in C by the way.
Thanks.
I have a course on algorithms this semester. I know there are quite a few programmers here, so this should be quite simple for you. I just spent 5 hours trying to figure it out in the lab, but couldn't and I'm pretty sure the answer is quite simple.
Basically, you have an ordered list of numbers:
2
3
5
5
10
20
25
30
And what you need to do is with those 'coins' give change for a 35$ note or whatever.
So what I need to do is go through all the possible iterations and match all the possibilities.
I tried doing a bubble sort kind of thing.
So what I did was:
for loop from first element in array to last (i);
{
for loop from last element of coin array to current value of i;
{
check if value = 35; then add to counter of possible ways of giving change;
check if value < 35;
{
then add to total;
if total = 35 then add to counter;
if total > 35 remove that number from the total again
}
}
}
The problem with this is that it only goes through the number once. What I mean is that let's say it manages to find out that 30+5 = 35. It then goes to the next lower value in the coin array 25 instead of finding the other 30+5 and the 30+3+2.
I hope you understand what I am talking about.
I need a way to go through each possibility. Any suggestions.
Programming in C by the way.
Thanks.