• Post Reply Bookmark Topic Watch Topic
  • New Topic

How can I get this algorithm to work correctly ?

 
David Martínez
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
Ganesh Patekar
Bartender
Posts: 696
23
Eclipse IDE Hibernate Java jQuery MySQL Database Netbeans IDE Oracle Spring Tomcat Server
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
     
    Sergiu Dobozi
    Ranch Hand
    Posts: 96
    1
    Java
    • Likes 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 696
    23
    Eclipse IDE Hibernate Java jQuery MySQL Database Netbeans IDE Oracle Spring Tomcat Server
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Sergiu Dobozi,
    Welcome to CodeRanch!

    Your logic is way better and short than I thought.
     
    Sergiu Dobozi
    Ranch Hand
    Posts: 96
    1
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 96
    1
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    No problem, David. It was a fun exercise
     
    Junilu Lacar
    Marshal
    Posts: 10411
    125
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Marshal
    Posts: 10411
    125
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Marshal
    Posts: 10411
    125
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 96
    1
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Marshal
    Posts: 10411
    125
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 96
    1
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    Campbell Ritchie
    Marshal
    Posts: 53225
    124
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I suggest you use arr.length instead of creating a new local variable rows.
     
    Ganesh Patekar
    Bartender
    Posts: 696
    23
    Eclipse IDE Hibernate Java jQuery MySQL Database Netbeans IDE Oracle Spring Tomcat Server
    • Likes 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    @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
    Greenhorn
    Posts: 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Rancher
    Posts: 1712
    47
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Rancher
    Posts: 1712
    47
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Consider Paul's rocket mass heater.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!