How can I get this algorithm to work correctly ?

[David Martínez]

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:

import java.util.Scanner;

public class Centavos {
	
		public static void main(String[] args)
	    {
	        int amount, originalAmount, fiveCents, threeCents;
	         
	        System.out.println("Write an number greater than 7");       
	        Scanner keyboard = new Scanner(System.in);
	        amount = keyboard.nextInt();
	        originalAmount = amount;
	        
	        if(amount%2 == 0){
		        fiveCents = amount/5;
		        amount = amount%5;
		        threeCents = amount/3;

	        }else{
		        threeCents = amount/3;
		        amount = amount%3;
		        fiveCents = amount/5;

	        }
	        
	        System.out.println(originalAmount 
	                          + " cents: ");
	        System.out.println(fiveCents + " coins of 5 cents");
	        System.out.println(threeCents + " coins of 3 cents");
	    }
}

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

Correct:



Incorrect:

[Ganesh Patekar]

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

If I'm not wrong,

Amount	No of 5 cents	No of 3 cents
11	1	2
12	0	4
13	2	1
21	3	2
27	3	4

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

if (amount % 5 == 0) {
    totalFiveCents = amount / 5;
} else {
    // your logic If amount is not completely divisible by 5 is here
}

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.

[Sergiu Dobozi]

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.

int n=10;
int fiver=0;
int threer=0;
for(int b=threer;threer<=n;b++)
{
if((n-b*3)%5==0)
{fiver=(n-b*3)/5;
threer=b;
break;}
}
System.out.print(n+"="+fiver+"*5+"+threer+"*3");

[Ganesh Patekar]

Sergiu Dobozi,
Welcome to CodeRanch!

Your logic is way better and short than I thought.

[Sergiu Dobozi]

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]

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.

int n=10;
int fiver=0;
int threer=0;
for(int b=threer;threer<=n;b++)
{
if((n-b*3)%5==0)
{fiver=(n-b*3)/5;
threer=b;
break;}
}
System.out.print(n+"="+fiver+"*5+"+threer+"*3");

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

[Sergiu Dobozi]

No problem, David. It was a fun exercise

[Junilu Lacar]

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.

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);
}

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:

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);
}

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]

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.

        ...

	for (int i = 8; i < 15; i++)
		changer.makeChangeFor(i);
	...

	void makeChangeFor(int num) {
		int i = 0;
		for (; num % 5 != 0; num -= 3, i++) {}
		System.out.printf("Change for %d cents => @%d 5 cents, @%d 3 cents%n", num, (num - i*3)/5, i);
	}

Output: 

Change for 5 cents => @0 5 cents, @1 3 cents
Change for 0 cents => @-1 5 cents, @3 3 cents
Change for 10 cents => @2 5 cents, @0 3 cents
Change for 5 cents => @0 5 cents, @2 3 cents
Change for 0 cents => @-2 5 cents, @4 3 cents
Change for 10 cents => @1 5 cents, @1 3 cents
Change for 5 cents => @0 5 cents, @3 3 cents

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.

	void makeChangeFor(final int num) {
		int i = 0;

		// *** WON'T COMPILE because parameter is final ***
		for (; num % 5 != 0; num -= 3, i++) {}  

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

[Junilu Lacar]

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:

    void makeChangeFor(final int total) {
        int howMany3s = 0;
        for (int remainder = total; remainder % 5 != 0; remainder -= 3, howMany3s++) {}

        System.out.printf("Change for %d cents => (%d * 5c) + (%d * 3c)%n", total, (total - howMany3s * 3)/5, howMany3s);
    }

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

    void makeChangeFor(final int total) {
        int count = 0; // # of 3s to subtract to get a number that's divisible by 5
        for (int n = total; n % 5 != 0; n -= 3, count++) {}

        System.out.printf("Change for %d cents => (%d * 5c) + (%d * 3c)%n", total, (total - count * 3) / 5, count);
    }

I can live with that

[Sergiu Dobozi]

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]

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:

/**
 * Extracts elements on a diagonal of the specified array.
 *
 * The diagonal extracted starts at the bottom left corner
 * of the specified array, going up to the right. The nested
 * arrays are assumed to have uniform lengths. That is, arr
 * is assumed to be square/rectangular.
 */
int[] diagonalUp(int[][] arr) {
	int rows = arr.length;
	int cols = arr[0].length;
	int[] diagonal = new int[Math.min(rows, cols)];

	for (int i = rows-1, j = 0, k = 0; k < diagonal.length; i--, j++, k++) {
		diagonal[k] = arr[i][j];
	}
	return diagonal;
}

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]

Junilu Lacar wrote:

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

/**
 * Extracts elements on a diagonal of the specified array.
 *
 * The diagonal extracted starts at the bottom left corner
 * of the specified array, going up to the right. The nested
 * arrays are assumed to have uniform lengths. That is, arr
 * is assumed to be square/rectangular.
 */
int[] diagonalUp(int[][] arr) {
	int rows = arr.length;
	int cols = arr[0].length;
	int[] diagonal = new int[Math.min(rows, cols)];

	for (int i = rows-1, j = 0, k = 0; k < diagonal.length; i--, j++, k++) {
		diagonal[k] = arr[i][j];
	}
	return diagonal;
}

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

    for (int j = 0; j < diagonal.length; j++) {
        diagonal[j] = arr[rows-1-j][j];
 }

[Campbell Ritchie]

I suggest you use arr.length instead of creating a new local variable rows.

[Ganesh Patekar]

@Junilu It was really cool to know how we can utilize a for loop.

Nice to see different better ways to achieve one thing.

[Frank Ventura]

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;
     double sphereRadius = 0.0;

     sphereRadius = 1.0;

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

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

[Piet Souris]

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

class SphereVolumeCalculator {
    public static double calculate(double radius) {
        double volume = ???; // formula is given
        return volume;
    }
}

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

double volume = SphereVolumeCalculator.calculate(5.234);

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]

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;
     double sphereRadius = 0.0;

     sphereRadius = 1.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
 Testing with radius 1.0
Your value: 4.188786666666666
 Testing with radius 0.0
Your value: 0.0
✖   Testing with radius 5.5
Expected value: 696.9093816666666
Your value: 23.038326666666666

[Piet Souris]

Hmm, how does that testing program set the radius? Do you somewhere use a Scanner?

Also, have a look at your formula that calculates the volume. You should raise the radius to the power of 3. Since in the first two tests the radii were 0 and 1, this error didn't show up, but you see the difference when the radius is 5.