问题描述设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋8*8的棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘全部的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个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示:Htry101234567-2-11221-1-2Htry2012345671221-1-2-2-1位于(i,j)的马可以走到新位置是在棋盘范围内的(i+Htry1[h],j+Htry2[h]),其中h=0,1,….7.一.需求分析1.输入的形式和输入值的范围;分开输入马的初始行坐标X和列坐标Y,X和Y的范围都是[0,7]。2.输出的形式;一共提供了2种输出方式:(1)以数组下标形式输入,代表起始位置,i表示行标,j表示列标。(2)以棋盘形式输出,每一格打印马走的步数,这种方式比较直观。3.程序所能达到的功能;让马从任一起点出发都能够历遍整个8×8的棋盘。二.概要设计1.设定栈的抽象数据类型定义:ADTStack{数据对象:D={ai|ai∈CharSet,i=1,2..,n}数据关系:R1={ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作:(这里仅列举本题中使用的操作)InitStack(&S)操作结果:构建一个空栈。Push(&S,e)操作结果:在栈顶插入新的元素。Pop(&S,&e)操作结果:将栈顶元素弹出。SetTop(S,&e)操作结果:将e设为栈顶元素。GetTop(S,&e)操作结果:将栈顶元素取出。StackEmpty(S)判断栈是否为空}ADTStack2.本程序包含2个模块(1).主程序模块:Voidmain(){初始化棋盘;while(1){接受命令;处理命令;}执行Path(x,y);}(2).栈模块-实现栈抽象数据类型3.探讨每次选择位置的“最佳策略”思路1)先求出每个坐标点的权值,即是该坐标下一步有几个方向可以走2)权值越小,则被上一点选中的可能性就越大,下一个方向八个值的选择顺序保存MAP[X][Y][K]数组中,0=K=7,例如MAP[X][Y][0]保存的是下一步优先选择走的方向,MAP[X][Y][7]就是最后才走的。边界的点最先走,然后再走中间。4.踏遍棋盘伪码算法:While(){若已经走了64步,则{打印输出结果;}否则{若该点所有方向已走完{出栈}若该点所有方向未走完{若该点未走过且在棋盘内{入栈,已走步数加1}否则{*下一步方向加1}}}}三.详细设计1.栈类型structSElemType{inta;intb;intdi;//方向编号intflag[8];//访问过的方向数};栈的顺序存储表示typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;};栈基本操作:StatusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈,则返回TRUE,否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusGetTop(SqStackS,SElemType*e){/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR/if(S.topS.base){*e=*(S.top-1);returnOK;}elsereturnERROR;}StatusSetTop(SqStackS,SElemType*e){if(S.topS.base){*(S.top-1)=*e;returnOK;}elsereturnERROR;}StatusPush(SqStack*S,SElemTypee){/*插入元素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;returnOK;}StatusPop(SqStack*S,SElemType*e){/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}2.求最佳策略算法求各点权值:可走的方向数越少,则被上一点选中的可能性越大intnum(intx1,inty1){intcount1=0;for(intj=0;j8;j++){intx2=x1+Htry1[j];inty2=y1+Htry2[j];if(Pass(x2,y2)){count1++;}}returncount1;}主要程序:#includestdio.h#includemalloc.h#includestring.h#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2intboard[8][8]={0};//棋盘初始化intHtry1[8]={-2,-1,1,2,2,1,-1,-2};intHtry2[8]={1,2,2,1,-1,-2,-2,-1};structSElemType{inta;intb;intdi;intflag[8];};typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;};voidInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}intStackEmpty(SqStack&S){if(S.base==S.top)return1;elsereturn0;}voidPush(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;}intPop(SqStack&S,SElemType&e){if(S.top==S.base)return0;e=*--S.top;return1;}intPass(inti,intj){if(i=0&&i=7&&j=0&&j=7&&board[i][j]==0)return1;elsereturn0;}//判断该方向是否能够通过intnum(intx1,inty1){intcount1=0;for(intj=0;j8;j++){intx2=x1+Htry1[j];inty2=y1+Htry2[j];if(Pass(x2,y2)){count1++;}}returncount1;}SElemTypeNextPos(SElemTypee){intx1,y1;inti,j;intx=e.a;inty=e.b;intp=0;intdi_num=0;intdi_min=8;for(i=0;i8;i++){if(e.flag[i]!=0)continue;//判断该方向是否走过x1=x+Htry1[i];y1=y+Htry2[i];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.flag[p]=1;returne;}intsearch(intx,inty,SqStack&S){SElemTypee,curpos;intcount=0;memset(curpos.flag,0,sizeof(curpos.flag));//将结构体中的flag赋0curpos.a=x;curpos.b=y;while(count64){x=curpos.a;y=curpos.b;if(Pass(x,y)){若找到下一个点,则将该点压入栈中count++;//printf(count=%d\n,count);board[x][y]=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);elsereturn0;count--;while(e.di==7&&!StackEmpty(S)){若8个方向都不能通过,则从栈中弹出上一个点board[e.a][e.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));}}}return1;}voiddisplay(){//将马的轨迹输出inti,j;for(i=0;i8;i++){for(j=0;j8;j++){printf(%2d,board[i][j]);}printf(\n);}}intmain(){//主函数intx,y;SqStackS;InitStack(S);printf(输入马的初始位置:\n);scanf(%d%d,&x,&y);search(x,y,S);printf(输出马的移动轨迹:\n);display();return0;}四.验收分析第一次验收时,我用的是回溯法,程序虽然没有问题,但是程序运行时间过长,半个多小时才会有结果。于是我改用贪心算法,也就是找到可通过方向最少的点作为下一个要走的点。将回溯法改为贪心算法,并不需要做太多的改动,只需要在结构体中多加一个记录通过方向的量。改动之后,我的算法依然有一些缺憾:8个点的可通过方向数没有用数组存起来并进行排序,可能导致回溯时增加时间复杂度。五.运行结果