4 replies to this topic

[Melchoire]

Right, so I'm just trying to make a function that lists out the steps for solving the Towers of Hanoi. Here's the code I got for the function:

void towers(int N, int presentPeg, int toPeg, int tempPeg)
{
	if(N > 0)
	{
		towers(N-1, presentPeg, toPeg, tempPeg);
		cout << "Move disc from Peg#" << presentPeg << " to Peg#" << toPeg << endl;
		towers(N-1, tempPeg, presentPeg, toPeg);
	}
}

The out for 3 discs is:

Move disc from Peg#1 to Peg#3
Move disc from Peg#1 to Peg#3
Move disc from Peg#2 to Peg#1
Move disc from Peg#1 to Peg#3
Move disc from Peg#2 to Peg#1
Move disc from Peg#2 to Peg#1
Move disc from Peg#3 to Peg#2

Which is obviously wrong. I'm calling the function like so: "towers(n, 1, 3, 2);" where n=3. Can anyone spot a problem?

[jcrdude]

Seems awful awkward to call the function from within itself.... let me see what I can think up...

Ok... first off, you need to determine your first move. With that in mind, it should be handy to come up with a function for just that purpose.

int determineFirstMove (n, toPeg, tempPeg)
{
 if n%2 == 0
 {
 	return tempPeg
 }
 else
 {
 	return toPeg
 }
}

Edited by jcrboy, 21 November 2009 - 05:39 PM.

[Melchoire]

Seems awful awkward to call the function from within itself.... let me see what I can think up...

Ok... first off, you need to determine your first move. With that in mind, it should be handy to come up with a function for just that purpose.

int determineFirstMove (n, toPeg, tempPeg)
{
 if n%2 == 0
 {
 	return tempPeg
 }
 else
 {
 	return toPeg
 }
}

That's what I meant by recursion I think it's the easiest way of solving the problem.

[Hydrogen]

That's what I meant by recursion I think it's the easiest way of solving the problem.

It's the only way to solve this problem . You can't do it in the general case without recursion . I haven't looked at the code since I'm a bit busy at the moment but my advice is to solve it for three pegs and then abstract that to the general case. The three pegs are your base case and everything will follow after that easily with recursion . Sorry, I know this post isn't very helpful .

[Melchoire]

It's the only way to solve this problem . You can't do it in the general case without recursion . I haven't looked at the code since I'm a bit busy at the moment but my advice is to solve it for three pegs and then abstract that to the general case. The three pegs are your base case and everything will follow after that easily with recursion . Sorry, I know this post isn't very helpful .

Never mind, got it working. But that's pretty much what I was doing. I just had some a variables in the wrong place. =P

revised:

void towers(int N, int presentPeg, int tempPeg, int toPeg);//new header
...
towers(n, 1, 2, 3);

Edited by Melchoire, 21 November 2009 - 06:41 PM.