Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1366703
  • 博文数量: 946
  • 博客积分: 52360
  • 博客等级: 大将
  • 技术积分: 13080
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-07 17:31
文章分类

全部博文(946)

文章存档

2011年(1)

2008年(945)

我的朋友

分类: C/C++

2008-08-07 17:42:16

下载本文示例代码
下载源代码

汉诺塔问题是最经典的递归问题,笔者就该问题设计了这个游戏,由用户交互游戏和自动演示两部分组成,支持撤销功能、选关、自动完成等功能。

首先建立了类CMap,该类主要实现用户每一步的操作和画图显示功能,记录的时候只须记录每组盘子的个数和盘子的矩形。代码和注释如下:

//记录每一步的盘子的情况

class CMap

{

public:

	//每组盘子的个数

	int iCount[3];

	//3组盘子里面,每个盘子的位置,用矩形表示

	RECT *Rect[3];

	//构造函数

	CMap()

	{

		//三组盘子,每组盘子的矩形

		for(int i=0;i<3;i  )

			Rect[i]=new RECT[NUM];

		//初始化每组盘子的个数

		iCount[0]=NUM;

		iCount[1]=0;

		iCount[2]=0;

		//第一组盘子的矩形的位置

		for(i=0;i

      下面是汉诺塔的主类Hanio,该类的成员函数有OnDraw(),Undo(),Move(),AutoMove()等,分别实现汉诺塔的画图显示、撤销、移动盘子、自动移动盘子等功能,代码及注释如下:
class Hanio

{

public:

	//当前的步数

	int iStep;

	//记录每一步的盘子的情况

	CMap Record[MAXSTEP];

public:

	//构造函数

	Hanio()

	{

		//初始化,步数为0

		iStep=0;

		//初始化记录

		for(int i=0;i0)

			iStep--;

		//重绘

		Draw();

	}

	//移动盘子

	void Move(int iStart,int iEnd)

	{

		//得到当前盘子的记录

		CMap Map=Record[iStep];

		//移动的情况判断,去除非法的移动

		if(iStart<0||iStart>=3)

			return;

		if(iEnd<0||iEnd>=3)

			return;

		if(iStart==iEnd)

			return;

		if(Map.iCount[iStart]<1)

			return;

		//得到移动前的开始组,结束组的盘子的个数

		int iStartRectNum=Map.iCount[iStart];

		int iEndRectNum=Map.iCount[iEnd];

		//从小盘子移动到大盘子上面的情况是不可以的。

		if(iEndRectNum>0)

			if(Width(Map.Rect[iStart][iStartRectNum-1])>=Width(Map.Rect[iEnd][iEndRectNum-1]))

				return;

		//步数累加

		iStep  ;

		//记录新的盘子的情况

		Record[iStep]=Record[iStep-1];

		//移走的那一组盘子的个数减少

		Record[iStep].iCount[iStart]--;

		//被移到的那一组的盘子个数增加

		Record[iStep].iCount[iEnd]  ;

		//重新计算移动后的盘子的矩形

		//主要是被移到的那一组的最上面那个盘子的矩形的计算

		RECT rect;

		rect.left=Center[iEnd]-Width(Map.Rect[iStart][iStartRectNum-1])/2;

		rect.right=Center[iEnd] Width(Map.Rect[iStart][iStartRectNum-1])/2;

		rect.bottom=(NUM 1-Map.iCount[iEnd])*Dx;

		rect.top=(NUM-Map.iCount[iEnd])*Dx;

		Record[iStep].Rect[iEnd][iEndRectNum]=rect;

		//刷新

		SendMessage(hWnd,WM_PAINT,0,0);

	}

	//自动移盘子

	void AutoMove(int iA,int iB,int iC,int iNum)

	{

		//递归实现自动移盘子

		//递归的出口,如果个数为3,按如下进行移动。

		if(iNum==3)

		{

			Move(iA,iC);

			::Sleep(500);



			Move(iA,iB);

			::Sleep(500);



			Move(iC,iB);

			::Sleep(500);



			Move(iA,iC);

			::Sleep(500);



			Move(iB,iA);

			::Sleep(500);



			Move(iB,iC);

			::Sleep(500);



			Move(iA,iC);

			::Sleep(500);

		}

		//个数大于3,递归实现移动。

		else

		{

			//递归自动移动。

			AutoMove(iA,iC,iB,iNum-1);

			Move(iA,iC);

			::Sleep(500);

			AutoMove(iB,iA,iC,iNum-1);

		}

	}

};
程序实现的结果如下图:


由于堆栈内存的限制,选关不可能是无限个盘子,本程序设计的最大关数是8。自动移动是用递归实现的,自动移动的过程中,其他消息无法响应,可以改成多线程或由用户控制的形式。上述的程序附有Visual C 源代码,并在Windows XP和Visual C 6.0下调试成功。 下载本文示例代码
阅读(164) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~