Towers of Hanoi

Discussion in 'C++' started by Constant, Sep 17, 2003.

  1. Constant

    Constant Guest

    I need a programe that will deal with the solving of the problem ..i
    have 3 pegs A, B, C...and I want to move the disk A to disk C using B
    as auxiliary.At the end all disk should be at peg C in the same order
    as in the beginning.
    I do not know how to solve this problem because I have only basic
    skill in C++

    Please help.

    Thanks for your time.
     
    Constant, Sep 17, 2003
    #1
    1. Advertisements

  2. Constant

    Alexandros Guest

    Constant escribi├│:

    Here you are a program wich solves the problem:

    #include <iostream>
    using namespace std;

    void hanoi (int nDisks, int pegA, int pegB, int pegC)
    {
    if (n>0) {
    hanoi (nDisks - 1, pegA, pegC, pegB);

    cout << "Move disk from peg " << pegA << " to peg " << pegC << endl;

    hanoi( nDisks-1, pegB, pegA, pegC);
    }
    }

    int main ()
    {
    int n;
    cout << "Input number of disks: ";
    cin >> n;

    hanoi (n, 1, 2, 3);

    return 0;
    }
     
    Alexandros, Sep 17, 2003
    #2
    1. Advertisements

  3. Please do not solve other peoples homework.
    Give him some hints, try to make him thinking about
    the problem, but do not post a program he can turn in
    without actually having mastered the problem by himself.

    Hanoi is often used to check if a student has grasped
    the concept of recursion. He needs to build up a mental
    model on how recursion works in order to solve it with
    recursion:
    a) What makes the problem complicated?
    b) What parameter can be made simpler, such that
    finally this parameter reaches 0 or 1 or any other
    trivial case.
    c) What is the trivial case, how can it be solved?
    d) How can I use a simpler solution to find the solution
    for the more complex problem.

    By providing him a complete workable solution,
    you have defeated that intention.

    Thank you.

    PS (for the OP):
    a) the number of disks. Obviously, if no disk must be moved
    the problem is so simple, that even a 2 year old child can solve
    it: do nothing.
    b) again, the number of disks. Moving n-1 disks is easier then
    moving n disks.
    c) Having to move 0 disks. No action is required then.
    d) To move n disks from a StartPad to GoalPad with the help
    of a ParkingPad:
    * move n-1 disks from StartPad to ParkingPad, in order to free
    the n-th disk for movement. You can use the GoalPad as the parking pad.
    * move the n-th disk from StartPad to GoalPad
    * move the n-1 disks you have parked at ParkingPad, from ParkingPad
    to GoalPad, this time you can use the StartPad as the parking pad.

    moving n-1 disks is simpler then moving n disks. Thus the above
    uses the solution of simpler problems to solve the problem for n.
     
    Karl Heinz Buchegger, Sep 17, 2003
    #3
  4. Constant

    Mike Wahler Guest

    This is not a 'program supply' group. It's a group
    for discussing the C++ language.
    No C++ knowledge or computer knowledge at all is required
    to solve this problem. It can (and imo should) first be
    done with paper and pencil. Once you've worked out and
    tested (again on paper) your algorithm, only then is is
    time to translate it into a programming language.

    WHen you have some code representing your best attempt,
    but are still stuck or confused, then by all means post it here
    and ask specific questions. That's how to get quality assistance
    here.

    -Mike
     
    Mike Wahler, Sep 17, 2003
    #4
  5. Constant

    Gavin Deane Guest

    Do you know how to solve the problem in English or your native
    language? Before you start to write any C++ you'll need to be able to
    fully describe the algorithm in natural language. It's not very
    complicated but you'll need to be precise. Once you've done that,
    start translating it into C++.

    Or are you at the coding stage already? If so, post compileable code
    that demonstrates your problem. Include compiler messages and/or
    program output that you don't understand and explain what you expect
    to happen. Then people will be able to help.

    Good luck.
    GJD
     
    Gavin Deane, Sep 17, 2003
    #5
  6. Constant

    Mike Wahler Guest

    Then stop spinning around. :)
    They would be e.g. names and values of variables at
    given points of execution.

    Data and control flow.
    Some can do that easily, others have trouble.
    This 'vision' can be made concrete with a *pad* of paper,
    on on top of the other. Each succeeding 'page' would
    represent a level of recursion.
    Yup.

    -Mike
     
    Mike Wahler, Sep 17, 2003
    #6
  7. Constant

    osmium Guest

    The notion of making some marks on paper for a recursive solution makes me
    slightly dizzy. I can't imagine what those marks would be or what they
    would represent. IMO a recursive problem must be held and solved, to some
    degree, in the head. A *vision*, if you will. The next step: a computer
    program or at least pseudocode. Your mileage obviously varies.
     
    osmium, Sep 17, 2003
    #7
  8. Constant

    Jack Klein Guest

    #include <check_calendar>

    Yep, still September!


    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c++-faq-lite/
    alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq
     
    Jack Klein, Sep 18, 2003
    #8
  9. Constant

    Noah Roberts Guest

    The answer to this question can be found in the introduction to Concrete
    Mathematics by Knuth and friends. There you will find a recursive
    algorithm which performs the task you want, is proven, and is analyzed
    for N so that we can finally answer the question about how long it will
    take those monks to finish 1000 planks and we can all start over.

    NR
     
    Noah Roberts, Sep 18, 2003
    #9
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.