Tower of Hanoi - Can it be optimized some how ?

[Sonia]

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);
}
}

 

[Jean-François GAZET]

If it can help, i wrote this game in PHP :
http://www.webjeff.org/jeux/index.htm

I can send you the source code if you want.

 

[Heinz Ozwirk]

: 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

 

[Sonia]

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