document.txt

此程序为数值算法分析里的跳马算法演示程序

习题六
跳马问题
6.在一个n*n棋盘的......的答案. 
算法描述：
在n*n棋盘上，先给定起始坐标(x,y)，然后依次向8个方向：(x-2,y+1);(x-1,y+2);(x+1,y+2);(x+2,y+1);(x+2,y-1);(x+1,y-2);(x-1,y-2);(x-2,y-1)
进行搜索，发现前面无路可走时进行回溯。本程序采用递归思路。
界限函数：每走一步进行是否越界判断。
n值从3到10，递归算法对3-7都可以在几秒内算出结果。对于8-10，本算法运行时间会长些。
本程序还设有动画演示全过程。
主要算法如下：
int CSeekView::FindPath(int x,int y,int step)
{
	totalSteps++;          //记录总步数
	int i,j;
	flag[x][y]=1;           //标志数组
	pArray[step].x=x;    //pArray为一个struct {int x,int y}结构 ,用来保存路径 x,y
	pArray[step].y=y;
	if(pathNum==0 && m_bAnimation)        //是否开启动画标志    
	{
		PrintGrapth(x,y,0,step+1,false);      //打印路径
	    Sleep(m_interval);                                 //打印延时
	}
	if(step>=n*n-1)                  //找到一条路径后便返回退出
	{
		pathNum=1;
		for(int c=0;c<=step;c++)
		{			pathRecord[c].x=pArray[c].x;      //拷贝路径
					pathRecord[c].y=pArray[c].y;
				}//for
		return 1;
		
	}
	if((i=x+1)>=0 && (i=x+1)<n && (j=y+2)>=0 && (j=y+2)<n && !flag[i][j])      //(x+1,y+2)搜索
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x+2)>=0 && (i=x+2)<n && (j=y+1)>=0 && (j=y+1)<n && !flag[i][j])    //(x+2,y+1)搜索
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x+2)>=0 && (i=x+2)<n && (j=y-1)>=0 && (j=y-1)<n && !flag[i][j])     //(x+2,y-1)搜索
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x+1)>=0 && (i=x+1)<n && (j=y-2)>=0 && (j=y-2)<n && !flag[i][j])    //(x+1,y-2)搜索
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x-1)>=0 && (i=x-1)<n && (j=y+2)>=0 && (j=y+2)<n && !flag[i][j])     //(x-1,y+2)搜索
		if(FindPath(i,j,step+1)) 
			return 1;
	
	if((i=x-2)>=0 && (i=x-2)<n && (j=y+1)>=0 && (j=y+1)<n && !flag[i][j])    //(x-2,y+1)搜索
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x-2)>=0 && (i=x-2)<n && (j=y-1)>=0 && (j=y-1)<n && !flag[i][j])    //(x-2,y-1)搜索
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x-1)>=0 && (i=x-1)<n && (j=y-2)>=0 && (j=y-2)<n && !flag[i][j])  //(x-1,y-2)搜索
		if(FindPath(i,j,step+1))
			return 1;
	
	flag[x][y]=0;           //清除走过的标志

	pArray[step].x=pArray[step].y=-1;
    if(pathNum==0 && m_bAnimation)
	{
		PrintGrapth(x,y,1,step+1,false);
		Sleep(m_interval);
	}
	return 0;              //找不到路径，回溯

}

算法在最坏情况下的时间复杂度为:(n*n)!。空间复杂度为(n*n)!深的系统栈