马踏棋盘程序设计

精选优质文档-倾情为你奉上问题描述 设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋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),(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 -2Htry2 0 1 2 3 4 5 6 712 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种输出方式：（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) 操作结果：将e设为栈顶元素。GetTop(S, &e)操作结果：将栈顶元素取出。StackEmpty(S) 判断栈是否为空 ADT Stack 2本程序包含2个模块(1).主程序模块:Void main() 初始化棋盘；while(1) 接受命令；处理命令；执行Path(x,y);(2).栈模块实现栈抽象数据类型3探讨每次选择位置的“最佳策略”思路1）先求出每个坐标点的权值，即是该坐标下一步有几个方向可以走2）权值越小,则被上一点选中的可能性就越大，下一个方向八个值的选择顺序保存MAPXYK数组中，0=KS.base) *e=*(S.top-1); return OK; else return ERROR; Status SetTop(SqStack S,SElemType *e) if(S.topS.base) *(S.top-1)=*e; return OK; else return ERROR; Status Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素 */ if(*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间 */ (*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 */ 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 STACKINCREMENT 2int 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) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.base=S.top) return 1;else return 0;void Push(SqStack &S,SElemType &e) if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;int Pop(SqStack &S,SElemType &e) if(S.top=S.base) return 0; e=*-S.top; return 1;int Pass(int i,int j) if(i=0&i=0&j=7&boardij=0) return 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=e.a; int y=e.b; int p=0; int di_num=0; int di_min=8; for(i=0;i8;i+) if(e.flagi!=0) continue;/判断该方向是否走过 x1=x+Htry1i; y1=y+Htry2i; if(Pass(x1,y1) di_num=num(x1,y1); if(di_numdi_min) /判断该方向是否有最少的可通过方向 e.a=x1; e.b=y1; di_min=di_num; p=i; e.flagp=1; return e;int search(int x,int y,SqStack &S) SElemType e,curpos; int count=0; memset(curpos.flag,0,sizeof(curpos.flag);/将结构体中的flag赋0 curpos.a=x; curpos.b=y; while(count64) x=curpos.a; y=curpos.b; if(Pass(x,y)若找到下一个点，则将该点压入栈中 count+; /printf(count=%d n, count); boardxy=count; e.di=0; e=curpos; Push(S,e); curpos=NextPos(e); memset(curpos.flag,0,sizeof(curpos.flag); else if(!StackEmpty(S) Pop(S,e); else return 0; count-; while(e.di=7&!StackEmpty(S)若8个方向都不能通过，则从栈中弹出上一个点 boarde.ae.b=0; Pop(S,e); count-; if(e.di7)若该点的还有方向没有访问过，则换下一个方向 e.di+; Push(S,e); count+; curpos=NextPos(e); memset(curpos.flag,0,sizeof(curpos.flag); return 1;void display()/将马的轨迹输出 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个点的可通过方向数没有用数组存起来并进行排序，可能导致回溯时增加时间复杂度。五运行结果专心-专注-专业