programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

How can I get this algorithm to work correctly ?

Greenhorn
Posts: 13
Hello there!

I'm trying to implement something like the Change Maker Algorithm used by ATM's.

It is a mathematical problem, it says that I can use 5 cents coin and 3 cents coin to get any number greater than 7, for example; to get 8 cents I would need one 5cents coint and one 3cents coin, to get 10 cents I would need two 5cents coins.

This is what I have right now:

And it actually works with several numbers, but if I write 11, 12 or 13 for example, it fails.

Correct:

Incorrect:

Bartender
Posts: 772
27
• 1

David Martínez wrote:to get 10 cents I would need two 5cents coins.

If I'm not wrong,
AmountNo of 5 centsNo of 3 cents
1112
1204
1321
2132
2734

this is what you want alogorithm to produce?

Then IMO, you need to ponder on how would you decide how many cents of 5 and 3 will be needed If you have amount 10. Write that logic on a paper, dry run It manually write the value of each variable after execution of every step see that is what you want, If something else then how can you change the logic to get what you want, think about It. Once you get the result as expected then go for implementation.
• First you need to check amount should not be less than 8.
• As assumed amount = 10, we know 10 is completely divisible by 5 so we can have 2 cents of 5 only. So we have first condition If amount completely divisible by 5 means

• but what If we have 11 which is not completely divisible by 5? Now we got else part which will have logic for amount which is not completely divisible by 5.

Since we are in else part means there has to be some cents of 3 so start with taking one cent of 3 and deduct 3 from amount this way keep checking for cents of 3 until with some condition which you have to find out. If still has doubts you can ask.

Ranch Hand
Posts: 109
2
• 2
I tried to figure it out and with pen and paper and I can only do this with a for loop.
Let's say if you have the number 10, this program tests if 10-0*3 divides by 5, then assigns 10/5 the number of 5cents you need.
If you have 11 then 11-0*3 does not divide by 5.  It's only when b=2 that it becomes true. so 11-2*3 divides by 5 and then you have the number of 3cents and you can pull out from the loop.

Ganesh Patekar
Bartender
Posts: 772
27
Sergiu Dobozi,
Welcome to CodeRanch!

Your logic is way better and short than I thought.

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Ganesh Patekar wrote:Sergiu Dobozi,
Welcome to CodeRanch!

Your logic is way better and short than I thought.

Thank you Ganesh! That was really nice of you to say

David Martínez
Greenhorn
Posts: 13

Sergiu Dobozi wrote:I tried to figure it out and with pen and paper and I can only do this with a for loop.
Let's say if you have the number 10, this program tests if 10-0*3 divides by 5, then assigns 10/5 the number of 5cents you need.
If you have 11 then 11-0*3 does not divide by 5.  It's only when b=2 that it becomes true. so 11-2*3 divides by 5 and then you have the number of 3cents and you can pull out from the loop.

This worked perfectly! Thank you so much!
Thank you too, Sergiu!

Sergiu Dobozi
Ranch Hand
Posts: 109
2
No problem, David. It was a fun exercise

Sheriff
Posts: 12019
196
Good job working out the basic idea.

However, the solution provided is opaque and convoluted. It's really a lot simpler than that. Basically, you just keep subtracting 3 until you get a number that's evenly divisible by 5. The calculations can be done with two lines of code and another line of code to display the results.

Notice the comment and semicolon at the end of the loop statement. All the work is done in the loop header. The variable that accumulates the 3-cent count needs to be declared/init'd outside the loop. Alternatively, you can write it like this:

The comment is obviously optional but I prefer to put it there to make it clear that there's nothing else to be done.

Junilu Lacar
Sheriff
Posts: 12019
196
I found some interesting unexpected behavior while testing my solution out. I had naively used/modified the parameter in the loop instead of copying it to a loop variable. This gave me some results that I can't really explain.

I'm not really sure why the results get messed up like that but it seems like something on the stack is getting seriously clobbered. Kind of makes me wonder if there are any security-related implications related to this. Nevertheless, I think I have found a good reason to declare method parameters final. Doing so would have made me realize my mistake and do something about it.

