Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
Programming

Journal Short Circuit's Journal: [challenge] Denominations 9

Journal by Short Circuit

Programming challenge: What's the most efficient way to take a possibly fractional currency amount, and present using as few entities of physical currency as possible. (i.e. a dollar is represented as a dollar bill. $0.99 would be a half-dollar, a quarter, two dimes, and four pennies.)

Here's a semicomplete example of what I'm talking about. (Semicomplete because it doesn't deal with notes larger than $1, and it doesn't consider half-dollars.)

#include <iostream>
 
int main () {
  float total = 0.0f; // In cents
  cout << "Please enter an amount of money, in USD: ";
  cin >> total;
 
  int pennies = (unsigned int) total * 100;
 
  int dollars = (int) (total / 100);
  pennies = pennies % 100;
 
  int quarters = (int) (pennies / 25);
  pennies = pennies % 25;
 
  int dimes = (int) (pennies / 10);
  pennies = pennies % 10;
 
  int nickels = (int) (pennies / 5);
  pennies = pennies % 5;
 
  cout << "Dollars: " << dollars << endl
      << "Quarters: " << quarters << endl
      << "Dimes: " << dimes << endl
      << "Nickels: " << nickels << endl
      << "Pennies: " << pennies << endl;
 
  return 0;
}

I could do it in Perl in fewer lines (around 12, I think. Less, if I left mandated one line per statement. And it would support an arbitrary variety of denominations.

So...I have to assume there are more faster, more proper, and/or shorter ways to do this. How would you go about it? (No restriction on language.)

This discussion has been archived. No new comments can be posted.

[challenge] Denominations More

[challenge] Denominations

Comments Filter:

  • So.. (Score:2)

    by ryanr ( 30917 ) *
    Were you wanting to play perl golf, then?
    • Not really...I'm more interested in better algorithms than smaller code.

      Here's my Perl implementation:

      @denominations = ("Dollars", "Kennedy", "Quarters", "Dimes", "Nickels", "Pennies");
      @values = (100, 50, 25, 10, 5, 1);
      print "Please enter an amount of money in USD:";
      $total = <STDIN>;
      $smallest = $total * 100;

      for ($counter = 0; $counter < (scalar @denominations - 1); $counter++) {
      $count[$counter] = $smallest / $values[$counter];
      $smallest %= $values[$counter];
      }

      for ($c

      • I am reasonably sure that the only algorithm is: Give largest denomination available until you can't, repeat with next denomination until change made.

        #!/usr/bin/perl

        use strict;
        use warnings;

        my @money = ( Dollar => 100,
        Half => 50,
        Quarter => 25,
        Dime => 10,
        Nickel => 5,
        Penny => 1 );

        print "Enter an amount in cents: ";
        chomp( my $amount = <STDIN>);

        while (my ($coin, $value) = splice(@money,0,2)) {
        while ($amount >= $value) {
        print "$coin\n";
        $amount-= $val

        • Hrm ... why did /. smash all the whitespace inside an <ecode> section?
        • Hm. I see I left a few things out.

          I dropped

          #!/usr/bin/perl -w"

          because the #! line is technically a shell command, not a Perl command.

          I dropped

          use strict;

          because I wanted to save on lines, because I was somewhat space conscious when I wrote it. (I always use it in my projects! Really!)

          I'd say I dropped

          use warnings;

          for the same reasons, but I just plain forgot.

          I used plain old arrays instead of hashes because I wasn't sure what order the keys would come out if I used the keys keyword.

          I'm not sure how y

          • No worries.

            For a moment, I had considered using a hash, and elected not to for precisely the reason you didn't. An array of hashrefs would have been good, too

            As to the outer loop.... splice (@array,0,$n) is a moderately common idiom that is worth knowing. Shift $n items off of @array. So while I got two items (a coin name and its cent value) off of the array of coins do the inner loop. perldoc -f splice for more examples of how to use it.

            #!/usr/bin/perl -w is just a pre-y2k way of saying use warnings

        • I do realize I'm jumping around in the thread a lot (in time) but I am endeavoring to keep my responses attached to the most relevant posting.

          I also just realized that my simple-minded algorithm above only works for certain sets of coins (it happens to work for the three nations whose coinage I have commited to memory).

          Imagine I want to optimally give you 30 fizzos (the national currency of Fizzland), who have three coins, a 25-fizzo, a 15-fizzo and a 1-fizzo. The least number of coins I can give you is

      • By the way:

        use strict;

        Always.

        for my $counter ( 0 .. $#denominations)

        is a much better Perl idiom for getting the index to an array, but any time you are indexing an array should be a waving red flag that your data structure is ... highly suboptimum.

        And finally, your code does not produce correct output

        I do realize that booking time on the supercomputer center to test 13 line perl programs takes months of preplanning, so you are clearly forgiven for failing to test before posting

        Smile. It

      • Re: (Score:2)

        by ryanr ( 30917 ) *
        Does your algorithm work?

        What happens when you do 75 cents?

Slashdot Top Deals

One man's "magic" is another man's engineering. "Supernatural" is a null word. -- Robert Heinlein

Close