2022年马踏棋盘c++课程设计 .pdf

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

1、1问题描述设计一个国际象棋的马踏棋盘的演示程序2需求分析(1)将马随即放在国际象棋的8 8 棋盘 Board88 的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64 个方格。(2)编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2, ,64 依次填入一个8 8 的方阵，输出之。(3)程序执行命令为：1)输入起始方格坐标(X,Y) 2)求解第一组路径并显示,按 Q 键退出系统，按其他任意键求解并显示下一组路径。(4)测试数据 :(0,0),(1,2) 3 概要设计3.1程序设计思路 . 按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考

2、虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。3.2存储结构设计 8 个可能位置可以用两个一维数组表示：数组 1： 0 1 2 3 4 5 6 7 -2 -1 1 1 2 2 1 -1 -2 数组 2：0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 位于（ i,j ）的马可以走到的新位置是在棋盘范围内的（I+数组 1h,j+ 数组 2h）,其中 h=0，1，7。每次在多个可走位置中选择其中一个进行试探，其中未曾试探过的可走位置用适当栈结构妥善管理，也

3、备试探失败时的 “ 回溯 ” （悔棋）使用，即用栈结构存储试探的路径来进行路径试探操作。3.3主要算法设计 3.3.1 栈类的定义和接口: template class MyStack private:Type *bottom; / 元素存放的动态数组int size,ptr; / 堆栈大小和当前栈顶元素索引inline int extent(); /当栈满时 ,自动扩充public: /构造函数MyStack() bottom=new TypeBASESIZE;ptr=-1;size=BASESIZE;/用默认大小初始化名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

4、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - MyStack(int i) bottom=new Typei;ptr=-1;size=i; /用指定大小初始化/析构函数MyStack()if(bottom!=NULL) delete bottom; /清栈inline void clear();/判栈空inline bool IsEmpty();/入栈int push(Type e); /出栈int pop(Type &e); /获得栈顶元素int top(Type &e); /直接修改栈定元素

5、int settop(Type e); / 用 callback 函数对栈从栈底向上遍历void traverse(void callback(Type *),Type *); ; 3.3.2 本程序的结构1)主程序模块 : void main() 初始化；向屏幕输出输入提示；接受输入起始坐标(X,Y) ；输出第一组解的路径和回溯情况；while(1) 接受命令；处理命令 if(命令 =退出 ) 退出；其他命令 输出下一组解的路径及回溯情况； 异常处理 ；正常退出； 2)路径求解模块 -求解所有可行的路径3)可行路径求解的核心算法: 名师资料总结 - - -精品资料欢迎下载 - - - - -

6、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - bool Result(int start_x, int start_y, int board8) 初始化路径栈sPath; 初始化方向栈sDir; 初始化当前步数序号和当前方向step = 1, d = 0 将点 (start_x,start_y)入路径栈 ,将该点方向d 入方向栈；while(1) 将当前的路径栈中点出栈并保存，将该点方向出栈并保存；/为上一次的目标点和目标方向if(方向 =8) 抹去该点痕迹；步数序号-1；调用 My

7、Stack 的 traverse函数演示退栈情况；退栈；方向栈中的方向 +；continue; if(方向 8)/ 方向未走完if( 目标点在棋盘内且未被走过) 记录序号，目标点入栈，目标点方向初始为0 入栈；continue; else(目标点已被走过或目标点不在棋盘内) 方向 +；continue;/继续 /enf if(d8) if (步数序号已满 ) 向屏幕输出路径if（查看下一路径） 回退一步；方向+；continue; /end while(1) 3.4测试用例设计 依次输入（ 0，0） （1，2）4 详细设计4.1 堆栈类 MyStack 参见文件base 中 MyStack 模

8、板类的定义和实现。4.2 求解出所有路径为了快速求解出所有路径，使用了优化策略，即计算各个点的可以行走的下一个点的个数作为点的权值存放在权值矩阵weight88 中；然后根据这个矩阵对各点的8 方向各方向按权设置优先级，保存于各点方向矩阵序列 map888 ，权值小的优先行走。详见 horse.cpp 文件中的setweight,setmap 函数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 4.3 求解路径核心算法函数b

