C++ help

Discussion in 'C++' started by davy.zou@brentwood.bc.ca, Mar 3, 2007.

  1. Guest

    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.

    Thanks
    Davy
     
    , Mar 3, 2007
    #1
    1. Advertising

  2. Ian Collins Guest

    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.
    >

    Post an attempt and you will get some help. We don't do homework here,
    but we are happy to help with problems in your homework code.

    --
    Ian Collins.
     
    Ian Collins, Mar 3, 2007
    #2
    1. Advertising

  3. Guest

    On Mar 3, 5:55 pm, Ian Collins <> wrote:
    > 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.

    >
    > Post an attempt and you will get some help. We don't do homework here,
    > but we are happy to help with problems in your homework code.
    >
    > --
    > Ian Collins.


    I wasn't asking anyone to do my homework. I just need someone to point
    me in the right direction.
     
    , Mar 3, 2007
    #3
  4. Guest

    here is the code I first came up with, obviously it doesn't work,

    #include <iostream.h>
    #include <math.h>


    int centscalculation (int x, int y, int z);
    int computecent (int x, int y, int z);

    int centscalculation (int x, int y, int z) {
    double low=0, high=1, guessedcent, calculatedcent;
    const double epsilon=0.0001;

    for (;;) {
    guessedcent=(low+high)/2;
    if ((high-low)<(2*epsilon)) {
    return guessedcent;
    }

    centscalculation=computecent (x, y, z);

    if (calculatedcent==guessedcent) {
    return guessedcent;
    }

    if (calculatedcent>guessedcent) {
    low=guessedcent;
    } else {
    high=guessedcent;
    }
    }


    }

    int computecent (int x, int y, int z) {

    int a=2, b=7, c=9;


    return x*a+y*b+z*c;

    }



    void main () {

    int cents, a=2, b=7, c=9, x, y, z, ans; //a has value of 2, b has 7,
    c has 9

    while (true) {

    cout<<"Enter cents, 0 to terminate: "<<endl;
    cin>>cents;

    if (cents<0) {
    cout<<"Error."<<endl;
    }

    if (cents=0) {
    break;
    }


    ans=centscalculation (x, y, z);

    cout<<"answer is "<<ans<<endl;
    }


    }
     
    , Mar 3, 2007
    #4
  5. Gavin Deane Guest

    On 3 Mar, 23:02, wrote:
    > On Mar 3, 5:55 pm, Ian Collins <> wrote:
    > > 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.

    >
    > > Post an attempt and you will get some help. We don't do homework here,
    > > but we are happy to help with problems in your homework code.


    > I wasn't asking anyone to do my homework. I just need someone to point
    > me in the right direction.


    The FAQ is at http://www.parashift.com/c -faq-lite/ but it seems to
    be down at the moment. When it comes back to life, the FAQ you want is
    5.8. As Ian says, there are plenty of people here willing and able to
    help you, but none of them are mind-readers. Nobody can help you
    without knowing what your problem is. FAQ 5.8 explains how to get that
    help. In summary:

    Post the actual code you are having problems with, not a description
    of the code.
    Post *minimal* code - i.e. the *smallest possible* program that
    exhibits your problem.
    Post *compileable* code - i.e. copied and pasted *directly* from your
    editor into your message
    For code that does not compile and you don't understand why, copy and
    past the error messages directly from your compiler and make it clear
    which statement(s) the error refers to.
    For a program that compiles and runs but doesn't behave as you expect,
    post the inputs to the program, the actual outputs and your expected
    outputs.

    Without all this, nobody can be sure they are recreating exactly the
    situation you have and be sure they are answering the right question.

    HTH
    Gavin Deane
     
    Gavin Deane, Mar 3, 2007
    #5
  6. Guest

    On Mar 3, 6:23 pm, "Gavin Deane" <> wrote:
    > On 3 Mar, 23:02, wrote:
    >
    >
    >
    > > On Mar 3, 5:55 pm, Ian Collins <> wrote:
    > > > 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.

    >
    > > > Post an attempt and you will get some help. We don't do homework here,
    > > > but we are happy to help with problems in your homework code.

    > > I wasn't asking anyone to do my homework. I just need someone to point
    > > me in the right direction.

    >
    > The FAQ is athttp://www.parashift.com/c++-faq-lite/but it seems to
    > be down at the moment. When it comes back to life, the FAQ you want is
    > 5.8. As Ian says, there are plenty of people here willing and able to
    > help you, but none of them are mind-readers. Nobody can help you
    > without knowing what your problem is. FAQ 5.8 explains how to get that
    > help. In summary:
    >
    > Post the actual code you are having problems with, not a description
    > of the code.
    > Post *minimal* code - i.e. the *smallest possible* program that
    > exhibits your problem.
    > Post *compileable* code - i.e. copied and pasted *directly* from your
    > editor into your message
    > For code that does not compile and you don't understand why, copy and
    > past the error messages directly from your compiler and make it clear
    > which statement(s) the error refers to.
    > For a program that compiles and runs but doesn't behave as you expect,
    > post the inputs to the program, the actual outputs and your expected
    > outputs.
    >
    > Without all this, nobody can be sure they are recreating exactly the
    > situation you have and be sure they are answering the right question.
    >
    > HTH
    > Gavin Deane


    Thanks alot.
     
    , Mar 3, 2007
    #6
  7. osmium Guest

    <> wrote:

    > here is the code I first came up with, obviously it doesn't work,


    <snip>

    Think about dividing the available amount by 9, 7 and 2 in that order. I am
    not sure that is the right answer in all cases, but you can expand on it if
    needed. Look up the modulo operator (%). See the Wikipedia entry for
    modulo..
     
    osmium, Mar 3, 2007
    #7
  8. Kai-Uwe Bux Guest

    osmium wrote:

    > <> wrote:
    >
    >> here is the code I first came up with, obviously it doesn't work,

    >
    > <snip>
    >
    > Think about dividing the available amount by 9, 7 and 2 in that order. I
    > am not sure that is the right answer in all cases, but you can expand on
    > it if needed. [snip]


    I am not so sure that this looks like a promissing line of attack. There
    seems to be a little more to the problem. What is the answer for 10 and how
    do you find it through the division sequence? What about 35?


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Mar 4, 2007
    #8
  9. Guest

    On Mar 3, 6:43 pm, "osmium" <> wrote:
    > <> wrote:
    > > here is the code I first came up with, obviously it doesn't work,

    >
    > <snip>
    >
    > Think about dividing the available amount by 9, 7 and 2 in that order. I am
    > not sure that is the right answer in all cases, but you can expand on it if
    > needed. Look up the modulo operator (%). See the Wikipedia entry for
    > modulo..


    THANK YOU! dividing it by 9, 7, and 2! that is ingenious!
     
    , Mar 4, 2007
    #9
  10. bnonaj Guest

    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.
    >
    > Thanks
    > Davy
    >

    This is a variation of the bin packing problem. I've developed
    C++ code which can solve this problem for all solutions. It is
    also capable of handling target ranges as well, and multiples
    thereof. It's known to be a hard problem to create an efficient
    algorithm for.

    JB
     
    bnonaj, Mar 4, 2007
    #10
  11. Kai-Uwe Bux Guest

    wrote:

    > On Mar 3, 5:55 pm, Ian Collins <> wrote:
    >> 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.

    >>
    >> Post an attempt and you will get some help. We don't do homework here,
    >> but we are happy to help with problems in your homework code.
    >>
    >> --
    >> Ian Collins.

    >
    > I wasn't asking anyone to do my homework. I just need someone to point
    > me in the right direction.


    The following three observations might prove useful:

    a) You shall never need to use more than 6 stamps of 2c because you can
    trade 7 stamps of 2c for 2 stamps of 7c.

    b) You shall never need to use more than 8 stamps of 7c because you can
    trade 9 stamps of 7c for 7 stamps of 9c.

    c) You shall never need to use both 7c and 2c stamps because you can trade a
    pair of a 7c stamp and a 2c stamp for a single 9c stamp.


    This cuts down the complexity of the problem to a managable size.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Mar 4, 2007
    #11
  12. untitled Guest

    ok for number 19 for example, we can use 9+2+2+2+2+2 as effective in
    terms of cost, but also 9+9 is more effective in terms of number of
    stamps but we will waste 1 cent.

    which one we should use? i need to understand the problem first to
    solve it.
     
    untitled, Mar 4, 2007
    #12
  13. untitled Guest

    with number 3, 5 we will waste one cent, not an option, so can we
    tolerent loosing one cent at higher numbers like 22?
    so 22cents = 7+7+7 and waste one cent, instead of 9+9+2+2 more stamps
    but waste nothing.
     
    untitled, Mar 4, 2007
    #13
  14. Guest

    On Mar 3, 8:43 pm, "untitled" <> wrote:
    > ok for number 19 for example, we can use 9+2+2+2+2+2 as effective in
    > terms of cost, but also 9+9 is more effective in terms of number of
    > stamps but we will waste 1 cent.
    >
    > which one we should use? i need to understand the problem first to
    > solve it.


    You use the one with the least number of stamps. and if you run into a
    number like 35, you use 36cents as the ans. So you go one above the
    required number.
     
    , Mar 4, 2007
    #14
  15. Alan Johnson Guest

    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.
    >
    > Thanks
    > Davy
    >


    This is a classic dynamic programming problem. Let's start by laying
    some foundation you'll need to develop a solution.

    Let's say you already have a solution for N cents. For example, if
    N=23, the solution would be {9, 7, 7}. The first thing you should
    notice is that the solution has what is called an "optimal
    substructure". That is, if you took any part of the solution, it is
    optimal for smaller version of the problem. From the example N=23, we
    have subsolutions {9, 7} and {7, 7}, which are optimal for N=16 and
    N=14, respectively. It is trivial to prove by contradiction that the
    optimal substructure property holds for every solution. I'll leave that
    as an exercise for you, or you can just assume I'm right.

    So, the goal is to find the fewest number of stamps needed to make some
    value. Let's call that C(N). Examples: C(23) = 3, C(14) = 2, C(16) = 2.
    Because of optimal substructure, we know that the solution for C(N) is
    the same as some smaller problem plus one more stamp. That is, it is
    either 1+C(N-2), or 1+C(N-7), or 1+C(N-9). How do we decide which one?
    Easy, we compute them all, and use the smallest, since we are trying to
    minimize the number of stamps.

    Combine this with the fact that the solution for N=0 is obviously 0
    stamps, and you get the following recursion:

    C(N) = 0 if N = 0
    C(N) = min( 1+C(N-2), 1+C(N-7), 1+C(N-9) ) if N > 0


    Now all you need to do is write some C++ code that implements that
    recursion. (Hint: Make an array of size N, and make a loop that computes
    all the solutions from i=0 to i=N. At any particular i, you should
    already have the recursive values computed.)

    --
    Alan Johnson
     
    Alan Johnson, Mar 4, 2007
    #15
  16. untitled Guest

    ok here is my idea, it gives 1cent below the required number,

    x is the required number

    int sevens=x/7 //without the fractures
    remainder = x-(sevens*7)
    int twos= remainder/2 //without fractures
    uint nines=sevens-twos //without sign
    sevens=sevens-nines
    twos=twos-nines

    print nines,sevens,twos

    i'll write the one with one above the required number in few minutes...
     
    untitled, Mar 4, 2007
    #16
  17. untitled Guest

    then its an easy one,

    x is the requested number


    int sevens=x/7 //without the fractures
    remainder=x - (sevens*7)
    int twos= remainder/2 //without the fractures
    if (remainder - (twos*2)) =1 then twos++
    if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
    sevens=0
    if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
    =0

    just put it in c code
     
    untitled, Mar 4, 2007
    #17
  18. Alan Johnson Guest

    untitled wrote:
    > then its an easy one,
    >
    > x is the requested number
    >
    >
    > int sevens=x/7 //without the fractures
    > remainder=x - (sevens*7)
    > int twos= remainder/2 //without the fractures
    > if (remainder - (twos*2)) =1 then twos++
    > if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
    > sevens=0
    > if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
    > =0
    >
    > just put it in c code
    >


    Judging from the OP's description, this is an assignment for some sort
    of algorithms class. If that's the case, then coming up with a solution
    that actually depends on the number 2, 7, and 9 isn't particularly useful.

    How would you solve the problem if the denominations were D1, D2, and
    D3, rather than some specific three numbers? Or better yet, let's say
    you have denominations D1 through Dk.

    --
    Alan Johnson
     
    Alan Johnson, Mar 4, 2007
    #18
  19. Guest

    On Mar 3, 9:54 pm, Alan Johnson <> wrote:
    > untitled wrote:
    > > then its an easy one,

    >
    > > x is the requested number

    >
    > > int sevens=x/7 //without the fractures
    > > remainder=x - (sevens*7)
    > > int twos= remainder/2 //without the fractures
    > > if (remainder - (twos*2)) =1 then twos++
    > > if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
    > > sevens=0
    > > if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
    > > =0

    >
    > > just put it in c code

    >
    > Judging from the OP's description, this is an assignment for some sort
    > of algorithms class. If that's the case, then coming up with a solution
    > that actually depends on the number 2, 7, and 9 isn't particularly useful.
    >
    > How would you solve the problem if the denominations were D1, D2, and
    > D3, rather than some specific three numbers? Or better yet, let's say
    > you have denominations D1 through Dk.
    >
    > --
    > Alan Johnson


    It is not an algorithm class, it is purely C++, we get to algorithms
    next year, I think.
    But you have peaked my interest, would D1 through Dk be inputed by
    user? If it is inputed by user, then it shouldn't be too difficult to
    add the lines of codes to the program that will assign the user input
    to D1 through Dk.

    Davy
     
    , Mar 4, 2007
    #19
  20. Guest

    On Mar 3, 9:39 pm, "untitled" <> wrote:
    > then its an easy one,
    >
    > x is the requested number
    >
    > int sevens=x/7 //without the fractures
    > remainder=x - (sevens*7)
    > int twos= remainder/2 //without the fractures
    > if (remainder - (twos*2)) =1 then twos++
    > if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
    > sevens=0
    > if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
    > =0
    >
    > just put it in c code


    1 1int sevens=x/7 //without the
    fractures
    2 remainder=x - (sevens*7)
    3 int twos= remainder/2 //without the fractures
    4 if (remainder - (twos*2)) =1 then twos++
    5 if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
    sevens=0
    6 if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos,
    twos=0

    I don't get it. Several things in fact.

    First, I can't see what your program does. Since it doesn't have an
    output statement. But I will go on a tangent and guess that it is for
    comparing which ever way is the most effective way to distribute the
    stamps.

    Second, why not just use x%7 for line 2?

    Third, since you assigned that twos be reminder/2, then the act of
    mutiplying twos by 2 would result in the remainder from line2.
    Therefore, in line4, having remainder-remainder would result in 0.

    Fourth, in line4, what do you mean by twos++?

    Five, line 5 and 6 doesn't make much sense either.

    Six, what is if final out put?

    I really appreciate you trying to help, and I know that with the above
    list I sound like an ungrateful little brat. But I am grateful. I just
    don't get your programing. Please explain.

    Davy
     
    , Mar 4, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?dHJlbGxvdzQyMg==?=

    HELP! HELP! HELP! Opening Web Application Project Error

    =?Utf-8?B?dHJlbGxvdzQyMg==?=, Feb 20, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    805
    =?Utf-8?B?dHJlbGxvdzQyMg==?=
    Feb 20, 2004
  2. Harvey
    Replies:
    0
    Views:
    772
    Harvey
    Jul 16, 2004
  3. Harvey
    Replies:
    1
    Views:
    890
    Daniel
    Jul 16, 2004
  4. =?Utf-8?B?S2ltb24gSWZhbnRpZGlz?=

    HELP - HELP - HELP

    =?Utf-8?B?S2ltb24gSWZhbnRpZGlz?=, Mar 9, 2006, in forum: ASP .Net
    Replies:
    4
    Views:
    716
    Eliyahu Goldin
    Mar 9, 2006
  5. Buster

    Help, Help, Help

    Buster, Oct 4, 2003, in forum: Java
    Replies:
    3
    Views:
    495
    Saager
    Oct 30, 2003
Loading...

Share This Page