国际象棋马的哈密尔顿回路.docx
《国际象棋马的哈密尔顿回路.docx》由会员分享，可在线阅读，更多相关《国际象棋马的哈密尔顿回路.docx（17页珍藏版）》请在冰点文库上搜索。
国际象棋马的哈密尔顿回路
算法分析与设计实验报告
第2次实验
姓名
学号
班级
时间
3.19上午
地点
四合院
实验名称
国际象棋马的哈密尔顿回路
实验目的
通过上机实验，要求掌握国际象棋马的哈密尔顿回路算法的问题描述、算法设计思想、程序设计。
实验原理
使用分治算法，根据不同的输入用例，能准确的输出马的哈密尔顿路线，有坐标和步数两种形式。
实验步骤
①设置马的哈密尔顿路线的基础数据；
②设置行数和列数分别为m,n，当m,n大于等于12时，分割步，将棋盘尽可能平均地分割成四块，当m,n=4k时，分割为2个2k,当m,n=4k+2时，分割为1个2k和1个2k+2；
③合并步，分别删除4个子棋盘中的结构化的边，添入新边构成整个棋盘的结构化哈密顿回路；
④输出马的哈密顿回路到文件中。
关键代码
//分治法的主体由如下算法comb给出
boolKnight:
:
comb（intmm,intnn,intoffx,intoffy）{
intmm1,mm2,nn1,nn2;
intx[8],y[8],p[8];
if（odd（mm）||odd（nn）||mm-nn>2||nn-mm>2||mm<6||nn<6）return1;
if（mm<12||nn<12）{//基础解
base_answer（mm,nn,offx,offy）;
return0;
}
mm1=mm/2;
if（mm%4>0）mm1--;
mm2=mm-mm1;
nn1=nn/2;
if（nn%4>0）nn1--;
nn2=nn-nn1;
//分割步
comb（mm1,nn1,offx,offy）;
comb（mm1,nn2,offx,offy+nn1）;
comb（mm2,nn1,offx+mm1,offy）;
comb（mm2,nn2,offx+mm1,offy+nn1）;
//合并步
x[0]=offx+mm1-1;
y[0]=offy+nn1-3;
x[1]=x[0]-1;
y[1]=y[0]+2;
x[2]=x[1]-1;
y[2]=y[1]+2;
x[3]=x[2]+2;
y[3]=y[2]-1;
x[4]=x[3]+1;
y[4]=y[3]+2;
x[5]=x[4]+1;
y[5]=y[4]-2;
x[6]=x[5]+1;
y[6]=y[5]-2;
x[7]=x[6]-2;
y[7]=y[6]+1;
for（inti=0;i<8;i++）
p[i]=pos（x[i],y[i],n）;
//交界处重新连接
for（inti=1;i<8;i+=2）{
intj1=（i+1）%8,j2=（i+2）%8;
if（link[x[i]][y[i]].x==p[i-1]）link[x[i]][y[i]].x=p[j1];
elselink[x[i]][y[i]].y=p[j1];
if（link[x[j1]][y[j1]].x==p[j2]）link[x[j1]][y[j1]].x=p[i];
elselink[x[j1]][y[j1]].y=p[i];
}
return0;
}
//base_answer是根据基础解构造子棋盘的结构化的Hamilton回路
voidKnight:
:
base_answer（intmm,intnn,intoffx,intoffy）{
if（mm==6&&nn==6）construct（mm,nn,offx,offy,n,b66）;
if（mm==6&&nn==8）construct（mm,nn,offx,offy,n,b68）;
if（mm==8&&nn==6）construct（mm,nn,offx,offy,n,b86）;
if（mm==8&&nn==8）construct（mm,nn,offx,offy,n,b88）;
if（mm==8&&nn==10）construct（mm,nn,offx,offy,n,b810）;
if（mm==10&&nn==8）construct（mm,nn,offx,offy,n,b108）;
if（mm==10&&nn==10）construct（mm,nn,offx,offy,n,b1010）;
if（mm==10&&nn==12）construct（mm,nn,offx,offy,n,b1012）;
if（mm==12&&nn==10）construct（mm,nn,offx,offy,n,b1210）;
}
//实质性的构造由算法construct完成,完成点与点之间的连接
voidKnight:
:
construct（intm,intn,intoffx,intoffy,intcol,grid*b）{
inti,p,q,k=m*n;
for（i=0;iintx1=offx+b[i].x,y1=offy+b[i].y;
intx2=offx+b[（i+1）%k].x,y2=offy+b[（i+1）%k].y;
p=pos（x1,y1,col）;
q=pos（x2,y2,col）;
link[x1][y1].x=q;
link[x2][y2].y=p;
}
}
//由out按要求输出计算出的结构化的Hamilton回路
voidKnight:
:
out（）{
inti,j,k,x,y,p,**a;
a=newint*[m];
for（k=0;ka[k]=newint[n];
}
Make2DArray1（a,m,n）;
if（comb（m,n,0,0））return;
for（i=0;ifor（j=0;ja[i][j]=0;
i=0;
j=0;
k=2;
a[0][0]=1;
cout<<"（0,0）"<<"";
for（p=1;px=link[i][j].x;
y=link[i][j].y;
i=x/n;
j=x%n;
if（a[i][j]>0）{
i=y/n;
j=y%n;
}
a[i][j]=k++;
cout<<"（"<if（（k-1）%n==0）cout<}
cout<for（i=0;ifor（j=0;jcout<cout<}
}
测试结果
实验心得
这个实验对于我来说是比较困难的，在小班课上没有听太懂，在课下自己又理解了一下，也请教了同学之后我懂了这个算法的关键地方就是怎样把分割的四块合起来，当行数和列数都小于12时，有基础解可以直接使用，当大于等于12时，就将整个棋盘分割成四块，每一小块都有基础解，接下来的问题就是将这四块整合在一起，方法就是分别删除4个子棋盘中的结构化的边，添入新边构成整个棋盘的结构化哈密顿回路，最后再调用输出函数就可以输出马的哈密顿回路了。
通过这个实验我深刻地意识到分治法可以将一个复杂的大问题分割为同样解法的小问题，这样理解起来会更快一些。
实验得分
助教签名
附录：
完整代码
#include
#include
usingnamespacestd;
//grid是表示整数对的结构
typedefstruct{
intx;
inty;
}grid;
//二维数组的构造
voidMake2DArray1（int**a,intm,intn）{
for（inti=0;ifor（intj=0;ja[i][j]=0;
}
voidMake2DArray2（grid**link,intm,intn）{
for（inti=0;ifor（intj=0;jlink[i][j].x=0;
link[i][j].y=0;
}
}
//odd函数,判断奇偶
boolodd（intx）{
if（x%2==0）return0;
elsereturn1;
}
//用一个类Knight实现算法
classKnight{
public:
Knight（intm,intn）;
~Knight（）{};
voidout（）;
public:
intm,n;
grid*b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;
intpos（intx,inty,intcol）;
voidchange（intm,intn,int**a,grid*b）;
voidconstruct（intm,intn,intoffx,intoffy,intcol,grid*b）;
voidbase_answer（intmm,intnn,intoffx,intoffy）;
boolcomb（intmm,intnn,intoffx,intoffy）;
};
//构造函数读入基础数据，初始化各数组
Knight:
:
Knight（intmm,intnn）{
inti,j,k;
m=mm;
n=nn;
b66=newgrid[36];
b68=newgrid[48];
b86=newgrid[48];
b88=newgrid[64];
b810=newgrid[80];
b108=newgrid[80];
b1010=newgrid[100];
b1012=newgrid[120];
b1210=newgrid[120];
//初始化二维数组a和link
link=newgrid*[m];
for（k=0;klink[k]=newgrid[n];
}
int**a=newint*[10];
for（k=0;k<10;k++）{
a[k]=newint[12];
}
Make2DArray2（link,m,n）;
Make2DArray1（a,10,12）;
inta66[6][6]={
{1,30,33,16,3,24},
{32,17,2,23,34,15},
{29,36,31,14,25,4},
{18,9,6,35,22,13},
{7,28,11,20,5,26},
{10,19,8,27,12,21},
};
for（i=0;i<6;i++）
for（j=0;j<6;j++）
a[i][j]=a66[i][j];
change（6,6,a,b66）;
inta68[6][8]={1,10,31,40,21,14,29,38,
32,41,2,11,30,39,22,13,
9,48,33,20,15,12,37,28,
42,3,44,47,6,25,18,23,
45,8,5,34,19,16,27,36,
4,43,46,7,26,35,24,17
};
for（i=0;i<6;i++）
for（j=0;j<8;j++）
a[i][j]=a68[i][j];
change（6,8,a,b68）;
change（8,6,a,b86）;
inta88[8][8]={1,46,17,50,3,6,31,52,
18,49,2,7,30,51,56,5,
45,64,47,16,27,4,53,32,
48,19,8,29,10,55,26,57,
63,44,11,22,15,28,33,54,
12,41,20,9,36,23,58,25,
43,62,39,14,21,60,37,34,
40,13,42,61,38,35,24,59
};
for（i=0;i<8;i++）
for（j=0;j<8;j++）
a[i][j]=a88[i][j];
change（8,8,a,b88）;
inta810[8][10]={1,46,37,66,3,48,35,68,5,8,
38,65,2,47,36,67,4,7,34,69,
45,80,39,24,49,18,31,52,9,6,
64,23,44,21,30,15,50,19,70,33,
79,40,25,14,17,20,53,32,51,10,
26,63,22,43,54,29,16,73,58,71,
41,78,61,28,13,76,59,56,11,74,
62,27,42,77,60,55,12,75,72,57
};
for（i=0;i<8;i++）
for（j=0;j<10;j++）
a[i][j]=a810[i][j];
change（8,10,a,b810）;
change（10,8,a,b108）;
inta1010[10][10]={1,54,69,66,3,56,39,64,5,8,
68,71,2,55,38,65,4,7,88,63,
53,100,67,70,57,26,35,40,9,6,
72,75,52,27,42,37,58,87,62,89,
99,30,73,44,25,34,41,36,59,10,
74,51,76,31,28,43,86,81,90,61,
77,98,29,24,45,80,33,60,11,92,
50,23,48,79,32,85,82,91,14,17,
97,78,21,84,95,46,19,16,93,12,
22,49,96,47,20,83,94,13,18,15
};
for（i=0;i<10;i++）
for（j=0;j<10;j++）
a[i][j]=a1010[i][j];
change（10,10,a,b1010）;
inta1012[10][12]={1,4,119,100,65,6,69,102,71,8,75,104,
118,99,2,5,68,101,42,7,28,103,72,9,
3,120,97,64,41,66,25,70,39,74,105,76,
98,117,48,67,62,43,40,27,60,29,10,73,
93,96,63,44,47,26,61,24,33,38,77,106,
116,51,94,49,20,23,46,37,30,59,34,11,
95,92,115,52,45,54,21,32,35,80,107,78,
114,89,50,19,22,85,36,55,58,31,12,81,
91,18,87,112,53,16,57,110,83,14,79,108,
88,113,90,17,86,111,84,15,56,109,82,13
};
for（i=0;i<10;i++）
for（j=0;j<12;j++）
a[i][j]=a1012[i][j];
change（10,12,a,b1012）;
change（12,10,a,b1210）;
}
//change用于将读入的基础棋盘的Hamilton回路转化为网格数据
voidKnight:
:
change（intm,intn,int**a,grid*b）{
inti,j,k=m*n;
if（mfor（i=0;ifor（j=0;jintp=a[i][j]-1;
b[p].x=i;
b[p].y=j;
}
}else{
for（i=0;ifor（j=0;jintp=a[j][i]-1;
b[p].x=i;
b[p].y=j;
}
}
}
//分治法的主体由如下算法comb给出
boolKnight:
:
comb（intmm,intnn,intoffx,intoffy）{
intmm1,mm2,nn1,nn2;
intx[8],y[8],p[8];
if（odd（mm）||odd（nn）||mm-nn>2||nn-mm>2||mm<6||nn<6）return1;
if（mm<12||nn<12）{//基础解
base_answer（mm,nn,offx,offy）;
return0;
}
mm1=mm/2;
if（mm%4>0）mm1--;
mm2=mm-mm1;
nn1=nn/2;
if（nn%4>0）nn1--;
nn2=nn-nn1;
//分割步
comb（mm1,nn1,offx,offy）;
comb（mm1,nn2,offx,offy+nn1）;
comb（mm2,nn1,offx+mm1,offy）;
comb（mm2,nn2,offx+mm1,offy+nn1）;
//合并步
x[0]=offx+mm1-1;
y[0]=offy+nn1-3;
x[1]=x[0]-1;
y[1]=y[0]+2;
x[2]=x[1]-1;
y[2]=y[1]+2;
x[3]=x[2]+2;
y[3]=y[2]-1;
x[4]=x[3]+1;
y[4]=y[3]+2;
x[5]=x[4]+1;
y[5]=y[4]-2;
x[6]=x[5]+1;
y[6]=y[5]-2;
x[7]=x[6]-2;
y[7]=y[6]+1;
for（inti=0;i<8;i++）
p[i]=pos（x[i],y[i],n）;
//交界处重新连接
for（inti=1;i<8;i+=2）{
intj1=（i+1）%8,j2=（i+2）%8;
if（link[x[i]][y[i]].x==p[i-1]）link[x[i]][y[i]].x=p[j1];
elselink[x[i]][y[i]].y=p[j1];
if（link[x[j1]][y[j1]].x==p[j2]）link[x[j1]][y[j1]].x=p[i];
elselink[x[j1]][y[j1]].y=p[i];
}
return0;
}
//base_answer是根据基础解构造子棋盘的结构化的Hamilton回路
voidKnight:
:
base_answer（intmm,intnn,intoffx,intoffy）{
if（mm==6&&nn==6）construct（mm,nn,offx,offy,n,b66）;
if（mm==6&&nn==8）construct（mm,nn,offx,offy,n,b68）;
if（mm==8&&nn==6）construct（mm,nn,offx,offy,n,b86）;
if（mm==8&&nn==8）construct（mm,nn,offx,offy,n,b88）;
if（mm==8&&nn==10）construct（mm,nn,offx,offy,n,b810）;
if（mm==10&&nn==8）construct（mm,nn,offx,offy,n,b108）;
if（mm==10&&nn==10）construct（mm,nn,offx,offy,n,b1010）;
if（mm==10&&nn==12）construct（mm,nn,offx,offy,n,b1012）;
if（mm==12&&nn==10）construct（mm,nn,offx,offy,n,b1210）;
}
//实质性的构造由算法construct完成,完成点与点之间的连接
voidKnight:
:
construct（intm,intn,intoffx,intoffy,intcol,grid*b）{
inti,p,q,k=m*n;
for（i=0;iintx1=offx+b[i].x,y1=offy+b[i].y;
intx2=offx+b[（i+1）%k].x,y2=offy+b[（i+1）%k].y;
p=pos（x1,y1,col）;
q=pos（x2,y2,col）;
link[x1][y1].x=q;
link[x2][y2].y=p;
}
}
//pos用于表示计算棋盘方格的编号，棋盘方格各行从上到下，各列从左到右依次编号为0,1....,mn-1
intKnight:
:
pos（intx,inty,intcol）{
returncol*x+y;
}
//由out按要求输出计算出的结构化的Hamilton回路
voidKnight:
:
out（）{
inti,j,k,x,y,p,**a;
a=newint*[m];
for（k=0;ka[k]=newint[n];
}
Make2DArray1（a,m,n）;
if（comb（m,n,0,0））return;
for（i=0;ifor（j=0;ja[i][j]=0
升级会员 