Rhyous

September 22, 2009

The Tower of Hanoi as an example of using a recursive functions in C++

Filed under: Uncategorized — J. Abram barneck @ 4:21 am

I am not going to explain the Tower of Hanoi here. I assume if you are reading this you know what you are looking for. Otherwise, read this:
http://en.wikipedia.org/wiki/Tower_of_Hanoi

Main.cpp

#include <iostream>
#include "TowerOfHanoi.h"

int main()
{
	TowerOfHanoi *toh = new TowerOfHanoi(true);
	std::cout << toh->toString();
	toh->solve();
	system("pause");
}

TowerOfHanoi.h

#include <iostream>
#include <string>
#include <sstream>
#include <string>

#define leftPeg 1
#define middlePeg 2
#define rightPeg 3

class TowerOfHanoi
{
	public:
		// Constructors
		TowerOfHanoi(bool inPromptUser);
		TowerOfHanoi(int inNumberOfRings);

		// Destructor
		~TowerOfHanoi();

		// Other functions
		void solve();

		// Standard functions
		std::string toString();
		bool equals(TowerOfHanoi inTowerOfHanoi);

	private:
		void initializeClass(int inNumberOfRings);
		void runRecursiveAlgorithm(int inNumberOfRings, int mPegOriginallyHoldingRing, int inTemporaryPeg, int inDestinationPeg);
		std::string intToString(int i);
		int power(int inInteger, int inExponent);
		std::string getTabs();

		int mNumberOfRings;
		int mPegOriginallyHoldingRing;
		int mDestinationPeg;
		int mTemporyPeg;
		int mNumberOfStepsToSolve;
		int mStepCounter;
};

TowerOfHanoi.cpp

#include "TowerOfHanoi.h"
#include <iostream>
#include <string>
// Constructors
TowerOfHanoi::TowerOfHanoi(bool inPromptUser)
{
	int tmpNumberOfRings;
	std::cout << std::endl << "How many rings? [1 - 10] " << std::endl;
	std::cin >> tmpNumberOfRings;
	initializeClass(tmpNumberOfRings);
}

TowerOfHanoi::TowerOfHanoi(int inNumberOfRings)
{
	initializeClass(inNumberOfRings);
}

// Destructor
TowerOfHanoi::~TowerOfHanoi()
{
}

// Other functions
void TowerOfHanoi::solve()
{
	mStepCounter = 0;
	runRecursiveAlgorithm(mNumberOfRings, mPegOriginallyHoldingRing, mTemporyPeg, mDestinationPeg);
}

// Private functions
void TowerOfHanoi::initializeClass(int inNumberOfRings)
{
	mNumberOfRings = inNumberOfRings;

	mNumberOfStepsToSolve = power(2, inNumberOfRings) - 1;

	mPegOriginallyHoldingRing = leftPeg;
	mDestinationPeg = rightPeg;
	mTemporyPeg = middlePeg;
	mStepCounter = 0;
}

void TowerOfHanoi::runRecursiveAlgorithm(int inNumberOfRings, int mPegOriginallyHoldingRing, int inTemporaryPeg, int inDestinationPeg)
{
	std::string tabs = "\t\t";
	if (inNumberOfRings == 1)
	{
		std::cout << "Step " << ++mStepCounter << getTabs() << mPegOriginallyHoldingRing << " > " << inDestinationPeg << std::endl;
	}
	else
	{
		runRecursiveAlgorithm(inNumberOfRings - 1, mPegOriginallyHoldingRing, inDestinationPeg, inTemporaryPeg);
		std::cout << "Step " << ++mStepCounter << getTabs() << mPegOriginallyHoldingRing << " > " << inDestinationPeg << std::endl;
		runRecursiveAlgorithm(inNumberOfRings - 1, inTemporaryPeg, mPegOriginallyHoldingRing, inDestinationPeg);
	}
}

std::string TowerOfHanoi::getTabs()
{
	if (mStepCounter > 99)
	{
		return "\t";
	}
	return "\t\t";
}

// Standard functions
std::string TowerOfHanoi::intToString(int i)
{
	std::stringstream ss;
	std::string s;
	ss << i;
	s = ss.str();
	return s;
}

int TowerOfHanoi::power(int inInteger, int inExponent)
{
	int retVal = 1;
	for (int i = 0; i < inExponent; i++)
	{
		retVal *= inInteger;
	}

	return retVal;
}

// Standard Functions
std::string TowerOfHanoi::toString()
{
	return "Tower of Hanoi with " + intToString(mNumberOfRings) + " rings.\n";
}

bool TowerOfHanoi::equals(TowerOfHanoi inTowerOfHanoi)
{
	if (this->mNumberOfRings == inTowerOfHanoi.mNumberOfRings)
	{
		return true;
	}
	return false;
}
Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: