国际象棋马走满棋盘不重复.pdf

《国际象棋马走满棋盘不重复.pdf》由会员分享，可在线阅读，更多相关《国际象棋马走满棋盘不重复.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 实习报告实习报告 题目:编制一个实现8X8马踏棋盘的一个程序.班级:11计算机2班 组员:潘财策 斯祯量 章春伟 朱伟 完成日期:2013.6.7 一一 需求分析需求分析 将马随机放在国际象棋的8 8棋盘ch0707的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个8 8的方阵，输出之 二二 概要设计概要设计 为实现上述功能需要一个顺序的栈存储每一步，以及一个模拟马踏棋盘过程的模块。为此需要两个抽象数据类型，即栈和马踏棋盘.1.对栈的抽象数据定义为:void InitSta

2、ck(SqStack&S)；/构造一个空栈S bool GetTop(SqStack&S,XY&e);/若栈不空，则用e返回s的栈顶元素，返回OK；否则返回ERROR void Push(SqStack&S,XY&e);/插入元素e为新的栈顶元素 bool Pop(SqStack&S);/若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR 2.对马踏棋盘的抽象数据定义为:void Cha(XY&e)；/判断可选的最佳位置并排序 bool Next(XY&e,int ch8,SqStack&S,XY&r);/贪心法判断下一步的可能选位置，并返回OK 若找不到位置返回ER

3、ROR void MT(int ch8,SqStack&S);/依次重复运行，找出所有位置 3.本程序包涵3个模块:1)主程序模块.2)实现栈操作模块.3)实现马踏棋盘操作模块.三三 详细设计详细设计#include#include#include#define STACK_INIT_SIZE 70#define STACKINCREMENT 10 void gz()/程序说明 system(cls);printf(*n);printf(*程序说明：*n);printf(*8X8 的国际棋盘 *n);printf(*输入两个数字作为马的初始位置 *n);printf(*输入数据必须在 07 之

4、间 *n);printf(*程序将给出马的遍历行走路线 *n);printf(*路线以步数形式给出 *n);printf(*计算机 2 班 16 组*nn);printf(输入初始位置开始程序：);typedef struct /定义 Po 型数据，Po 为下一步棋的坐标（简称当前步的出口）int x;/x 坐标 int y;/y 坐标 int p;/当前步出口的下一步棋出口的数量 Po;typedef struct /定义 XY 类型，xy 为当前步棋 int x;/x 坐标 int y;/y 坐标 int p;/当前步棋的出口序号 int n;/当前步棋的出口数量 Po a8;/Po 型数

5、组 XY;typedef struct /定义栈 XY*base;XY*top;int stacksize;SqStack;void InitStack(SqStack&S)/建立空栈 S.base=(XY*)malloc(STACK_INIT_SIZE*sizeof(XY);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;bool GetTop(SqStack&S,XY&e)/顶端元素赋值给 e，返回 ture if(S.top=S.base)return false;e=*(S.top-1);return

6、 true;void ChP(SqStack&S,XY e)/修改栈顶端元素 *(S.top-1)=e;void Push(SqStack&S,XY&e)if(S.top-S.base=S.stacksize)/如果栈存储空间不够，增加分配空间 S.base=(XY*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(XY);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;(*S.top).x=e.x;/把 e 压入栈 (*S.top

7、).y=e.y;(*S.top).p=e.p;S.top+;bool Pop(SqStack&S)if(S.top=S.base)return false;/如果空栈返回 false -S.top;/删除栈顶元素 return true;int NextP(XY e,int ch8)/通过传入步数和棋盘信息 /返回出口数 int X8=-1,1,2,2,1,-1,-2,-2;/X 轴坐标变化值 int Y8=2,2,1,-1,-2,-2,-1,1;/Y 轴坐标变化值 int i,p=0;for(i=0;i=0&e.ae.n.y+Yi=0&e.ae.n.x+Xi8&e.ae.n.y+Yi8&ch

8、e.ae.n.x+Xie.ae.n.y+Yi=0)p+;/循环 8 次找出此坐标的出口数目 return p;/出口数以 p 值返回 void Cha(XY&e)/以出口数由小到大为出口排序 int i,j;Po temp;for(i=0;ie.n;i+)/冒泡排序实现出口坐标以对应出口数由小到大排序 for(j=i+1;je.aj.p)/满足条件交换位置 temp=e.ai;e.ai=e.aj;e.aj=temp;bool Next(XY&e,int ch8,SqStack&S,XY&r)/此函数用于判断是否含有合适出口,以 BOOL 形式返回 /初始化第初次走过的坐标 /传出下一步可走的位

9、置 int X8=-1,1,2,2,1,-1,-2,-2;int Y8=2,2,1,-1,-2,-2,-1,1;int i;if(e.p=0)e.n=0;for(i=e.p;i=0&e.y+Yi=0&e.x+Xi8&e.y+Yi8&che.x+Xie.y+Yi=0)e.ae.n.x=e.x+Xi;e.ae.n.y=e.y+Yi;e.ae.n.p=NextP(e,ch);e.n+;if(e.n=0)return false;/如果没有出口 则返回 false Cha(e);/引用 Cha 函数对出口坐标排序 e.p=0;/标记点为 0 r.x=e.ae.p.x;r.y=e.ae.p.y;/r 为

10、下一步的坐标 r.p=0;e.p+;/标记点后移 ChP(S,e);/将改动入栈 return true;/返回 true if(e.p!=0&e.pe.n)/判断该用于处理回溯过程 r.x=e.ae.p.x;r.y=e.ae.p.y;r.p=0;e.p+;ChP(S,e);return true;return false;/不满足以上条件则为回溯也无法找到出口 返回 false void MT(int ch8,SqStack&S)/函数用于实现马踏棋盘的过程 int n=1;bool f=1;XY e,r;while(n64&f)/当没有走到第 64 步切栈不为空则进入循环 f=GetTop

11、(S,e);/提取栈顶元素 栈为空则 f=0 if(Next(e,ch,S,r)/Next 返回 true 则可找到下一步 做入栈操作 Push(S,r);n+;/步数+1 chr.xr.y=n;/标记棋盘 else if(f&!Next(e,ch,S,r)/满足次条件 说明无路可走 退栈 GetTop(S,e);che.xe.y=0;/清除棋盘标记 Pop(S);n-;/步数-1 int main()/主函数 int n,m;gz();/屏幕提示 while(scanf(%d%d,&n,&m)!=EOF)/当输入不为 EOF 时 执行马踏棋盘函数 int ch88=0,i,j;/初始化棋盘

12、SqStack S;XY e;InitStack(S);/创建新栈用于存放步 e.x=m;e.y=n;e.p=0;che.xe.y=1;/记录第 1 步 Push(S,e);/通过输入的值 将第一步入栈 MT(ch,S);/通过 MT 函数实现马踏棋盘操作 system(cls);/清屏 printf(初始位置为(%d,%d)nn 0 1 2 3 4 5 6 7n,n,m);printf(+-+-+-+-+-+-+-+-+n);for(i=0;i8;i+)printf(%d|,i);for(j=0;j8;j+)printf(%3d|,chij);printf(n);printf(+-+-+-+-+-+-+-+-+n);printf(nn 请输入下一个初始位置或退出：);/输出棋盘 return 0;四四 调试分析调试分析 1.初期对栈操作不熟练,花费了大量时间熟悉.2.对于空间复杂度理解不够,导致空间利用不合理,效率低下.3.首次测试的程序由于没有对算法进行优化，导致时间效率非常低，导致调试时间过长.4.通过加入优先选用出口数最少的坐标先走的优化后极大的缩短了程序的运行时间.五五 测试结果测试结果