This discussion is archived
12 Replies Latest reply: Jan 15, 2013 7:35 PM by baftos RSS

Help needed with past exam problem!! Referencing an array.

983019 Newbie
Currently Being Moderated
/*Write a segment of code that takes as its input an integer value for a sum of money in cents.
The program should return a list of notes and coins required to make up the sum of money.

The following run time display helps explain what is required.

Amount entered:84

50 20 10 2 2

Hint: The following line of code is where you could start.

int [] d = {5000,2000,1000,500,200,100,50,20,10,5,2,1};

Explain your reasoning.*/

package solutions;

import java.util.Scanner;

public class FourB {

     
     public static void main(String[] args) {
          
          Scanner sc = new Scanner(System.in);
          System.out.print("Please enter an amount of money in cents : ");
          
          int amount = sc.nextInt();
          
          int [] d = {5000,2000,1000,500,200,100,50,20,10,5,2,1};
          
          
          for(int i = 0; i < d.length; i++)
          {
               if(amount > amount % d)
               {
                    //System.out.print(amount + " ");
                    
                    amount = amount % d[i];
                    
                    System.out.println(d[i]);
                    
                    
               }
               
          }
          
     }

}

The code is running ok but will only output array element once..
For example with amount 444 it outputs 200,20,2 instead of 200,200,20,20,2,2.
Any help is greatly appreciated. Also this is my first post so if its in the wrong location please advise. Thanks
  • 1. Re: Help needed with past exam problem!! Referencing an array.
    939520 Explorer
    Currently Being Moderated
    I believe the following correction is what you need.
    It probably will not output the correct answer, but it may get you on the correct path.
    nt [] d = {5000,2000,1000,500,200,100,50,20,10,5,2,1};
    
    for(int i = 0; i < d.length; i++)
    {
    if(amount > amount % d)
    {
    //System.out.print(amount + " ");


    amount = amount % d[i];


    System.out.println(amount);


                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
  • 2. Re: Help needed with past exam problem!! Referencing an array.
    baftos Expert
    Currently Being Moderated
    Your algorithm is wrong. You should not start by writing Java code, but pseudo-code that you will later convert to Java.
    The right algorithm is known by virtualy any cashier in the world who has to give change and knows how to perform divisions and substractions and knows nothing about modulus (ony substractions would also work).
    Assume you have to give change and you have in front of you drawers with the different notes and coins sorted from largest to smallest. Write the basic mental steps in plain English.
    This is your pseudo-code. Run mentally or with a pencil in your hand a few exemples. If all looks fine, convert to Java.

    Edited by: baftos on Jan 4, 2013 5:04 PM
  • 3. Re: Help needed with past exam problem!! Referencing an array.
    Gowtham Gutha Newbie
    Currently Being Moderated
    for(int i = 0; i < d.length; i++)
    {
    if(amount > amount % d)
    {
    //System.out.print(amount + " ");

    amount = amount % d;

    System.out.println(d);
    break;

    }

    }

    Break the loop after once it is true.

    Gowtham Gutha.
  • 4. Re: Help needed with past exam problem!! Referencing an array.
    EJP Guru
    Currently Being Moderated
    Completely incorrect. The algorithm has already been described as wrong, and all you've done is add a break, contrary to the explicit instruction 'every' in the original question. Do read the thread before you post.
  • 5. Re: Help needed with past exam problem!! Referencing an array.
    morgalr Explorer
    Currently Being Moderated
    The basic flaw in the algo your instructor gave is that a for/next loop is a set number of loops as given. The problem given cannot be fit into a set number of loops... (but alas, it can, but not in my example) do as previously stated in posts: follow the process you would use manually and notice the phrasing you use, actually vocalize it outloud may help, it will give you your approach to the solution.

    here's a solution to your problem, it is not done the way the instructor wanted, nor at any level you can turn in, but you can see what it looks like--Merry Late Christmas:
    public class JMoneyLoops {
      public JMoneyLoops(int iStart){ //constructor
        int[] iMoney={10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1}; //denominations array
        int[] iMoneyCount={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //count of each denomination
        int i=0; //array index--used to select denomination and count elements
        int iWork = Math.abs(iStart);  //retain initial value, but have amount to work, account for negative numbers too
        for(boolean b=false; b!=true;){ //for loop modified to be a while loop
          if(iWork-iMoney>=0){ //is the amount left bigger or equal to the denomination 
    iMoneyCount[i]++; //increment the denominstion counter
    iWork-=iMoney[i]; //subtract the amount we just saved (denomination amount)
    }else{ //it's not
    i++; //move to next denomination and count element
    if(i==iMoney.length) b=true; //flagged exit when at the end of the array
    }
    }
    System.out.println("Given Amount: "+iStart); //report what we started with
    for(int j=0;j<iMoney.length;j++){ //iterate through all elements
    System.out.println(Integer.toString(iMoney[j])+" x "+Integer.toString(iMoneyCount[j])); //report our results
    }
    }
    public static void main(String[] args) { //java start--main
    if(args.length<1){ //did we get a value passed in
    System.out.println("Please enter an amount in cents on the command line."); //complain because we did not
    System.out.println(); //give a little space at the bottom between runs
    }else{
    new JMoneyLoops(Integer.parseInt(args[0])); //initialize the Object--entry point
    }
    }
    }
  • 6. Re: Help needed with past exam problem!! Referencing an array.
    EJP Guru
    Currently Being Moderated
    Blimey. It's not that complicated. All he needs is a division and a modulus, and yes it can be done within the original loop structure. At root it's just an exercise in multi-radix conversion.
  • 7. Re: Help needed with past exam problem!! Referencing an array.
    morgalr Explorer
    Currently Being Moderated
    yeppers.
  • 8. Re: Help needed with past exam problem!! Referencing an array.
    baftos Expert
    Currently Being Moderated
    EJP wrote:
    Blimey. It's not that complicated. All he needs is a division and a modulus, and yes it can be done within the original loop structure. At root it's just an exercise in multi-radix conversion.
    How did you reach this conclusion? Because of the % operator in the original post?
    What is wrong with the simpistic approach below:
    for each drawer in the array {
        while amount owed >= drawer's sticker {
            print drawr's sticker and give the customer one item from the drawer
            amount owed = amount owed - drawer's sticker
       }
    }
  • 9. Re: Help needed with past exam problem!! Referencing an array.
    EJP Guru
    Currently Being Moderated
    How did you reach this conclusion?
    By knowing the answer.
    # 5 dollar bills = total/5
    total <- total mod 5
    etc for next lower denomination

    You don't need an inner loop.

    I must say I am really astonished by all these answers.
  • 10. Re: Help needed with past exam problem!! Referencing an array.
    baftos Expert
    Currently Being Moderated
    But I am a shepherd from the 5th century BC and I know nothing about / and %. My code:
    - works
    - it's easier to understand by other shepherds
    - has the same O (you will need to loop to print)
    - may be a bit faster (no division and modulus, which in the bronze age were slower than substractions)
    - it is shorter (definitely an advantage when you program on clay tablets).
  • 11. Re: Help needed with past exam problem!! Referencing an array.
    EJP Guru
    Currently Being Moderated
    But I am a shepherd from the 5th century BC
    The OP is a computer programmer, asking a computer programming question, on a forum dedicated to a programming language that contains the division and modulus operators.
    I know nothing about / and %.
    If I may say so, that was already obvious ;-)
    My code:
    - works
    Slowly.
    - it's easier to understand by other shepherds
    The target audience for the OP's question is a CS examiner. He is not going to pass your answer, unless he is a lot more lenient than I would be.
    - has the same O (you will need to loop to print)
    Complete, utter, and absolute rubbish. A solution with an inner loop cannot possibly have the same O as a solution without one. The correct answer is O(N) in the number of denominations. Yours is O(M**N) where M is the value of the total. You only have to print the number of each denomination in the outer loop, not in your inner loop. You don't appear to understand your own solution.
    - may be a bit faster (no division and modulus, which in the bronze age were slower than subtractions)
    Enough already. I'm getting tired of this irrelevance. We are in the C21. I have programmed multiple precision division and remainder operators into COBOL compilers and I can assure you they are a lot faster than subtractive methods.
    - it is shorter (definitely an advantage when you program on clay tablets).
    No, it is not shorter. More rubbish. One loop control statement, two braces, two assignment statements, and one print statement is shorter than two loop statements, four braces, two assignments, and one print statement.

    I take it back about being astonished. I am appalled.
  • 12. Re: Help needed with past exam problem!! Referencing an array.
    baftos Expert
    Currently Being Moderated
    You only have to print the number of each denomination in the outer loop, not in your inner loop.
    In the original example, the expected printout for 444 is not "2x200 2x20 2x2" (This would be O(N) indeed), but "200 200 20 20 2 2".
    This is not the number of each denomination, but rather the denomination value of each item.
    Correct me if I am wrong, but to prooduce "200 200 20 20 2 2", your code would look like:
    for each denomination {
        n = amount / denomination;
        // The following loop is not "one print statement"
        for (int i = 0; i < n; i++) {
            print denomination
        }
        amount = amount % denomination;
    }
    Edited by: baftos on Jan 15, 2013 10:34 PM

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points