2022年马踏棋盘程序设计 .pdf

问题描述设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋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 个可能位置可以用一维数组Htry10 , 7 和 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 种输出方式：（1）以数组下标形式输入，代表起始位置，i 表示行标， j 表示列标。（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。3程序所能达到的功能；让马从任一起点出发都能够历遍整个88 的棋盘。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 二概要设计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) 判断栈是否为空ADTStack 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(SqStackS,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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - return ERROR; *e=*-(*S).top; return OK; 2求最佳策略算法求各点权值 :可走的方向数越少 ,则被上一点选中的可能性越大intnum(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 2 int board88=0;/棋盘初始化int Htry18=-2,-1,1,2,2,1,-1,-2; int Htry28=1,2,2,1,-1,-2,-2,-1; structSElemType int a; int b; int di; int flag8; ; typedefstructSqStack SElemType *base; SElemType *top; intstacksize; ; voidInitStack(SqStack&S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; intStackEmpty(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(inti,int j) if(i=0&i=0&j=7&boardij=0) return 1; else return 0; / 判断该方向是否能够通过intnum(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+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - return count1; SElemTypeNextPos(SElemType e) int x1,y1; inti,j; int x=e.a; int y=e.b; int p=0; intdi_num=0; intdi_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(intx,inty,SqStack&S) SElemTypee,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+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - /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()/ 将马的轨迹输出inti,j; for(i=0;i8;i+) for(j=0;j8;j+) printf(%2d ,boardij); printf(n); int main()/ 主函数intx,y; SqStack S; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - InitStack(S); printf( 输入马的初始位置：n); scanf(%d%d,&x,&y); search(x,y,S); printf( 输出马的移动轨迹：n); display(); return 0; 四验收分析第一次验收时， 我用的是回溯法，程序虽然没有问题，但是程序运行时间过长，半个多小时才会有结果。于是我改用贪心算法，也就是找到可通过方向最少的点作为下一个要走的点。 将回溯法改为贪心算法，并不需要做太多的改动，只需要在结构体中多加一个记录通过方向的量。改动之后，我的算法依然有一些缺憾：8个点的可通过方向数没有用数组存起来并进行排序，可能导致回溯时增加时间复杂度。五运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -