Announcement

Collapse
No announcement yet.

Math Contest for Cashiers!

Collapse
This topic is closed.
X
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Math Contest for Cashiers!

    Here's a math contest for cashiers (well anyone can enter).

    The most common algorithm (or series of computational steps) to making change is known as the "greedy algorithm." You start with the highest denomination coin (the quarter), take out as many as you need before it gets to be too much, move onto the next lowest (dime), rinse, repeat until you get to pennies.

    For example, using the greedy algorithm, giving 62 cents back in change will equal:

    2 quarters + 1 dime + 0 nickels + 2 pennies

    Using the greedy algorithm will yield the lowest number of coins needed for any transaction.

    However, as any cashier will tell you, using the greedy algorithm will have you hemorrhaging quarters and will leave your roll of nickels practically untouched.

    So let's see who can come up with a new change-making algorithm that satisfies the following requirement:

    Per 10 transactions, the cashier is left with as close to no coins as possible.

    The algorithm that yields a result closest to 0 total coins (using a standard set of randomly generated numbers) will be the winner.

    Make the following assumptions:

    1) Half dollar coins and dollar coins do not exist.
    2) The decimal price of each order (.01 –.99) is random but never .00.
    3) (For the sake of simplicity) no coins are added to the cash drawer (by customers.)
    4) A cash drawer contains 1 roll of quarters (x40), 1 roll of dimes (x50), 1 roll of nickels (x40), and 1 roll of pennies (x50).

    There is no one "right" answer. I don't even have an algorithm formed yet, so I'll try to think of one myself.

    Remember that an algorithm is (simply put) a series of steps.
    Last edited by dbblsanta; 08-18-2009, 01:16 AM.

  • #2
    Do I have to give back proper change?

    First customer gets 50 pennies, or however many are necessary if the change is under 50 cents, plus however many nickels till his change is satisfied, giving him the extra if I cannot make the pennies work out evenly.

    Second customer gets all his change back in nickels, then dimes, till his is satisfied, giving him extra if necessary.

    #3 gets nickel, and dimes till his change is overed (the C is missing on purpose)

    #4, 5, 6, 7, etc. get dimes till dimes are gone, then quarters

    #nexts get quarters till gone

    all the rest get paper change, up to 99 cents over the actual change that they should get.

    What, this isn't what you meant? I have to give back PROPER change? But you didn't specify! awww, that's no fun!

    ETA: see my earlier post in this forum to see where my brain is right now!
    Last edited by Primer; 08-17-2009, 11:26 PM. Reason: see my earlier post!!
    Everything will be ok in the end. If it's not ok, it's not the end.

    Comment


    • #3
      You have to give back exact change. So if the customer is owed 57 cents you can't round it to 60 cents or down to 55 cents.

      (Also note that I changed it from 100 transactions to 10 transactions. It'd be too time-consuming to test these algorithms to 100 transactions.)

      Using this algorithm it looks like you'd run out of pennies way too soon and have too much of the other coins left over. If you have no pennies left before the test ends, the algorithm fails. So it all depends on if you get really really lucky and the list of random numbers works out in your favor.

      But at least we have one entry!

      So let me summarize:

      1A) If change ≤ .50, customer gets change in pennies.
      1B) If change > .50, customer gets change in pennies with least amount of nickels necessary.

      Steps 1A and 1B are repeated until pennies are expended.

      2) Customer gets change back entirely in nickels.

      Step 2 is repeated until nickels are expended.

      3) Customer gets change back entirely in dimes.

      Step 3 is repeated until dimes are expended.

      4) Customer gets change back entirely in quarters.

      Step 4 is repeated until quarters are expended.
      Last edited by dbblsanta; 08-18-2009, 12:45 AM.

      Comment


      • #4
        I forgot to add the last step: the cashier gets fired for incompetence!
        Everything will be ok in the end. If it's not ok, it's not the end.

        Comment


        • #5
          OK, here's my entry:

          1A) If change is < .10, use the greedy algorithm.

          1B) If change is > .10, give back change entirely in dimes and pennies and continue to step 2.

          2) Convert the fifth dime counted into two nickels. (Note that this "dime counting" is continuous amongst customers. If Customer A gets dimes #1, 2, and 3, then Customer B's dimes start with #4.)

          3) Leave the fifth dime counted after that as a dime.

          4) Leave the fifth dime counted after Step 3 as a dime.

          5A) If change is ≥ .25, convert the fifth and sixth dime after Step 3 into a quarter with a nickel. If there is no nickel in customer's change, convert the seventh dime into two nickels, then proceed to convert the fifth and sixth dime into a quarter with one nickel.

          5B) If the change is < .25, then leave the fifth dime counted after Step 3 as a dime. As soon as possible, convert two dimes and a nickel into a quarter, or three dimes into a quarter and nickel.

          6) Repeat steps 1 through 5. If step 5B is followed, then follow Step 3* instead of Step 3.

          3*) Convert the fifth and sixth dime after Step 2 into a quarter with a nickel. If there is no nickel in customer's change, convert the seventh dime into two nickels, then proceed to convert the fifth and sixth dime into a quarter with one nickel.

          7) When dimes are expended, revert to greedy algorithm. When quarters are expended, do not convert dimes into quarters. When nickels are expended, do not convert dimes into nickels. When nickels are expended, use pennies when change is less than 10 cents.


          ---------

          OK, now let me explain my reasoning.

          We need to use the greedy algorithm for change less than 10 cents, otherwise we'd run out of pennies too soon. (Giving out 9 cents in pennies too often would ruin us.)

          For the rest of the algorithm, we can ignore the pennies for the most part. They are the "essential" coin because they are the lowest denomination. You can't make 67 cents, for example, without using pennies. Therefore they are used only when they must be used.

          The algorithm is based on dimes being used as a base. There are more dimes per roll than any other coin (50 dimes per roll). For every 5 dimes there are 4 nickels, and for every 5 dimes there are 4 quarters (because there are 40 coins in a nickel or quarter roll).

          So we have a 5:4 ratio of dimes:nickels and 5:4 of dimes:quarters. We need to get that to 4:4 (or 1:1).

          So imagine 5 dimes next to each other: 0 0 0 0 0

          We pluck that fifth dime and turn it into 2 nickels:

          0 0 0 0 / ( ) ( ) ( ) ( ) ( ) ( )

          We now have 4 dimes and 6 nickels. Keep in mind that one nickel gets used up to make a quarter in step 4, and the dimes in steps 3 and 4 are conserved as dimes (to offset the 2 dimes taken to make the quarter). Thus the ratio of dimes:nickels wobbles from 5:4 to 4:6 to 5:4 to 3:5. This averages out to a proportion of about .9917:1. That's pretty close to 1:1.

          If the ratio of dimes:quarters is 5:4 and we take out two of those dimes to make one quarter, we get a ratio of 3:5 on every 20th dime. So that means the ratio of dimes:quarters goes from 5:4 to 4:4 (remember we took out one dime for nickels) to 5:4 to 5:4 to 3:5. This averages out to a proportion of 1.07. This is also close to 1:1.
          Last edited by dbblsanta; 08-18-2009, 01:15 AM.

          Comment


          • #6
            Here's one more I thought of that is actually practical to implement:


            1) Use greedy algorithm until 1/2 the quarters are expended.
            2) Use greedy algorithm but without using quarters until 1/2 the dimes are expended.
            3) Use greedy algorithm but without using dimes (but you can use quarters) until 1/2 the nickels are expended or 1/2 of remaining quarters are expended.
            4) Repeat starting with step 2.

            Comment


            • #7
              I use an entirely different algorithm to make change. I count up. Example, total is xx.43. Starting with pennies, count UP to the next multiple of 5. Then move to the next coin, in this case nickles since the the count is now at 45. One nickle brings it to 50. 2 quarters finishes the count.

              So, if I had a total of xx.64, the count would be one penny, one dime, one quarter (65, 75, dollar).

              Using this method, you never give anyone back more than 4 of any one type of coin.

              As for your test, sorry, I'm not really awake enough yet to do that.
              You're only delaying the inevitable, you run at your own expense. The repo man gets paid to chase you. ~Argabarga

              Comment


              • #8
                Quoth Kittish View Post
                I use an entirely different algorithm to make change. I count up.
                That's the greedy algorithm, you're just thinking about it the opposite way.

                Ex: The customer who's total is xx.43, you'd give him back 2 pennies, 1 nickle, 2 quarters (.44, .45, .50, .75, $1), I'd give him back 2 quarters, 1 nickle, and 2 pennies (.25, .50, .55, .57) either way he's getting 57cents back in the fewest coins possible, the only difference is what's going on in the cashier's head.
                The High Priest is an Illusion!

                Comment

                Working...
                X