使用 Win32 和 C++ 的汉诺塔真 GUI

• 下载演示 - 91.76 KB
• 下载源代码 - 23.59 KB 

引言

汉诺塔是一个益智游戏，其中有三个柱子，每个柱子都放着一些盘子。
这里的想法是将第一个柱子上的盘子移动到第三个柱子上，在移动盘子时，必须考虑

1. 尺寸顺序，这意味着在移动盘子时，不能将其放在较小的盘子上。
2. 每次只能移动一个盘子。

请注意，我使用了递归方法。

背景

正式地说，汉诺塔递归函数由以下公式给出：

void Hanoi(int platesCount, int from, int dest, int by)
{
	if (platesCount==1)
	{
		printf(
			"Move the plate from %d to %d through %d"
			, from, dest, by);
	}
else
	{
		Hanoi(platesCount -1, from, by, dest);
		Hanoi(1, from, dest, by);
		Hanoi(platesCount -1, by, dest, from);
	}
} 

这里有一张概念图：

使用程序

启动应用程序后，您将看到下一个屏幕：

然后您需要选择是让程序自动逐步解决问题，还是不让程序自动解决。

Using the Code

在实现程序时，我面临一个问题，即难以分离步骤，因为我使用了递归版本，所以我决定保留递归方法。但是，对 Hanoi 方法的调用只会在按下“下一步”或“解决”按钮时发生一次。在 Hanoi 方法内部，我存储了解决方案的状态，这意味着每次调用时，当前步骤的解决方案都会存储在一个整数列表中。由于 Hanoi 方法中的每个步骤都需要 4 个参数（如上所述），因此将 4 个整数添加到列表中以表示参数。然后，每次调用 SolveNextStep 方法时，程序都会从列表中读取 4 个项目来表示状态。

可用的类如下：

1. HanoiDrawer
2. PlateGUIInfo
3. 工具

无论如何，我将描述 HanoiDrawer 类中的方法，这些方法直接负责解决谜题。

HanoiDrawer 类

// Advance one step to solve Hanoi
void HanoiDrawer::SolveNextStep()
{
	int platesCount
		, source
		, destination
		, intermediate;

	if(listSavedState.size()==0)
	{
		this->Hanoi(this->iPlatesCount, HanoiDrawer::SOURCE
			, HanoiDrawer::DESTINATION, HanoiDrawer::INTERMEDIATE);
	}

	if(listSavedState.size() % 4 != 0 )
	{
		return;
	}

	platesCount = listSavedState.front();
	listSavedState.pop_front();

	source = listSavedState.front();
	listSavedState.pop_front();

	destination = listSavedState.front();
	listSavedState.pop_front();

	intermediate = listSavedState.front();
	listSavedState.pop_front();

	MovePlateFromTo(source, destination);

	this->iMovesCount++;

	if(iMovesCount == this->GetTotalMovesCount())
	{
		this->solved = true;
	}

	SetDlgItemInt(this->hWnd, this->countContainerResourceId, 
						GetMovesCount(), FALSE);

	SetDlgItemText(this->hWnd, this->fromContainerResourceId
				, PlaceIntToString(source).c_str() );
	SetDlgItemText(this->hWnd, this->toContainerResourceId
				, PlaceIntToString(destination).c_str() );
	SetDlgItemText(this->hWnd, this->throughContainerResourceId
				, PlaceIntToString(intermediate).c_str() );
}

// Draws stands and plates
// then do Invalidate
// this operation is required
// in each step
void HanoiDrawer::ReDraw()
{
	DrawStands();

	DrawPlates();

	Invalidate();
}

// The internal function that is responsible
// about solve the problem.
// platesCount : how many plates
// source : the index of the source
// destination : the index of the destination
// intermediate : the index of the intermediate
void HanoiDrawer::Hanoi(int platesCount, int source, int destination, int intermediate)
{
	if (platesCount == 1)
	{
		listSavedState.push_back(platesCount);
		listSavedState.push_back(source);
		listSavedState.push_back(destination);
		listSavedState.push_back(intermediate);
		return;
	}
	else
	{
		Hanoi(platesCount - 1, source, intermediate, destination);
		Hanoi(1, source, destination, intermediate);
		Hanoi(platesCount - 1, intermediate, destination, source);
		return;
	}
}

改进

• 用户可以拖放盘子，然后程序应该验证用户的选择。

注意事项

• 我试图专注于我实现谜题的主要思想，以便于理解我的代码。我没有提及任何与窗口相关的任务。
• 概念图由维基百科的 MG 创建
• http://commons.wikimedia.org/wiki/User:MG
• http://en.wikipedia.org/wiki/Image:Tower_of_Hanoi_4.gif

历史

• v1.0 2007/7/14：主要核心和功能