www.gusucode.com > C++四柱汉诺塔源代码-源码程序 > C++四柱汉诺塔源代码-源码程序/code/Hanoi.cpp

    //Download by http://www.NewXing.com
// Hanoi.cpp: implementation of the Hanoi class.
//
//////////////////////////////////////////////////////////////////////

#include "Hanoi.h"
#include <iostream>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Hanoi::Hanoi()
{
	ThreePegs = NULL;
	FourPegs = NULL;
	nMaxDishNum = -1;
}

Hanoi::~Hanoi()
{
	delete []ThreePegs;
	delete []FourPegs;
}

bool Hanoi::Init(int num)
{
	if (num <= nMaxDishNum)
	{
		return true;
	}
	else
	{
		Number *pegs_3 = new Number[num+1];
		Number *pegs_4 = new Number[num+1];
		for(int i=0; i<nMaxDishNum; i++)
		{
			pegs_3[i] = ThreePegs[i];
		}
		for(int j=0; j<nMaxDishNum; j++)
		{
			pegs_4[j] = FourPegs[j];
		}
		delete []ThreePegs;
		delete []FourPegs;
		ThreePegs = pegs_3;
		FourPegs = pegs_4;
		nMaxDishNum = num;

		return true;
	}

	return false;
}

/************************************************************************/
/* 三柱汉诺塔问题                                                       */
/************************************************************************/
Number & Hanoi::ThreePegsHanoi(int num)
{
	if (!Init(num))
	{
		exit(1);
	}
	
	Number times;
	if (num <= 0)
	{
		ThreePegs[num] = Number(0);
		return ThreePegs[num];
	}
	else if (num == 1)
	{
		ThreePegs[num] = Number(1);
		return ThreePegs[num];
	}
	else
	{
		if (ThreePegs[num-1].Compare(Number(0)) != 0)
		{
			ThreePegs[num] = ThreePegs[num-1]+ThreePegs[num-1]+Number(1);
			return ThreePegs[num];
		} 
		else
		{
			times = ThreePegsHanoi(num-1);
			ThreePegs[num] = times+times+Number(1);
			return ThreePegs[num];
		}
	}
}

/************************************************************************/
/* 四柱汉诺塔问题                                                       */
/************************************************************************/
Number & Hanoi::FourPegsHanoi(int num)
{
	if (!Init(num))
	{
		exit(1);
	}

	Number minTimes;
	Number times;
	Number fourPegsTimes;
	
	if (num <= 0)
	{
		FourPegs[num] = Number(0);
		return FourPegs[num];
	}
	else if (num == 1)
	{
		FourPegs[num] = Number(1);
		return FourPegs[num];
	}
	else if (FourPegs[num].Compare(Number(0)) != 0)
	{
		return FourPegs[num];
	} 
	else
	{
		fourPegsTimes = FourPegsHanoi(0);
		times = fourPegsTimes+ThreePegsHanoi(num)+fourPegsTimes;
		minTimes = times;
		for (int i=1; i<num; i++)
		{
			fourPegsTimes = FourPegsHanoi(i);
			times = fourPegsTimes+ThreePegsHanoi(num-i)+fourPegsTimes;
			minTimes = Number::MinNum(minTimes, times);
		}
		FourPegs[num] = minTimes;
		return FourPegs[num];
	}
}