马踏棋盘程序设计.pdf

《马踏棋盘程序设计.pdf》由会员分享，可在线阅读，更多相关《马踏棋盘程序设计.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 问题描述 设计一个国际象棋的马踏棋盘的演示程序。基本要求 将马随机放在国际象棋 8*8 的棋盘 Board88的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1，2，3.64 一次填入一个 8*8 的方阵 输出之 测试数据 可自行指定一个马的初始位置（i,j）,0=i,j=7.。实现提示 一般说来，当马位于位置（i,j）时，可以走到下列 8 个位置之一 （i-2,j+1）,(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2)

2、,(i-2,j-1)但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8 个可能位置可以用一维数组 Htry107和 HTry20.7来表示：Htry1 0 1 2 3 4 5 6 7-2）-1 1 2 2 1 -1 -2 Htry2%0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2$-1 位于（i,j）的马可以走到新位置是在棋盘范围内的（i+Htry1h,j+Htry2h）,其中 h=0,1,.7.一需求分析 1输入的形式和输入值的范围；分开输入马的初始行坐标 X 和列坐标 Y，X 和 Y 的范围都是0,7。2输出的形式；一共提供了 2 种输

3、出方式：(（1）以数组下标形式输入，代表起始位置，i 表示行标，j 表示列标。（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。3程序所能达到的功能；让马从任一起点出发都能够历遍整个 88 的棋盘。二概要设计 1设定栈的抽象数据类型定义：ADT Stack !数据对象：D=ai|aiCharSet,i=1,2.,n 数据关系:R1=|ai-1,aiD,i=2,.,n 基本操作:(这里仅列举本题中使用的操作)InitStack(&S)操作结果:构建一个空栈。Push(&S,e)操作结果:在栈顶插入新的元素。Pop（&S,&e）操作结果：将栈顶元素弹出。SetTop(S,&e)操作结果

4、：将 e 设为栈顶元素。GetTop(S,&e)操作结果：将栈顶元素取出。StackEmpty(S)判断栈是否为空 ADT Stack ！2本程序包含 2 个模块(1).主程序模块:Void main()初始化棋盘；while(1)接受命令；（处理命令；执行 Path(x,y);(2).栈模块实现栈抽象数据类型 3探讨每次选择位置的“最佳策略”思路 1）先求出每个坐标点的权值，即是该坐标下一步有几个方向可以走 2）权值越小,则被上一点选中的可能性就越大，下一个方向八个值的选择顺序保存 MAPXYK数组中，0=K 否则 若该点所有方向已走完 出栈 若该点所有方向未走完 若该点未走过且在棋盘内 入

5、栈，已走步数加 1 否则*下一步方向加 1 (三详细设计 1栈类型 struct SElemType int a;int b;int di;ase=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S)/*若栈 S 为空栈，则返回 TRUE，否则返回 FALSE*/if=return TRUE

6、;else return FALSE;Status GetTop(SqStack S,SElemType*e)/*若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR/if *e=*;return OK;else return ERROR;Status SetTop(SqStack S,SElemType*e)if *=*e;return OK;else return ERROR;Status Push(SqStack*S,SElemType e)/*插入元素 e 为新的栈顶元素*/if(*S).top-(*S).base=(*S).stacksize)/*栈满，追加存

7、储空间*/、(*S).base=(SElemType*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;Status Pop(SqStack*S,SElemType*e)/*若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR

8、*/if(*S).top=(*S).base)return ERROR;*e=*-(*S).top;return OK;|2求最佳策略算法 求各点权值:可走的方向数越少,则被上一点选中的可能性越大 int num(int x1,int y1)int count1=0;for(int j=0;j8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;(if(Pass(x2,y2)count1+;return count1;主要程序：#include ,#include#include#define STACK_INIT_SIZE 10#define STACKINCREME

9、NT 2 int board88=0;/棋盘初始化 int Htry18=-2,-1,1,2,2,1,-1,-2;int Htry28=1,2,2,1,-1,-2,-2,-1;struct SElemType int a;int b;int di;int flag8;typedef struct SqStack SElemType*base;SElemType*top;int stacksize;void InitStack(SqStack&S)=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);：if(!exit(0);=;=STACK

10、_INIT_SIZE;int StackEmpty(SqStack&S)if=return 1;*else return 0;void Push(SqStack&S,SElemType&e)if =(SElemType*)realloc,+STACKINCREMENT)*sizeof(SElemType);if(!exit(0);。=+;+=STACKINCREMENT;*+=e;int Pop(SqStack&S,SElemType&e)if=return 0;|e=*;return 1;int Pass(int i,int j)if(i=0&i=0&j=7&boardij=0)return

11、 1;else:return 0;/判断该方向是否能够通过 int num(int x1,int y1)int count1=0;for(int j=0;j8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;if(Pass(x2,y2)count1+;return count1;SElemType NextPos(SElemType e)int x1,y1;int i,j;int x=;int y=;int p=0;int di_num=0;int di_min=8;for(i=0;i8;i+):ifi!=0)continue;/判断该方向是否走过 x1=x+Htry

12、1i;y1=y+Htry2i;if(Pass(x1,y1)di_num=num(x1,y1);if(di_numdi_min)/判断该方向是否有最少的可通过方向 =x1;|=y1;di_min=di_num;p=i;p=1;return e;int search(int x,int y,SqStack&S)SElemType e,curpos;int count=0;memset,0,sizeof);/将结构体中的 flag 赋 0 =x;=y;while(count64)x=;y=;if(Pass(x,y)若找到下一个点，则将该点压入栈中 count+;/printf(count=%d n,

13、count);boardxy=count;=0;e=curpos;Push(S,e);curpos=NextPos(e);memset,0,sizeof);else if(!StackEmpty(S)Pop(S,e);else return 0;count-;while=7&!StackEmpty(S)若 8 个方向都不能通过，则从栈中弹出上一个点 board=0;Pop(S,e);!count-;if7)若该点的还有方向没有访问过，则换下一个方向 +;Push(S,e);count+;curpos=NextPos(e);memset,0,sizeof);return 1;void displ

14、ay()/将马的轨迹输出 int i,j;for(i=0;i8;i+)for(j=0;j8;j+)printf(%2d ,boardij);printf(n);int main()/主函数 int x,y;SqStack S;InitStack(S);printf(输入马的初始位置：n);scanf(%d%d,&x,&y);search(x,y,S);printf(输出马的移动轨迹：n);display();return 0;四验收分析 第一次验收时，我用的是回溯法，程序虽然没有问题，但是程序运行时间过长，半个多小时才会有结果。于是我改用贪心算法，也就是找到可通过方向最少的点作为下一个要走的点。将回溯法改为贪心算法，并不需要做太多的改动，只需要在结构体中多加一个记录通过方向的量。改动之后，我的算法依然有一些缺憾：8 个点的可通过方向数没有用数组存起来并进行排序，可能导致回溯时增加时间复杂度。五运行结果