马踏棋盘程序设计.docx
《马踏棋盘程序设计.docx》由会员分享，可在线阅读，更多相关《马踏棋盘程序设计.docx（15页珍藏版）》请在冰点文库上搜索。
马踏棋盘程序设计
"
问题描述
设计一个国际象棋的马踏棋盘的演示程序。
基本要求
将马随机放在国际象棋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]来表示：
Htry1
01234567
-2
）
-1
1
2
2
1
-1
-2
Htry2
%
01234567
1
2
2
1
-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∈D,i=2,...,n}
基本操作:
（这里仅列举本题中使用的操作）
InitStack（&S）
操作结果:
构建一个空栈。
Push（&S,e）
操作结果:
在栈顶插入新的元素。
Pop（&S,&e）
~
操作结果：
将栈顶元素弹出。
SetTop（S,&e）
操作结果：
将e设为栈顶元素。
GetTop（S,&e）
操作结果：
将栈顶元素取出。
StackEmpty（S）
判断栈是否为空
}ADTStack
！
2．本程序包含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;ase=（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==
returnTRUE;
else
returnFALSE;
{
}
StatusGetTop（SqStackS,SElemType*e）
{/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR/
if>
{
*e=*;
returnOK;
}
;
else
returnERROR;
}
StatusSetTop（SqStackS,SElemType*e）
{
if>
{
*=*e;
{
returnOK;
}
else
returnERROR;
}
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;j<8;j++）{
intx2=x1+Htry1[j];
inty2=y1+Htry2[j];
（
if（Pass（x2,y2））{
count1++;}
}
returncount1;
}
主要程序：
#include<>
#include<>
#include<>
#defineSTACK_INIT_SIZE10
#defineSTACKINCREMENT2
intboard[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）{
=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
：
if（!
exit（0）;
=;
=STACK_INIT_SIZE;
}
intStackEmpty（SqStack&S）{
if==
return1;
*
else
return0;
}
voidPush（SqStack&S,SElemType&e）{
if=（SElemType*）realloc,
+STACKINCREMENT）*sizeof（SElemType））;
if（!
exit（0）;
。
=+;
+=STACKINCREMENT;
}
*++=e;
}
intPop（SqStack&S,SElemType&e）{
if==return0;
|
e=*;
return1;
}
intPass（inti,intj）{
if（i>=0&&i<=7&&j>=0&&j<=7&&board[i][j]==0）
return1;
else
:
return0;
}//判断该方向是否能够通过
intnum（intx1,inty1）{
intcount1=0;
for（intj=0;j<8;j++）{
intx2=x1+Htry1[j];
inty2=y1+Htry2[j];
》
if（Pass（x2,y2））{
count1++;}
}
returncount1;
}
SElemTypeNextPos（SElemTypee）{
^
intx1,y1;
inti,j;
intx=;
inty=;
intp=0;
intdi_num=0;
intdi_min=8;
for（i=0;i<8;i++）{
:
if[i]!
=0）continue;//判断该方向是否走过
x1=x+Htry1[i];
y1=y+Htry2[i];
if（Pass（x1,y1））{
di_num=num（x1,y1）;
if（di_num{//判断该方向是否有最少的可通过方向
=x1;
|
=y1;
di_min=di_num;
p=i;
}
}
}
[p]=1;
returne;
~
}
intsearch（intx,inty,SqStack&S）{
SElemTypee,curpos;
intcount=0;
memset,0,sizeof）;//将结构体中的flag赋0
《
=x;
=y;
while（count<64）{
x=;
y=;
if（Pass（x,y））{若找到下一个点，则将该点压入栈中
count++;
//printf（"count=%d\n",count）;
—
board[x][y]=count;
=0;
e=curpos;
Push（S,e）;
curpos=NextPos（e）;
memset,0,sizeof）;
}
else{
'
if（!
StackEmpty（S））
Pop（S,e）;
else
return0;
count--;
while==7&&!
StackEmpty（S））{若8个方向都不能通过，则从栈中弹出上一个点
board[][]=0;
Pop（S,e）;
!
count--;
}
if<7）{若该点的还有方向没有访问过，则换下一个方向
++;
Push（S,e）;
count++;
curpos=NextPos（e）;
memset,0,sizeof）;
}
}
}
return1;
}
voiddisplay（）{//将马的轨迹输出
inti,j;
for（i=0;i<8;i++）{
for（j=0;j<8;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个点的可通过方向数没有用数组存起来并进行排序，可能导致回溯时增加时间复杂度。
五．运行结果
升级会员 