9、ool Result(int myx, int myy, int board8) MyStack sPath; / 栈,记录路径点MyStack sDir; / 栈,记录方向选择MyPoint p,dest_p; / 当前点和目标点int step = 1, d = 0; / 当前序号 ,方向p.x = myx; p.y = myy; sPath.push(p); sDir.push(d);/起始点的坐标和首选方向入栈, /mapxy0 未必是 (x,y) 点的 offset0 方向 ,而是到该点可到的权值最小的点的方向即offsetmapxy0 boardp.xp.y = 1;/ 起始点标记

10、已走且序号为1 MyPoint pTemp;int iTemp; while(1) if (step=N*N) /路径完成 void(*pFun)(MyPoint *) ; pFun=&TraverseOut;MyPoint *e=NULL; coutn 起始点为(myx,myy)的解空间 n; cout依次走以下坐标(按行顺序 )第 num=8)/ 该点所有方向已走完，退栈 boardxy=0;/初始化 ; step-; sPath.pop(pTemp);sDir.pop(iTemp);/ 退栈sDir.top(iTemp); sDir.settop(iTemp+1);/ 更改方向conti

11、nue; /end if (d=8) if(d8)/ 方向未走完int off=mapxyd; dest_p.x=x+offsetoff.x;dest_p.y=y+offsetoff.y; if(check(dest_p.x,dest_p.y)&boarddest_p.xdest_p.y=0)/目标点在棋盘内且未被走过,则将目标点入栈同时标记为已走过 boardxy=step;/ 记录序号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - -

12、 - - step+; sPath.push(dest_p);/存入目标点sDir.push(0); /存入方向栈初始0; continue; else/i 目标点已被走过或目标点不在棋盘内,换方向 d+;/ 取下一个方向sDir.settop(d);/ 换方向continue;/继续 /enf if(d8) /end while(1) 4.4main 和其他 UI 函数核心代码/*horse.cpp 马踏棋盘算法实现文件文件 base 是自定义的数据结构类的定义和实现文件*/ #include #include base using namespace std; /*全局宏，常量，变量，函数

13、声明*/ #define N 8 / 棋盘大小int mapNN8; /按各点权值递升存放待走方向,每点 8 个int weightNN; /各点的权值int boardNN; / 表示棋盘的数组static MyPoint offset8 = / 8个候选方向的偏移 -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1 ; char ch;int num=1; void setweight();/ 求各点权值void setmap(); /各点的 8 个方向按权值递增排列bool Result(int x, int y, int boa

14、rd8); /主算法函数/*主函数 */ void main() for(int i=0;i8;i+) for(int j=0;j8;j+) boardij=0; setweight(); setmap(); char x,y; while(1) coutx; couty; if(x7|y7) cout起始坐标错误 ,重新输入！ nn; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - else break; bool re=R

15、esult(x-0,y-0,board); coutendlendl; if(re=false) coutBye!nn; else coutGood Bye!nn; /end main() /*求各点权值 :可走的方向数 .该值越小 ,则被上一点选中的可能性越大*/ void setweight() for(int i=0;iN;i+)/for 1 for(int j=0;jN;j+)/for 2 weightij=0; for(int k=0;k=0&x=0&yN) weightij+;/即在 8 个方向中，（i，j）点有几个方向可以移动 /end of for 1 /end setweig

16、ht() /*检查 (i,j) 是否在棋盘内 */ int check(int i,int j) if(i=8|j=8) return 0; return 1; /*标准输出 */ void output() cout 求解结果矩阵第 num 组 n; num+; for(int i=0;i8;i+) for(int j=0;j8;j+) if(boardij=0) cout64t; else coutboardijt; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 1

17、0 页 - - - - - - - - - coutendl; coutn; coutch; /*将各点的 8 个方向按该方向下的目标点的权值递增排列，不可到达的目标点(超出棋盘 )的方向放在最后面*/ void setmap() for(int i=0;iN;i+)/for 1 for(int j=0;jN;j+)/for 2 for(int k=0;k8;k+) mapijk=k;/设置默认方向索引for(int k=0;k8;k+)/for 3 与 for 4 两个循环对方向索引按点的权值升序排列，不能到达的方向排在最后 for(int m=k+1;mweightx2y2 )/*都可到但

18、达m 方向权值小 */) mapijk=d2; mapijm=d1; /*向交换两个方值*/ /end if /end for 4 /end for 3 /end for 2 /end for 1 /end setmap() void TraverseOut(MyPoint *e) static iEndl=1; cout(x,y) ; iEndl%=8; if(iEndl=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - -

19、 coutendl; iEndl+; bool Result(int myx, int myy, int board8)/ bool (*callback)(MyStack&, bool)=NULL) MyStack sPath; / 栈,记录路径点MyStack sDir; / 栈,记录方向选择MyPoint p,dest_p; / 当前点和目标点int step = 1, d = 0; / 当前序号 ,方向p.x = myx; p.y = myy; sPath.push(p); sDir.push(d);/起始点的坐标和首选方向入栈, / mapxy0 未必是 (x,y)点的 offset

