hanoi.cpp

汉诺塔算法演示程序

#include "StdAfx.h"
#include "Hanoi.h"
#include "HanoiDlg.h"




CHanoi::CHanoi(void):pieNum(3),pies(NULL),nTotalMoveCount(0),pDC(NULL),pView(NULL)
{
	stockCount[0] = 3;
	stockCount[1] = 0;
	stockCount[2] = 0;
}

void CHanoi::initial(CView *pView,CDC* pDC){
	CHanoi::pView = pView;
	CHanoi::pDC = pDC;
	if(pies) delete []pies;//删除上一次创建的用于记录圆盘信息的数组
	nTotalMoveCount = 0;
	stockCount[1] = 0;
	stockCount[2] = 0;

	CHanoiDlg hDlg;
	hDlg.pieNum = pieNum;
	INT_PTR result = hDlg.DoModal();
	if(result == IDOK){
		TRACE("Hanoi初始化,pieNum = %d\n",hDlg.pieNum);
		pieNum = hDlg.pieNum;
		stockCount[0] = pieNum;
		pies = new Pan[pieNum + 1];
		for(int i = 1;i<=pieNum;i++){
			pies[i].st = A;
			pies[i].layer = pieNum - i +1;//最底层的圆盘为第一层
		}
		TRACE("pies[1].layer = %d\n",pies[1].layer);
	}
	stockCount[0] = pieNum;
	//下面是初始化界面
/*	pView->ValidateRgn(NULL);*/
	CBrush brush;
	brush.CreateSolidBrush(RGB(255,255,255));
	pDC->SelectObject(&brush);
	pDC->Rectangle(0,0,1280,1000);//清除屏幕，不知有没更好的方法
	CString s;
	for(int i=0;i<3;i++)//画三个架子
	{
		TRACE("画三个架子for，i=%d",i);
		pDC->MoveTo(50+i*250,300);
		pDC->LineTo(250+i*250,300);
		pDC->MoveTo(150+i*250,300);
		pDC->LineTo(150+i*250,50);
		s.Format("%1c",'A'+i);
		pDC->TextOut(146+i*250,25,s);
	}
	pDC->TextOut(50,350,"设计人员：梁晓湛， 洪炎峰， 方菲菲，李晓春");

	CBrush brushClear;
	brushClear.CreateSolidBrush(RGB(0,150,0));
	pDC->SelectObject(&brushClear);
	int j=0;
	int k=0;
	for(int i=1;i<=pieNum;i++)//画几个长方饼，m_nTie为长方形个数
	{
		TRACE("画第 %2d 个圆盘",i);
		j=pies[i].st;
		k=pies[i].layer;
		pDC->Rectangle(150+j*250-i*25,300-k*25,
			150+j*250+i*25,300-k*25+25);
	}

	s.Format("总的移动次数=%d",0);
	pDC->TextOut(50,330,s);
	pView->Invalidate(FALSE);
}

CHanoi::~CHanoi(void)
{
	if(pies) delete []pies;
}

void CHanoi::doAlgorithm(CView *pView,CDC* pDC){
	CHanoi::pView = pView;
	CHanoi::pDC = pDC;
	doHanoi(pieNum,A,B,C);
}

void CHanoi::doHanoi(int n, Stock x, Stock y, Stock z){
	if(n == 1)
		move(x,1,z);
	else{
		doHanoi(n-1, x, z, y);
		move(x,n,z);
		doHanoi(n-1, y, x, z);
	}
}

void CHanoi::move(Stock origin, int n, Stock target){
	stockCount[origin]--;
	stockCount[target]++;
	pies[n].st = target;
	pies[n].layer = stockCount[target];
	
	pause(2);
/*	pView->ValidateRgn(NULL)*/;

/*	pView->Invalidate(TRUE);*/
	

	CBrush brush;
	brush.CreateSolidBrush(RGB(255,255,255));
	pDC->SelectObject(&brush);
	pDC->Rectangle(0,0,1280,1000);//清除屏幕
	CString s;
	for(int i=0;i<3;i++)//画三个架子
	{
		TRACE("画三个架子for，i=%d",i);
		pDC->MoveTo(50+i*250,300);
		pDC->LineTo(250+i*250,300);
		pDC->MoveTo(150+i*250,300);
		pDC->LineTo(150+i*250,50);
		s.Format("%1c",'A'+i);
		pDC->TextOut(146+i*250,25,s);
	}
	pDC->TextOut(50,350,"设计人员：梁晓湛， 洪炎峰， 方菲菲，李晓春");
	s.Format("总的移动次数=%d",++nTotalMoveCount);
	TRACE("总的移动次数=%d",++nTotalMoveCount);
	pDC->TextOut(50,330,s);
	CBrush brush2;
	brush2.CreateSolidBrush(RGB(0,150,0));
	pDC->SelectObject(&brush2);
	int j=0;
	int k=0;
	for(int i=1;i<=pieNum;i++)//画几个长方饼，m_nTie为长方形个数
	{
		TRACE("画第 %2d 个圆盘",i);
		j=pies[i].st;
		k=pies[i].layer;
		pDC->Rectangle(150+j*250-i*25,300-k*25,
					150+j*250+i*25,300-k*25+25);
	}

}
//程序暂停，单位为 秒

void CHanoi::pause(float ftime){
	time_t start,end;
	time(&start);
	do{
		time(&end);
	}while((end-start)<ftime);
}