Edit: <facepalm> Ok, I see why the output is like that now. My brain was stuck on the belief that num kept the value that it came in with and expected the System.out.println to see it my (mistaken) way. No stack was injured in this exercise after all.

Junilu Lacar
Sheriff
Posts: 12019
196
• 2
Just so nobody takes the "opaque and convoluted" remark personally, the code I gave is a little opaque, too. By "opaque" I mean that it's not clear and expressive. "Convoluted" just means that the code is more complicated than it needs to be.

This attempt doesn't make me feel much better about the clarity:

So maybe a short comment would be better in this case:

I can live with that

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Junilu Lacar wrote:Good job working out the basic idea.

However, the solution provided is opaque and convoluted. It's really a lot simpler than that. Basically, you just keep subtracting 3 until you get a number that's evenly divisible by 5. The calculations can be done with two lines of code and another line of code to display the results.
[code]
void makeChangeFor(int num) {
int i = 0;
for (int n = num; n % 5 != 0; n -= 3, i++) /* empty loop body */ ;

System.out.printf("Change for %d cents => @%d 5 cents, @%d 3 cents%n", num, (num - i*3)/5, i);
}

That's great, I didn't know that one can write a for loop like this. I had to write a random condition like threer<=n to make up for this lack of knowledge. I also realized I used too many assignments in my logic

Junilu Lacar
Sheriff
Posts: 12019
196

Sergiu Dobozi wrote:That's great, I didn't know that one can write a for loop like this.

The standard Java for-loop can have compound initialization expressions as well as compound increment expressions. For initialization, I believe the variables need to be of the same type. The terms in the compound expressions are separated by commas. Here's an example that uses 3 variables in tandem:

Of course, you might realize that this is a little more complicated than it needs to be. I'll leave that as an exercise.

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Junilu Lacar wrote:

Sergiu Dobozi wrote:That's great, I didn't know that one can write a for loop like this.

The for in your program could be written like this. I think this is the simplest I can come up with

Marshal
Posts: 59140
180
I suggest you use arr.length instead of creating a new local variable rows.

Ganesh Patekar
Bartender
Posts: 772
27
• 2
@Junilu It was really cool to know how we can utilize a for loop.

Nice to see different better ways to achieve one thing.

Greenhorn
Posts: 2
Good afteroon,

My name is Frank and I just starting working a Java class... I wanted to know if anyone can help me with the following problem which I'm currently stuck with.

"Given sphereRadius and piVal, compute the volume of a sphere and assign to sphereVolume. Use (4.0 / 3.0) to perform floating-point division, instead of (4 / 3) which performs integer division.  Volume of sphere = (4.0 / 3.0) π r3"

Here is my code, but whatever I do I can't seems to get this working.

import java.util.Scanner;

public class SphereVolumeCalculator {
public static void main (String [] args) {
double piVal = 3.14159;
double sphereVolume = 0.0;

sphereVolume = sphereRadius * ( 4.0 / 3.0) * piVal;

System.out.println("Sphere volume: " + sphereVolume);
return;
}
}

Master Rancher
Posts: 2655
91
hi Frank,

welcome to the ranch!

What your 'SphereVolumeCalculator' class needs is a methood, lets call it 'calculate', that takes a radius as parameter and returns the volume. So, like this

With this static method, you are now able to use it like this:

You do not need to have a field called piVal, since PI is standard present with Math.PI.
Do you know how to raise a value to the power of 3?

Frank Ventura
Greenhorn
Posts: 2
Actually, the code that is given by the school text book is this

public class SphereVolumeCalculator {
public static void main (String [] args) {
double piVal = 3.14159;
double sphereVolume = 0.0;

/* Your solution goes here  */

System.out.println("Sphere volume: " + sphereVolume);
return;
}
}

All I have to do is to add my statement in the page where it reads /* Your solution goes here */.  So most of the text is provided I just need to insert my statement that will make the code work.
This is what I have sphereVolume = sphereRadius * (4.0 / 3.0) * piVal;.  but the code fails.

This is the result I get
Expected value: 696.9093816666666