20、0 方向 ,而是到该点可到的权值最小的点的方向即offsetmapxy0 boardp.xp.y = 1;/ 起始点标记已走且序号为1 MyPoint pTemp;int iTemp; while(1) if (step=N*N) /*void(*pFun)(MyPoint *) ; pFun=&TraverseOut;MyPoint *e=NULL; coutn 起始点为(myx,myy)的解空间 n; cout依次走以下坐标(按行顺序 )第 num=8)/ 该点所有方向已走完，退栈 /coutendlback:(x ,y=8) if(d8)/ 方向未走完 int off=mapxyd; 名

21、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - dest_p.x=x+offsetoff.x;dest_p.y=y+offsetoff.y; if(check(dest_p.x,dest_p.y)&boarddest_p.xdest_p.y=0)/目标点在棋盘内且未被走过,将目标点入栈并标记当前点为已走过 /coutnin :(dest_p.x,dest_p.y) step=step d:d;/debug info boardx

22、y=step;/ 记录序号step+; sPath.push(dest_p);/存入目标点sDir.push(0); /存入方向栈初始0; continue; else/i 目标点已被走过或目标点不在棋盘内,换方向 d+;/ 取下一个方向sDir.settop(d);/ 换方向continue;/继续 /enf if(d8) /end while(1) 5 调试分析程序中的指针操作多次出现错误，尤其发生在操作栈中的方向分量时，由于操作的失误，开始实际未保存此数据，导致多次循环需要回溯时进入死循环。后改用 Visual Studio 2003 中 VC+.net 中的调试工具发现栈内的所有 di

23、r 分量值均为 -1，后改正即可。因为这个问题，我重改了一次整个程序。6 程序说明1)输入起始方格坐标(X,Y) 2)求解第一组路径并显示,按 Q 键退出系统，按其他任意键求解并显示下一组路径7 经验和体会由于一开始没有使用优化算法，使得路径计算很慢，采用了各点加权然后对各方向按权设置行走优先级的策略后求解速度很快，可以在极短的时间内求出一组解。本程序可以求出所有的可行解。在本实验中，用MyStack 堆栈类的traverse 方法可以演示堆栈回溯情形，不过在字符界面下不够直观，图形界面正在开发中。该C+堆栈模板类是自定义的通用模板类。路径求解核心算法Result 的效率与很多因数有关，比如起

24、始点，优化策略等，本程序使用的优化策略效率很高。通过该实验， 对基于堆栈的算法设计更深的认识，在刚开始调试的时候由于没有给MyStack 堆栈类定义一个直接修改栈顶元素的函数settop,所以要修改方向有点麻烦，必须先出栈，然后+1，然后再入栈，在定义了该函数后可以直接修改栈定元素。在设计 MyStack 类的时候，对C+的通用模板类设计有了深的理解8 程序结果8.1INPUT 输入的起始坐标 :(0,0) OUTPUT: 输出的第一组路径矩阵: 1 4 37 20 59 6 45 22 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

25、- - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 38 19 2 5 50 21 60 7 3 36 51 58 53 44 23 46 18 39 54 63 56 49 8 61 35 14 57 52 43 62 47 24 40 17 64 55 48 27 30 9 13 34 15 42 11 32 25 28 16 41 12 33 26 29 10 31 其他组解略8.2INPUT 输入的起始坐标 :(1，2) OUTPUT: 输出的第一组路径矩阵: 2 29 48 15 12 31 56 17 47 14 1 30 49 16 11 32 28 3 50 13 62 57 18 55 51 46 61 58 39 54 33 10 4 27 52 63 60 37 40 19 45 24 59 38 53 64 9 34 26 5 22 43 36 7 20 41 23 44 25 6 21 42 35 8名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -