Tower of Hanoi - Can it be optimized some how ?

Discussion in 'C++' started by Sonia, Aug 31, 2003.

  1. Sonia

    Sonia Guest

    Hi,
    I have written this code for the Tower of Hanoi problem. I was just
    wondering if there is any way of optimizing this code ?
    It's a failry simple code, but I thought that maybe somehow it could be
    improved. Please let me know. Thanks


    #include <iostream>

    using std::cout;
    using std::cin;
    using std::endl;


    void move(int, int, int, int);

    int count = 0;

    int main() {

    int numToBeMoved;
    int peg1=1; // peg on which the disks are initially
    int peg2=2; // peg to which the disks are to be moved
    int peg3=3; // temporary holding area

    cout<<"Enter number of disks to be moved: ";
    cin>>numToBeMoved;

    move(numToBeMoved, peg1, peg2, peg3);

    cout<<"Number of moves: "<<count<<endl;
    return 0;
    }

    void move (int n, int p1, int p2, int p3)
    {

    if(n>=1) {
    move(n-1, p1, p3, p2);
    count++;
    cout<<"move from "<<p1<< " to " <<p2<<endl;
    move(n-1, p3,p2,p1);
    }
    }
     
    Sonia, Aug 31, 2003
    #1
    1. Advertisements

  2. Jean-François GAZET, Aug 31, 2003
    #2
    1. Advertisements

  3. Sonia

    Heinz Ozwirk Guest

    : Hi,
    : I have written this code for the Tower of Hanoi problem. I was just
    : wondering if there is any way of optimizing this code ?
    : It's a failry simple code, but I thought that maybe somehow it could be
    : improved. Please let me know. Thanks

    There's not much to imporve on the algotizhem itself, but I have some suggestions on your source code. They may not seem to be very usefull in small programs like this, but when you have to work on a large project the hopefully will be usefull...

    : #include <iostream>
    :
    : using std::cout;
    : using std::cin;
    : using std::endl;
    :
    : void move(int, int, int, int);

    Even though it is allowed by the language, don't omit parameter names from prototypes. When you later see the prototype only, you will probably not remember which of the four ints has which meaning. (Not to mention others reading your code.)

    void move(int numberOfDisks, int sourcePeg, int targetPeg, int intermediatePeg);

    Reading a prototype like this you will not have to look for more documentation. Most of the information you need is already there.

    : int count = 0;

    Avoid global variables whenever possible. If you have to use one, give it a descriptive name that is not likely to be used for anything else. count is too common a name to be used for a global variable. Change it to something like numberOfMovesMade, or even better, change move() to return the number of moves made.

    : int main() {
    :
    : int numToBeMoved;
    : int peg1=1; // peg on which the disks are initially
    : int peg2=2; // peg to which the disks are to be moved
    : int peg3=3; // temporary holding area

    peg1, peg2 and peg3 never change, so they should be const. Also, these names are not really descriptive. You even have to write comments to describe their meanings. Whenever you have to do that, try to find a better name, for example

    const int initialPeg = 1;
    const int targetPeg = 2;
    const int holdingArea = 3;

    : cout<<"Enter number of disks to be moved: ";
    : cin>>numToBeMoved;
    :
    : move(numToBeMoved, peg1, peg2, peg3);
    :
    : cout<<"Number of moves: "<<count<<endl;
    : return 0;
    : }
    :
    : void move (int n, int p1, int p2, int p3)

    Again, names like p1, p2 and p3 are not very helpfull in most cases. If you don't like to write the long names from the prototype, use short but still descriptive names like from, to and hold.

    : {
    :
    : if(n>=1) {

    You might improve the algorithm, if you replaces the condition by n>1 and add a special case for n==1. That will save about have the calls to move(), namely all those calls where n==0 and move() does nothing at all. It might also be an improvement to compute n-1 once, but a good compiler should be able to optimize that itself.

    : move(n-1, p1, p3, p2);
    : count++;
    : cout<<"move from "<<p1<< " to " <<p2<<endl;
    : move(n-1, p3,p2,p1);
    : }
    : }

    Finally the move function with all the suggested changes:

    int move(int n, int from, int to, int hold)
    {
    int count = 1;
    if (n > 1)
    {
    count += move(n - 1, from, hold, to);
    cout << "move from " << from << " to " << to << endl;
    count += move(n - 1, hold, to, from);
    }
    else
    {
    cout << "move from " << from << " to " << to << endl;
    }
    return count;
    }

    Regards
    Heinz
     
    Heinz Ozwirk, Sep 1, 2003
    #3
  4. Sonia

    Sonia Guest

    : Hi,
    : I have written this code for the Tower of Hanoi problem. I was just
    : wondering if there is any way of optimizing this code ?
    : It's a failry simple code, but I thought that maybe somehow it could be
    : improved. Please let me know. Thanks

    There's not much to imporve on the algotizhem itself, but I have some
    suggestions on your source code. They may not seem to be very usefull in
    small programs like this, but when you have to work on a large project the
    hopefully will be usefull...

    : #include <iostream>
    :
    : using std::cout;
    : using std::cin;
    : using std::endl;
    :
    : void move(int, int, int, int);

    Even though it is allowed by the language, don't omit parameter names from
    prototypes. When you later see the prototype only, you will probably not
    remember which of the four ints has which meaning. (Not to mention others
    reading your code.)

    void move(int numberOfDisks, int sourcePeg, int targetPeg, int
    intermediatePeg);

    Reading a prototype like this you will not have to look for more
    documentation. Most of the information you need is already there.

    : int count = 0;

    Avoid global variables whenever possible. If you have to use one, give it a
    descriptive name that is not likely to be used for anything else. count is
    too common a name to be used for a global variable. Change it to something
    like numberOfMovesMade, or even better, change move() to return the number
    of moves made.

    : int main() {
    :
    : int numToBeMoved;
    : int peg1=1; // peg on which the disks are initially
    : int peg2=2; // peg to which the disks are to be moved
    : int peg3=3; // temporary holding area

    peg1, peg2 and peg3 never change, so they should be const. Also, these names
    are not really descriptive. You even have to write comments to describe
    their meanings. Whenever you have to do that, try to find a better name, for
    example

    const int initialPeg = 1;
    const int targetPeg = 2;
    const int holdingArea = 3;

    : cout<<"Enter number of disks to be moved: ";
    : cin>>numToBeMoved;
    :
    : move(numToBeMoved, peg1, peg2, peg3);
    :
    : cout<<"Number of moves: "<<count<<endl;
    : return 0;
    : }
    :
    : void move (int n, int p1, int p2, int p3)

    Again, names like p1, p2 and p3 are not very helpfull in most cases. If you
    don't like to write the long names from the prototype, use short but still
    descriptive names like from, to and hold.

    : {
    :
    : if(n>=1) {

    You might improve the algorithm, if you replaces the condition by n>1 and
    add a special case for n==1. That will save about have the calls to move(),
    namely all those calls where n==0 and move() does nothing at all. It might
    also be an improvement to compute n-1 once, but a good compiler should be
    able to optimize that itself.

    : move(n-1, p1, p3, p2);
    : count++;
    : cout<<"move from "<<p1<< " to " <<p2<<endl;
    : move(n-1, p3,p2,p1);
    : }
    : }

    Finally the move function with all the suggested changes:

    int move(int n, int from, int to, int hold)
    {
    int count = 1;
    if (n > 1)
    {
    count += move(n - 1, from, hold, to);
    cout << "move from " << from << " to " << to << endl;
    count += move(n - 1, hold, to, from);
    }
    else
    {
    cout << "move from " << from << " to " << to << endl;
    }
    return count;
    }

    Regards
    Heinz

    Thank Heinz, Helped a lot.
     
    Sonia, Sep 1, 2003
    #4
    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.