Re: C++ help

From:

Kai-Uwe Bux <jkherciueh@gmx.net>

Newsgroups:

comp.lang.c++

Date:

Tue, 06 Mar 2007 22:13:15 -0500

Message-ID:

<eslakf$f09$1@murdoch.acc.Virginia.EDU>

davy.zou@brentwood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

Any help would be greatly appreciated.

I feel this has become somewhat of a contest. So, here is my entry (sorry, I
couldn't resist).

Beware that this will not do you any good for your assignment because the
algorithm (not the code) is way too cryptic (it uses two magic numbers and
cuts some corners). In fact, the proof of correctness has a few rather
subtle points. Elsethread, I have posted more helpful comments already.
Have fun figuring this one out:

#include <iostream>
#include <ostream>
#include <iomanip>
#include <utility>
#include <cassert>

struct solution {
  unsigned no_9;
  unsigned no_7;
  unsigned no_2;
};

std::ostream & operator<< ( std::ostream & ostr,
                            solution const & sol ) {
  ostr << std::setw(2)
       << sol.no_9 << " x 9c + "
       << sol.no_7 << " x 7c + "
       << sol.no_2 << " x 2c";
  return ( ostr );
}

unsigned total ( solution sol ) {
  return ( sol.no_9 + sol.no_7 + sol.no_2 );
}

int main ( void ) {
  for ( unsigned money = 6; money < 200; ++money ) {
    std::cout << std::setw(4) << money << "c";
    solution try_a;
    solution try_b;
    // begin{white_magic}
    try_a.no_2 = 0;
    try_a.no_7 = ( 4 * ( money % 9 ) ) % 9;
    try_a.no_9 = ( money - 7*try_a.no_7 ) / 9;
    try_b.no_2 = ( 5 * ( money % 9 ) ) % 9;
    try_b.no_7 = 0;
    try_b.no_9 = ( money - 2*try_b.no_2 ) / 9;
    // end{white_magic}
    // begin{black_magic}
    // The following asserts do fail sometimes.
    // However, this does not affect correctness of the output.
    // assert( money == 9 * try_a.no_9 + 7 * try_a.no_7 + 2 * try_a.no_2 );
    // assert( money == 9 * try_b.no_9 + 7 * try_b.no_7 + 2 * try_b.no_2 );
    // end{black_magic}
    if ( total( try_a ) <= total( try_b ) ) {
      std::cout << " = " << try_a;
    }
    if ( total( try_b ) <= total( try_a )
         &&
         try_b.no_9 != try_a.no_9 ) {
      std::cout << " = " << try_b;
    }
    std::cout << '\n';
  }
}

Of course, I do not endorse this style of programming. It just seemed to be
too much fun to miss out on this one. (On the plus side, I would think that
it should be very hard to implement a solution that is algorithmically more
efficient.)

Best

Kai-Uwe Bux