2022年马踏棋盘程序设计方案.docx

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

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

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 Htry2h ）,位于（i,j）的马可以走到新位置是在棋盘范畴内的 （i+ Htry1h,j+ 其中 h=0,1, .7. 一需求分析1输入的形式和输入值的范畴；分开输入马的初始行坐标X 和列坐标 Y,X 和 Y 的范畴都是 0,7

3、 ；2输出的形式；一共供应了 2 种输出方式：（1）以数组下标形式输入,代表起始位置,i 表示行标, j 表示列标；（2）以棋盘形式输出,每一格打印马走的步数,这种方式比较直观；3程序所能达到的功能；名师归纳总结 让马从任一起点动身都能够历遍整个8 8 的棋盘；第 1 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 二概要设计1设定栈的抽象数据类型定义：ADT Stack 数据对象： D=ai|ai CharSet,i=1,2.,n 数据关系 :R1=|ai-1,ai D,i=2,.,n 基本操作 :这里仅列举此题中使用的操作 InitStack&S

4、操作结果 :构建一个空栈；Push&S,e 操作结果 :在栈顶插入新的元素；Pop（&S,&e ）操作结果：将栈顶元素弹出；SetTopS,& e 操作结果：将 e 设为栈顶元素；GetTopS, &e 操作结果：将栈顶元素取出；StackEmptyS 判定栈是否为空ADT Stack 2本程序包含 2 个模块 1.主程序模块 : Void main 初始化棋盘；while1 接受命令；处理命令； 执行 Pathx,y; 2.栈模块实现栈抽象数据类型3探讨每次挑选位置的“ 正确策略” 思路 1）先求出每个坐标点的权值,即是该坐标下一步有几个方向可以走 2）权值越小 ,就被上一点选中的可能性就越

5、大,下一个方向八个值的挑选顺 序储存 MAPXYK 数组中, 0=KS.base *e=*S.top-1; return OK; else return ERROR; Status SetTopSqStack S,SElemType *e ifS.topS.base *S.top-1=*e; return OK; else return ERROR; Status PushSqStack *S,SElemType e /* 插入元素 e 为新的栈顶元素*/ */ if*S.top-*S.base=*S.stacksize /* 栈满,追加储备空间 *S.base=SElemType*reall

6、oc*S.base,*S.stacksize+STACKINCRE MENT*sizeofSElemType; if.*S.base exitOVERFLOW; /* 储备安排失败 */ *S.top=*S.base+*S.stacksize; *S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; Status PopSqStack *S,SElemType *e e 返回其值,并返回OK；否就 /* 如栈不空,就删除S 的栈顶元素,用返回 ERROR */ if*S.top=*S.base 名师归纳总结 - - - - - - -第 4 页,

7、共 9 页精选学习资料 - - - - - - - - - return ERROR; *e=*-*S.top; return OK; 2求正确策略算法求各点权值 :可走的方向数越少 ,就被上一点选中的可能性越大 int numint x1,int y1 int count1=0; forint j=0;j8;j+ int x2=x1+Htry1j; int y2=y1+Htry2j; ifPassx2,y2 count1+; return count1; 主要程序：#include #include #include #define STACK_INIT_SIZE 10 #define ST

8、ACKINCREMENT 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 InitStackSqStack &S S.base=SElemType *mallocSTACK_INIT_SIZE*sizeofSE

9、lemType; 名师归纳总结 - - - - - - -第 5 页,共 9 页精选学习资料 - - - - - - - - - if.S.base exit0; S.top=S.base; S.stacksize=STACK_INIT_SIZE; int StackEmptySqStack &S ifS.base=S.top return 1; else return 0; void PushSqStack &S,SElemType &e ifS.top-S.base=S.stacksize S.base=SElemType *reallocS.base, S.stacksize+STACK

10、INCREMENT*sizeofSElemType; if.S.base exit0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; int PopSqStack &S,SElemType &e ifS.top=S.base return 0; e=*-S.top; return 1; int Passint i,int j ifi=0&i=0&j=7&boardij=0 return 1; else return 0; / 判定该方向是否能够通过int numint x1,int y1 int count1

11、=0; forint j=0;j8;j+ int x2=x1+Htry1j; int y2=y1+Htry2j; ifPassx2,y2 count1+; 名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - return count1; SElemType NextPosSElemType 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; fori=0;i8;i+ ife.flagi.=0 continue;/ 判定该方向是

12、否走过 x1=x+Htry1i; y1=y+Htry2i; ifPassx1,y1 di_num=numx1,y1; ifdi_numdi_min / 判定该方向是否有最少的可通过方向 e.a=x1; e.b=y1; di_min=di_num; p=i; e.flagp=1; return e; int searchint x,int y,SqStack &S SElemType e,curpos; int count=0; memsetcurpos.flag,0,sizeofcurpos.flag;/ 将结构体中的 flag 赋 0 curpos.a=x; curpos.b=y; whil

13、ecount64 x=curpos.a; y=curpos.b; ifPassx,y 如找到下一个点,就将该点压入栈中 count+; 名师归纳总结 - - - - - - -第 7 页,共 9 页精选学习资料 - - - - - - - - - /printfcount=%d n, count; boardxy=count; e.di=0; e=curpos; PushS,e; curpos=NextPose; memsetcurpos.flag,0,sizeofcurpos.flag; else if.StackEmptyS PopS,e; else return 0; count-; 栈

14、中弹出上一个点whilee.di=7&.StackEmptyS 如 8 个方向都不能通过,就从boarde.ae.b=0; PopS,e; count-; ife.di7 如该点的仍有方向没有拜访过,就换下一个方向 e.di+; PushS,e; count+; curpos=NextPose; memsetcurpos.flag,0,sizeofcurpos.flag; return 1; void display/ 将马的轨迹输出 int i,j; fori=0;i8;i+ forj=0;j8;j+ printf%2d ,boardij; printfn; int main/ 主函数 in

15、t x,y; 名师归纳总结 - - - - - - -第 8 页,共 9 页精选学习资料 - - - - - - - - - SqStack S; InitStackS; printf 输入马的初始位置：n; scanf%d%d,&x,&y; searchx,y,S; printf 输出马的移动轨迹：n; display; return 0; 四验收分析第一次验收时, 我用的是回溯法,程序虽然没有问题,但是程序运行时间过长,半 个多小时才会有结果；于是我改用贪心算法,也就是找到可通过方向最少的点作为下一个要走的点； 将回溯法改为贪心算法,并不需要做太多的改动,只需要在结构体中多加一个记录通过方向的量；改动之后,我的算法依旧有一些缺憾：起来并进行排序,可能导致回溯时增加时间复杂度；五运行结果8 个点的可通过方向数没有用数组存名师归纳总结 - - - - - - -第 9 页,共 9 页