Chinaunix首页 | 论坛 | 博客
  • 博客访问: 9547152
  • 博文数量: 1227
  • 博客积分: 10026
  • 博客等级: 上将
  • 技术积分: 20273
  • 用 户 组: 普通用户
  • 注册时间: 2008-01-16 12:40
文章分类

全部博文(1227)

文章存档

2010年(1)

2008年(1226)

我的朋友

分类: C/C++

2008-03-12 08:48:54

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

首先建立了类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下调试成功。
阅读(1853) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~