看了网上很多都是用dfs解决的，于是自己就写了一篇用高斯消元法的解决方法
问题描述
把 1 2 3 … 19 共19个整数排列成六角形状，如下：
要求每个直线上的数字之和必须相等。共有15条直线哦！
再给点线索吧！我们预先填好了2个数字，第一行的头两个数字是：15 13，参见下图，黄色一行为所求。
请你填写出中间一行的5个数字。数字间用空格分开。
这是一行用空格分开的整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字等）
解法
把15条直线看成是15条方程，每一个圆看成一个未知数，且未知数的系数为1即六角幻方对应的未知数：
x0 x1 x2
x3 x4 x5 x6
x7 x8 x9 x10 x11
x12 x13 x14 x15
x16 x17 x18
x0+x1+x2=38 x3+x4+x5+x6=38 x7+x8+x9+x10+x11=38 x12+x13+x14+x15=38 x16+x17+x18=38 …太多了，我就不写了
代码
#include
<iostream
>
#include
<cstdio
>
#include
<cstring
>
#include
<cmath
>
#include
<vector
>
using namespace std
;
#define
N 19
#define
M 15
int am
[M][N],bm
[M],col
[N],vi
[N],ans
[N],ans2
[N];
int
in[M][7]={
{0,1,2,-1},
{3,4,5,6,-1},
{7,8,9,10,11,-1},
{12,13,14,15,-1},
{16,17,18,-1},
{0,3,7,-1},
{1,4,8,12,-1},
{2,5,9,13,16,-1},
{6,10,14,17,-1},
{11,15,18,-1},
{2,6,11,-1},
{1,5,10,15,-1},
{0,4,9,14,18,-1},
{3,8,13,17,-1},
{7,12,16,-1}
};
void init(){
memset(am
,0,sizeof(am
));
for(int i
=0;i
<M;i
++)
{
for(int j
=0;in[i
][j
]!=-1;j
++)
{
am
[i
][in[i
][j
]]=1;
}
bm
[i
]=38;
}
for(int i
=0;i
<N;i
++)
col
[i
]=i
;
}
void r_swap(int i
,int j
){
if(i
==j
) return ;
for(int k
=0;k
<N;k
++)
{
swap(am
[i
][k
],am
[j
][k
]);
}
swap(bm
[i
],bm
[j
]);
}
void c_swap(int k
){
int i
;
for(i
=k
;i
<N;i
++)
{
if(am
[k
][i
]!=0)
break;
}
if(k
==i
|| i
>=N) return ;
for(int j
=0;j
<M;j
++)
{
swap(am
[j
][k
],am
[j
][i
]);
}
swap(col
[k
],col
[i
]);
}
int
gcd(int a
,int b
){
return b
==0?a
:gcd(b
,a
%b
);
}
void xiao_yuan(int k
,int j
){
int u
=am
[k
][k
],v
=am
[j
][k
];
if(u
==0||v
==0) return ;
int g
=gcd(u
,v
);
for(int i
=0;i
<N;i
++)
{
am
[j
][i
]=(u
*am
[j
][i
]-v
*am
[k
][i
])/g
;
}
bm
[j
]=(u
*bm
[j
]-v
*bm
[k
])/g
;
}
void show(){
printf("最终消元结果：\n");
for(int i
=0;i
<N;i
++)
{
printf("%5d",col
[i
]);
}
printf(" bm\n");
for(int i
=0;i
<(N+1)*5;i
++)
printf("%c",'-');
printf("\n");
for(int i
=0;i
<M;i
++)
{
for(int j
=0;j
<N;j
++)
printf("%5d",am
[i
][j
]);
printf("%5d\n",bm
[i
]);
}
printf("\n\n");
}
void guass(){
for(int i
=0;i
<M;i
++)
{
for(int j
=i
;j
<M;j
++)
{
if(am
[j
][i
]!=0)
{
r_swap(i
,j
);
break;
}
}
c_swap(i
);
for(int j
=0;j
<M;j
++)
{
if(j
!=i
)
xiao_yuan(i
,j
);
}
}
}
void output(){
if(ans2
[0]!=15||ans2
[1]!=13)
return ;
printf("%*c%2d %2d %2d%*c\n\n",4,' ',ans2
[0],ans2
[1],ans2
[2],6,' ');
printf("%*c%2d %2d %2d %2d%*c\n\n",2,' ',ans2
[3],ans2
[4],ans2
[5],ans2
[6],3,' ');
printf("%2d %2d %2d %2d %2d\n\n",ans2
[7],ans2
[8],ans2
[9],ans2
[10],ans2
[11]);
printf("%*c%2d %2d %2d %2d%*c\n\n",2,' ',ans2
[12],ans2
[13],ans2
[14],ans2
[15],3,' ');
printf("%*c%2d %2d %2d%*c\n\n\n",4,' ',ans2
[16],ans2
[17],ans2
[18],6,' ');
}
void check(){
for(int i
=11;i
>=0;i
--)
{
int t
=0;
for(int j
=12;j
<N;j
++)
{
t
+=am
[i
][j
]*ans
[j
];
}
t
=(bm
[i
]-t
)/am
[i
][i
];
if(t
<1||t
>N)
return ;
for(int j
=i
+1;j
<N;j
++)
{
if(t
==ans
[j
])
return ;
}
ans
[i
]=t
;
}
for(int i
=0;i
<N;i
++)
{
ans2
[col
[i
]]=ans
[i
];
}
output();
}
void f(int
*ans
,int k
){
if(k
<12)
{
check();
return ;
}
for(int i
=1;i
<=N;i
++)
{
bool flag
=true;
for(int j
=k
+1;j
<N;j
++)
{
if(i
==ans
[j
])
{
flag
=false;
break;
}
}
if(flag
)
{
ans
[k
]=i
;
f(ans
,k
-1);
}
}
}
int
main(){
init();
guass();
show();
f(ans
,18);
return 0;
}
结果
