马踏棋盘-实验报告

游戏算法实践实训报告姓名专业班级指导教师2014年1月16日TOC\o"1-1"\h\u5406一．需求分析 题目：需求分析用8x8的棋盘order[8][8]模拟国际象棋，其中的格子存放马的位子，马按走棋规则进行移动。每个方格只进去一次，走遍棋盘上全部的64个方格。用非递归的程序，求得马的行走路线，将数字1,2,…64依次填入order[8][8]数组。每次在多个可走位置中选择其中一个进行试探，每次选择位置的“最佳策略”，即可走位置最少的作为下一个试探位置。这样可以减少回溯次数。其余未曾试探过的可走位置用栈管理，以备试探失败时的“回溯”使用。演示程序以用户与计算机的对话方式执行，用户输入马初始的位置（i,j），输出结果显示在其后，即为马的行走路线。测试数据：(1)马的初始位置（i,j）为：23马的初始位置（i,j）为：11马的初始位置（i,j）为：14马的初始位置（i,j）为：57概要设计为实现上述程序功能，需要顺序栈。顺序栈的抽象数据类型定义为：ADTSqStack{数据对象：D={ai|ai∈Pos,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：intInitStack(SqStack&S)操作结果：构造一个空栈SintStackEmpty(SqStackS)操作结果：若栈S为空栈，则返回1，否则返回0intPush(SqStack&S,PosTypee)操作结果：插入元素e为新的栈顶元素intPop(SqStack&S,PosType&e)操作结果：插入元素e为新的栈顶元素}本程序中包括的四个基本模块：主程序模块：Voidmain(){初始化；求解行走路线；//ChessBoardPath(b,start);}栈模块：实现顺序栈的抽象数据结构求下一位置模块：用最优策略求下一个探测位置求棋盘行走路线模块：do{若当前位置可通，则{ 将当前位置纳入栈顶；并将b[i][j]相应位置的值置为当前编号；若当前位置的编号为64，则结束；否则切换当前位置的最优探测方向作为新的当前位置；}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为下一个最优位置；若栈不空且栈顶位置的四周均不可走，则{b[i][j]相应位置的值置为0；删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到下一个可走位置或出栈至栈空；}}}while(栈不空)；详细设计棋盘坐标结点类型、栈的结构体structPoint{intx;inty;intfrom;};//棋盘坐标位置类型structStack{Point*top;Point*base;intlength;};//顺序栈用顺序栈保存走过的路径，基本操作函数如下：boolInitstack(Stack&s){//构造一个空栈Ss.base=(Point*)malloc(STACKSIZE*sizeof(Point));if(!s.base)returnfalse;s.length=STACKSIZE;s.top=s.base;returntrue;}boolPush(Stack&s,Pointe){//插入元素e为新的栈顶元素if(s.top-s.base>=s.length){s.base=(Point*)realloc(s.base,(s.length+STACKINCREASE)*sizeof(Point));if(!s.base)returnfalse;s.length+=STACKINCREASE;s.top=s.base+s.length;}(*s.top).x=e.x;(*s.top).y=e.y;(*s.top).from=e.from;s.top++;returntrue;}boolPop(Stack&s,Point&e){//若栈不为空，则删除S的栈顶元素if(s.top==s.base)returnfalse;e.x=(*--s.top).x;e.y=(*s.top).y;e.from=(*s.top).from;returntrue;}voidDestroyStack(Stack&s){//销毁栈S，S不在存在free(s.base);}boolStackEmpty(StackS){//若栈S为空栈，则返回ture；否则返回falseif(S.base==S.top)returntrue;elsereturnfalse;}boolGetTop(StackS,Point&e){//若栈不为空，则取栈顶元素if(StackEmpty(S))returnfalse;else{e.x=(*(S.top-1)).x;e.y=(*(S.top-1)).y;e.from=(*(S.top-1)).from;returntrue;}}intGetDeep(StackS){//取栈的深度return(S.top-S.base);}关于行走路径的其他函数：voidSetRound(Pointcur){//查找所在位置的所有可走位置的坐标，将其赋给指针g_round[8]g_round[8];Pointround[]={cur.x-2,cur.y+1,0,cur.x-1,cur.y+2,0,cur.x+1,cur.y+2,0,cur.x+2,cur.y+1,0,cur.x+2,cur.y-1,0,cur.x+1,cur.y-2,0,cur.x-1,cur.y-2,0,cur.x-2,cur.y-1,0,};for(inti=0;i<8;i++){g_round[i].x=round[i].x;g_round[i].y=round[i].y;}}求解马的行走路线boolGetRound(inti,Point&pt){//将所在位置周围所有八个位置坐标赋予指针变量pt，并判断其合理性pt.x=g_round[i-1].x;pt.y=g_round[i-1].y;if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)//判断其合理性returnfalse;elsereturntrue;}主函数：voidmain(){ints=1;charyn;while(s){intorder[8][8]={0};//初始化intcount=0;//计数器，记录的是第几步棋Pointbegin; cout<<"请输入马在棋盘上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8；例如47]:";cin>>begin.x>>begin.y;cout<<endl;begin.from=0;while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){cout<<"输入有误!请重新输入"<<endl;cout<<endl;cout<<"请输入马在棋盘上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8;例如47]:";cin>>begin.x>>begin.y;cout<<endl;}begin.x--;//实际下标是0~7，begin.y--;StackhorseVisit;Pointcur,next;Initstack(horseVisit);Push(horseVisit,begin);//首位置进栈order[begin.x][begin.y]=++count;//计数器+1while(count<64){//其余63步棋的走法 GetTop(horseVisit,cur);SetRound(cur);boolflag=false;for(inti=cur.from+1;i<=8;i++){//按照逆时针的优先规则，选出下一个可用的新位置if(GetRound(i,next)&&order[next.x][next.y]==0){//可用位置未曾使用，则进栈，计数器加1flag=true;order[next.x][next.y]=++count;Pop(horseVisit,cur);cur.from=i;Push(horseVisit,cur);next.from=0;Push(horseVisit,next);break;}}if(!flag){//如果当前位置周围没有路径，则退栈，直至退到存在有最佳位置的坐标intj=0,p;if(begin.x==2&&begin.y==6)p=4;elsep=5;while(j<p&&GetDeep(horseVisit)>1){Pop(horseVisit,cur);order[cur.x][cur.y]=0;count--;j++;}}}DestroyStack(horseVisit);//完成后销毁栈cout<<"棋盘表示:"<<endl;cout<<"12345678"<<endl;for(inti=0;i<8;i++){//输出order数组，数组上数值为路径cout<<setw(12)<<i+1<<setw(2)<<"";for(intj=0;j<8;j++){cout<<resetiosflags(ios::right)<<setw(2)<<order[i][j]<<"";}cout<<endl;} cout<<endl;cout<<"谢谢使用！"<<endl;}}主函数的流程图：输入马在棋盘上的初始位置（i,j）输入马在棋盘上的初始位置（i,j）判定输入是否符合条件0<(i,j)<9?判定输入是否符合条件0<(i,j)<9?否是把i,j的值赋给内部指针变量begin.x,begin.y把i,j的值赋给内部指针变量begin.x,begin.y寻找下一步可走位置的坐标赋给指针g_round[8]寻找下一步可走位置的坐标赋给指针g_round[8]否是否还有别的路可走？是否还有别的路可走？使用最优算法选择下一步（这里采用逆时针优先原则）使用最优算法选择下一步（这里采用逆时针优先原则）是判断下一步是否在棋盘上？判断下一步是否在棋盘上？否是更新马在棋盘上的位置（i,j）更新马在棋盘上的位置（i,j）count=count+1count=>64?count=>64?否是逐行打印棋盘逐行打印棋盘调试分析这个程序刚开始写的时候，在处理如何选择下一步的做法上，我没有用“最优”策略，即找下个位子可走次数最少的，而是简单的将8个位子一个一个探测，结果程序在短时间内运行不出来，开始我不知道是因为算法效率低的缘故，以为是自己写错了，然后修改了算法，输出了结果，但是这时候并没有用最优处理，测试了很多数据都发现不出错误，最后再分析后发现写的算法有问题，根据问题测试出了错误。后来自己又用最优策略去改写，主要是改写了原来的求下一步的函数PosTypeNextPos(PosTypepos)，通过计算下一个方向的可走位置次数，把最小的方向作为最优策略，即为下一步。通过改写，减少了回溯次数，算法的效率得到了很大的提高。在求路径的算法里，主要参考了迷宫的思路，也是程序的核心算法，即当前位置可走，马行走此位置，记录信息，并探测下一位置，采取最优策略，即下一个方向的可走位置数最小的作为下一位置。若当前位置不可走，则退栈，找相邻的下一位置。直至走遍64个格子。但在处理尚有其他方向未被探索时，直接用了求下一步，有重复计算的现象，这是程序要改进的地方。用户手册本程序的运行环境为windows操作系统，执行文件名为：实训项目_马踏棋盘.exe运行程序后，需要根据提示输入马的初始位置(i,j)的值，其中1≤i,j≤8按回车键即可得到测试结果。数字标号即代表马在棋盘上的行走顺序。本程序的输入输出可以无线循环，可以重复输入。测试结果第一组数据测试结果：第二组数据测试结果：第三组数据测试结果：第四组数据测试结果：程序清单stack.h//栈的定义头文件stack.cpp//栈的定义Horsevisit.cpp//马踏棋盘的实现程序八．小结体会一、这次课程设计的心得体会通过实践我的收获如下：1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。九．参考文献[1]严蔚敏，吴伟民编著.数据结构（C语言版）——北京：清华大学出版社，[2]（c++版）——电子工业出版社[3]王红梅，胡明，王涛，数据结构（c++版）——北京：清华大学出版社，2005[4]网上搜索相关程序作为参考(如栈类型的定义等）附录//stack.h#include<malloc.h>#ifndefSTACK_H#defineSTACK_HstructPoint{intx;inty;intfrom;};#defineSTACKSIZE70#defineSTACKINCREASE10structStack{Point*top;Point*base;intlength;};boolInitstack(Stack&s);boolPush(Stack&s,Pointe);boolPop(Stack&s,Point&e);voidDestroyStack(Stack&s);boolStackEmpty(StackS);boolGetTop(StackS,Point&e);intGetDeep(StackS);#endif//stack.cpp#include"stack.h"boolInitstack(Stack&s){//构造一个空栈Ss.base=(Point*)malloc(STACKSIZE*sizeof(Point));if(!s.base)returnfalse;s.length=STACKSIZE;s.top=s.base;returntrue;}boolPush(Stack&s,Pointe){//插入元素e为新的栈顶元素if(s.top-s.base>=s.length){s.base=(Point*)realloc(s.base,(s.length+STACKINCREASE)*sizeof(Point));if(!s.base)returnfalse;s.length+=STACKINCREASE;s.top=s.base+s.length;}(*s.top).x=e.x;(*s.top).y=e.y;(*s.top).from=e.from;s.top++;returntrue;}boolPop(Stack&s,Point&e){//若栈不为空，则删除S的栈顶元素if(s.top==s.base)returnfalse;e.x=(*--s.top).x;e.y=(*s.top).y;e.from=(*s.top).from;returntrue;}voidDestroyStack(Stack&s){//销毁栈S，S不在存在free(s.base);}boolStackEmpty(StackS){//若栈S为空栈，则返回ture；否则返回falseif(S.base==S.top)returntrue;elsereturnfalse;}boolGetTop(StackS,Point&e){//若栈不为空，则取栈顶元素if(StackEmpty(S))returnfalse;else{e.x=(*(S.top-1)).x;e.y=(*(S.top-1)).y;e.from=(*(S.top-1)).from;returntrue;}}intGetDeep(StackS){//取栈的深度return(S.top-S.base);}//horsevisit.cpp/*SourceFiles/HorseVisit.cpp*/#include<iostream>#include"stack.h"#include<iomanip>usingnamespacestd;Pointg_round[8]={0,0,0};voidSetRound(Pointcur){//查找所在位置的所有可走位置的坐标，将其赋给指针g_round[8]g_round[8];Pointround[]={cur.x-2,cur.y+1,0,cur.x-1,cur.y+2,0,cur.x+1,cur.y+2,0,cur.x+2,cur.y+1,0,cur.x+2,cur.y-1,0,cur.x+1,cur.y-2,0,cur.x-1,cur.y-2,0,cur.x-2,cur.y-1,0,};for(inti=0;i<8;i++){g_round[i].x=round[i].x;g_round[i].y=round[i].y;}}boolGetRound(inti,Point&pt){//将所在位置周围所有八个位置坐标赋予指针变量pt，并判断其合理性pt.x=g_round[i-1].x;pt.y=g_round[i-1].y;if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)//判断其合理性returnfalse;elsereturntrue;}voidmain(){ints=1;charyn;while(s){intorder[8][8]={0};//初始化intcount=0;//计数器，记录的是第几步棋Pointbegin; cout<<"请输入马在棋盘上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8；例如47]:";cin>>begin.x>>begin.y;cout<<endl;begin.from=0;while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){cout<<"输入有误!请重新输入"<<endl;cout<<endl;cout<<"请输入马在棋盘上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8;例如47]:";cin>>begin.x>>begin.y;cout<<endl;}begin.x--;//实际下标是0~7，begin.y--;StackhorseVisit;Pointcur,next;Initstack(horseVisit);Push(horseVisit,begin);//首位置进栈order[begin.x][begin.y]=++count;//计数器+1while(count<64){//其余63步棋的走法 GetTop(horseVisit,cur);SetRound(cur);boolflag=false;for(inti=cur