国际象棋马的哈密尔顿回路Word格式文档下载.docx
《国际象棋马的哈密尔顿回路Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《国际象棋马的哈密尔顿回路Word格式文档下载.docx(17页珍藏版)》请在冰点文库上搜索。
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+=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);
nn==8)construct(mm,nn,offx,offy,n,b68);
if(mm==8&
nn==6)construct(mm,nn,offx,offy,n,b86);
nn==8)construct(mm,nn,offx,offy,n,b88);
nn==10)construct(mm,nn,offx,offy,n,b810);
if(mm==10&
nn==8)construct(mm,nn,offx,offy,n,b108);
nn==10)construct(mm,nn,offx,offy,n,b1010);
nn==12)construct(mm,nn,offx,offy,n,b1012);
if(mm==12&
nn==10)construct(mm,nn,offx,offy,n,b1210);
//实质性的构造由算法construct完成,完成点与点之间的连接
construct(intm,intn,intoffx,intoffy,intcol,grid*b){
inti,p,q,k=m*n;
for(i=0;
k;
i++){
intx1=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回路
out(){
inti,j,k,x,y,p,**a;
a=newint*[m];
for(k=0;
k<
m;
k++){
a[k]=newint[n];
Make2DArray1(a,m,n);
if(comb(m,n,0,0))return;
for(j=0;
j<
n;
j++)
a[i][j]=0;
i=0;
j=0;
k=2;
a[0][0]=1;
cout<
<
"
(0,0)"
"
;
for(p=1;
p<
m*n;
p++){
x=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<
("
i<
"
j<
)"
if((k-1)%n==0)cout<
endl;
cout<
a[i][j]<
测试结果
实验心得
这个实验对于我来说是比较困难的,在小班课上没有听太懂,在课下自己又理解了一下,也请教了同学之后我懂了这个算法的关键地方就是怎样把分割的四块合起来,当行数和列数都小于12时,有基础解可以直接使用,当大于等于12时,就将整个棋盘分割成四块,每一小块都有基础解,接下来的问题就是将这四块整合在一起,方法就是分别删除4个子棋盘中的结构化的边,添入新边构成整个棋盘的结构化哈密顿回路,最后再调用输出函数就可以输出马的哈密顿回路了。
通过这个实验我深刻地意识到分治法可以将一个复杂的大问题分割为同样解法的小问题,这样理解起来会更快一些。
实验得分
助教签名
附录:
完整代码
#include<
stdio.h>
iostream>
usingnamespacestd;
//grid是表示整数对的结构
typedefstruct{
intx;
inty;
}grid;
//二维数组的构造
voidMake2DArray1(int**a,intm,intn){
for(intj=0;
a[i][j]=0;
voidMake2DArray2(grid**link,intm,intn){
j++){
link[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();
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];
link[k]=newgrid[n];
int**a=newint*[10];
10;
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},
};
6;
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
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
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
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
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
12;
a[i][j]=a1012[i][j];
change(10,12,a,b1012);
change(12,10,a,b1210);
//change用于将读入的基础棋盘的Hamilton回路转化为网格数据
change(intm,intn,int**a,grid*b){
inti,j,k=m*n;
if(m<
n){
for(i=0;
for(j=0;
intp=a[i][j]-1;
b[p].x=i;
b[p].y=j;
}
}else{
for(j=0;
intp=a[j][i]-1;
//pos用于表示计算棋盘方格的编号,棋盘方格各行从上到下,各列从左到右依次编号为0,1....,mn-1
intKnight:
pos(intx,inty,intcol){
returncol*x+y;
a[i][j]=0